Petri net controlled grammars with a bounded number of additional places

Dassow Jürgen and Turaev Sherzod: Petri net controlled grammars with a bounded number of additional places. In: Acta cybernetica, (19) 3. pp. 609-634. (2010)

[thumbnail of Dassow_2010_ActaCybernetica.pdf]
Cikk, tanulmány, mű

Download (286kB) | Preview


A context-free grammar and its derivations can be described by a Petri net, called a context-free Petri net, whose places and transitions correspond to the nonterminals and the production rules of the grammar, respectively, and tokens are separate instances of the nonterminals in a sentential form. Therefore , the control of the derivations in a context-free grammar can be implemented by adding some features to the associated cf Petri net. The addition of new places and new arcs from/to these new places to/from transitions of the net leads grammars controlled by k-Petri nets, i.e., Petri nets with additional k places. In the paper we investigate the generative power and give closure properties of the families of languages generated by such Petri net controlled grammars, in particular, we show that these families form an infinite hierarchy with respect to the numbers of additional places.

Item Type: Article
Heading title: Regular papers
Journal or Publication Title: Acta cybernetica
Date: 2010
Volume: 19
Number: 3
ISSN: 0324-721X
Page Range: pp. 609-634
Language: English
Place of Publication: Szeged
Related URLs:
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: p. 633-634. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:24
Last Modified: 2022. Jun. 17. 10:51

Actions (login required)

View Item View Item