[FOM] finite automata equipped with bags:

[Wojciech Moczydlowski]

Seems like you can easily emulate a 2-counter machine with an automaton 
with a bag and 2-counter machines are Turing complete (I'm pretty sure the 
proof is in Hopcroft-Ullman, but I don't have a copy at hand to verify 
it).

Wojtek Moczydlowski

On Sat, 23 Aug 2008, Kreinovich, Vladik wrote:

> Dear Friends,
>
> Undergraduate theory of computation courses usually starts with finite
> automata
> (FA), pushdown automata (FA equipped with a stack into which he can push
> symbols and from which we can pop symbols), and Turing machines (FA with
> a tape
> or, equivalently, with two stacks). It is well understood what languages
> can
> recognized by such devices.
>
> 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?
>
> This idea was proposed by my colleague Amitawa Biswas in 2005; he is
> currently
> analyzing this new device and working on a related paper.
>
> At least some languages not recognizable by a pushdown automata (PDA)
> can be
> recognized by such a device. For example, a textbook example a language
> which
> cannot be recognized by a PDA is L = {a^n b^n c^n}. To recognize this
> language
> in a new device, we first get into an "a" state in which, upon seeing an
> "a"
> symbol, we push this symbol into the bag; upon seeing "b", we get into a
> "b"
> state in which, upon seeing every "b" symbol, we pop an "a" and push a
> "b";
> upon seeing a symbol "c", we get into a "c" state in which, upon seeing
> a
> symbol "c", we pop a symbol from a bag and, if the popped symbol is "b",
> we
> continue. We accept the word if we are in the final state "c" and the
> bag is
> empty.
>
> Amitawa thinks that probably all context-free languages can be
> recognized by
> this new device; maybe it is equivalent to a Turing machine, but he has
> not yet
> been able to prove that.
>
> Since the idea seems natural, he tried to google similar papers but has
> not
> found anything relevant yet.
>
> Any references and/or comments will be greatly appreciated.
>
> Please send your replies to me at vladik at utep.edu and to Amitawa at
> abiswas at utep.edu
>
> Many thanks
>
> Vladik
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>