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)
Preview |
Cikk, tanulmány, mű
Dassow_2010_ActaCybernetica.pdf Download (286kB) | Preview |
Abstract
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: | http://acta.bibl.u-szeged.hu/38529/ |
| 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 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/12883 |
Actions (login required)
 |
View Item |
