For the most recent entries see the Petri Nets Newsletter.

Twisting Petri Net Languages and How to Obtain them by Reducing Linear Context-Free Sets.

Jantzen, Matthias; Petersen, Holger

In: Proceedings of the 12th International Conference on Application and Theory of Petri Nets, 1991, Gjern, Denmark, pages 228-236. June 1991.

Abstract: It was shown by the authors (1987) (see PN-Newsletter 27, p. 69) that all terminal Petri net languages can be obtained from general context-free sets by complete cancellation of substrings from the Dyck set with one pair of parentheses, the so-called Dyck1-reduction. The authors generalize this characterization by showing that linear context-free languages suffice and that the Dyck set can be replaced by a simpler bounded language. In proving this the authors obtain a new closure property of the family of Petri net languages which is not shared by the context-free sets.

Keywords: terminal net languages; linear context-free set reduction; Dyck reduction; closure property (for) net language(s); context-free set.


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

Back to the Petri Nets Bibliography