Some Remarks on Codes Defined by Petri Nets
Дата
Авторы
Ito,Masami
Dassow,Jürgen
Stiebe,Ralf
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
With any Petri net we associated its CPN language which consists of all sequences of transitions which reach a marking with an empty place whereas all proper prefixes of the sequence lead to positive markings. We prove that any CPN language can be accepted by a partially blind multicounter machine, and that any partially blind multicounter language is the morphic image of some CPN language. As a corollary we obtain the decidability of membership, emptiness and finiteness problem for CPN languages. We characterize the very strictly bounded regular languages, which are CPN languages, and give a condition for a Petri net, which ensures that its generated language is regular. We give a dense CPN language and prove that no dense regular language is a CPN language. 1.) C. S. Calude, K. Salomaa, S. Yu (eds.). Advances and Trends in Automata and Formal Languages. A Collection of Papers in Honour of the 60th Birthday of Helmut Jürgensen.
Ключевые слова
Petri nets , codes , formal languages