[FOM] finite automata equipped with bags:
Vaughan Pratt
pratt at cs.stanford.edu
Tue Aug 26 16:14:50 EDT 2008
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?
More information about the FOM
mailing list