For the most recent entries see the Petri Nets Newsletter.

Decidability problems in grammar systems.

Mihalache, V.

In: Theoretical Computer Science, Vol. 215, No. 1-2, pages 169-189. 1999.

Abstract: Most of the basic decision problems concerning derivations in cooperating distributed grammar systems have so far been open, possibly because of the lack of unifying methods and techniques. In this paper such a unifying device is proposed. It is called a coverability tree because it bears some resemblance to the coverability graph of place/transition Petri nets and vector addition systems. The coverability tree is always finite, which leads to rather strong decidability properties concerning both arbitrary and terminal derivations. Our method is largely independent of the mode of the derivations and answers most of the direct decidability questions about the components of the system.

Keywords: Petri nets, coverability trees, decidability results, formal grammars, vector additions systems.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography