[FOM] finite automata equipped with bags:

[Vaughan Pratt]

Dear Vladik,

 From your example of a bag automaton accepting a^n b^n c^n it would 
appear that when the bag contains both a's and b's, one can specify that 
it is an "a" that is popped.  However you didn't say what happens if you 
attempt to pop an "a" when none is there.

If the machine can tell there is no "a" in the bag, then with any 
alphabet with two or more letters, such a machine is Turing universal, 
via the evident reduction to two-counter machines.  (Represent the pair 
(m,n) of values of the two counters as the bag with m copies of "a" and 
n copies of "b".  Pushing and popping "a" corresponds to incrementing 
and decrementing m, while detecting inability to pop "a" corresponds to 
detecting that m = 0, and similarly for "b" and n.)

If however the machine merely blocks when trying to pop a nonexistent 
"a" and disallows that action without any notification (i.e. the 
transition is inapplicable) then a natural problem for "bag automata" is 
whether the empty bag is reachable from a given bag.

If I'm not overlooking something, the acceptance problem for a given bag 
automaton A and input tape I reduces to the reachability problem for 
Petri nets, otherwise known as the vector addition problem (for this 
purpose the input I should be considered simply part of the automaton's 
finite control, and can be assumed to be two-way without changing the 
outcome).  This is because the inapplicability of popping "a" when there 
is no "a" present corresponds to the inapplicability of a transition 
firing rule when the requisite tokens are not present.

In effect you have a counter machine with as many counters as letters in 
the bag's alphabet, but you cannot tell deterministically when a 
particular counter is zero, despite being blocked from decrementing the 
counter when it is zero.

The reachability problem was shown to be decidable in the early 1980's, 
originally claimed by Ernst Mayr in 1981 and a year later shown by Rao 
Kosaraju who cleared up apparent lacunae in Mayr's proof.

It follows that the acceptance problem for any given bag automaton A and 
input I is decidable, whence no bag automaton can emulate a universal 
Turing machine.

Whether the reachability problem is decidable is a very hard question 
that remained open for over a decade.  Had it gone the other way 
(assuming it didn't do so via a Friedberg-Muchnik-type pathology) to the 
extent that even reachability of the origin (corresponding to the empty 
bag) was undecidable, then bag automata would have turned out to be 
Turing universal.

Vaughan Pratt

Kreinovich, Vladik wrote:
> A natural question is: what happens if, instead of a stack, we equip a
> finite
> automaton with a bag (= multi-set = a generalization of a set in which
> we can
> have multiple copies of each element). The resulting non-deterministic
> machine
> can push a symbol into a bag, pop (non-deterministically) a symbol from
> a bag,
> and check whether a bag is empty. What languages can be recognized by
> such a
> device?