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. Acta cybernetica, (19) 3. pp. 609-634. (2010)

[img] Cikk, tanulmány, mű

Download (286kB)


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
Journal or Publication Title: Acta cybernetica
Date: 2010
Volume: 19
Number: 3
Page Range: pp. 609-634
ISSN: 0324-721X
Language: angol
Heading title: Regular papers
Uncontrolled Keywords: Természettudomány, Informatika
Additional Information: Bibliogr.: p. 633-634.; Abstract
Date Deposited: 2016. Oct. 15. 12:24
Last Modified: 2018. Jun. 06. 12:33

Actions (login required)

View Item View Item