Multiset Pushdown Automata

• Autorzy: Kudlek M. , Totzke P. , Zetzsche G.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

commutative grammars and automata; Petri net; multiset rewriting and languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 93, nr 1-3
• Strony: 221--233
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Kudlek M.

autor

Totzke P.

autor

Zetzsche G.

• Department Informatik, MIN Fakultät, Universität Hamburg Vogt-Kölln-Straße 30, D-22527 Hamburg, Germany,

Bibliografia

• [1] Crespi-Reghizzi, S., Mandrioli, D.: Commutative grammars, Calcolo, 13(2), 1976, 173-189, ISSN 0008-0624.
• [2] Csuhaj-Varjú, E., Martın-Vide, C., Mitrana, V.: Multiset Automata, Multiset Processing - Mathematical, Computer Science, and Molecular Computing Points of View, 2235, Springer-Verlag, London, UK, 2001.
• [3] Hack, M.: Petri Net Languages, Technical Report CSG MEMO 124, MIT, 6 1975.
• [4] Jantzen,M.: On the hierarchy of Petri net languages, R.A.I.R.O. Informatique théorique/Theoretical Informatics, 13(1), 1979, 19-30.
• [5] Kudlek, M., Mart´ın-Vide, C., P˘aun, G.: Toward a Formal Macroset Theory, in: Multiset Processing - Mathematical, Computer Science, and Molecular Computing Points of View, vol. 2235 of LNCS, 2001, 123-133.
• [6] Kudlek, M., Mitrana, V.: Closure Properties of Multiset Language Families, Fundamenta Informatica, 49, 2002, 191-203.
• [7] Parikh, R. J.: On Context-Free Languages, J. ACM, 13(4), 1966, 570-581, ISSN 0004-5411.