JUCS - Journal of Universal Computer Science 8(2): 260-269, doi: 10.3217/jucs-008-02-0260
Some Remarks on Codes Defined by Petri Nets
expand article infoMasami Ito‡, Jürgen Dassow§, Ralf Stiebe§
‡ Department of Mathematics, Kyoto Sangyo University, Kyoto, Japan§ Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, Magdeburg, Germany

Corresponding author: Masami Ito ( ito@ksuvx0.kyoto-su.ac.jp )

© Masami Ito, Jürgen Dassow, Ralf Stiebe.
This article is freely available under the J.UCS Open Content License.
Citation: Ito M, Dassow J, Stiebe R (2002) Some Remarks on Codes Defined by Petri Nets. JUCS - Journal of Universal Computer Science 8(2): 260-269. https://doi.org/10.3217/jucs-008-02-0260
Open Access
Abstract
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.
Keywords
Petri nets, codes, formal languages