Finite automata with multiset memory: a new characterization of Chomsky hierarchy (Q2805444)

This paper introduces a new type of computing device and studies its computing power. The usual nondeterministic finite automata are augmented with \(d\) memories, each one capable of storing a multiset of natural numbers. These devices are referred to as finite automata with multiset memory (FAMMs). The authors show that FAMMs having \(0\), \(1\) or \(d\geq 2\) additional storage units accept the classes of regular, context-free or computably enumerable languages, respectively.NEWLINENEWLINEIf the contents of the storage units are bounded exponentially in the length of the input then finite automata with multiset memory accept the class of context-sensitive languages.NEWLINENEWLINEThe last section of the paper deals with classes of languages accepted by FAMMs having further memory restrictions.