Finite automata with multiset memory: a new characterization of Chomsky hierarchy
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.
- Self-modifying finite automata: An introduction
- Theory of reaction automata: a survey
- Decomposition and factorization of chemical reaction transducers
- An automata-theoretic characterization of the Chomsky-hierarchy
- scientific article; zbMATH DE number 2080936 (Why is no real title available?)
- Multi-island finite automata and their even computation.
- Chomskian hierarchies of families of sets of piecewise continuous functions
This page was built for publication: Finite automata with multiset memory: a new characterization of Chomsky hierarchy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805444)
