Affiliations: Department Informatik, MIN Fakultät
Universität Hamburg Vogt-Kölln-Straße 30, D-22527 Hamburg,
Germany. {kudlek,3totzke,3zetzsch}@informatik.uni-hamburg.de
Note: [] Address for correspondence: Department Informatik, MIN
Fakultät, Universität Hamburg, Vogt-Kölln-Straße 30,
D-22527 Hamburg, Germany
Abstract: Multiset finite Automata, a model equivalent to regular commutative
grammars, are extended with a multiset store and the accepting power of this
extended model of computation is investigated. This type of multiset automata
come in two flavours, varying only in the ability of testing the storage for
emptiness. This paper establishes normal forms and relates the derived language
classes to each other as well as to known multiset language classes.
Keywords: commutative grammars and automata, Petri nets, multiset rewriting and languages
