Multiset Pushdown Automata

Manfred Kudlek, Patrick Totzke, Georg Zetzsche

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
Pages (from-to)221-233
Number of pages13
JournalFundamenta Informaticae
Issue number1-3
Publication statusPublished - 2009


Dive into the research topics of 'Multiset Pushdown Automata'. Together they form a unique fingerprint.

Cite this