Kybernetika 54 no. 4, 748-764, 2018

Concurrently controlled grammars

Gairatzhan Mavlankulov, Mohamed Othman, Sherzod Turaev, Mohd Hasan Selamat, Laula Zhumabayeva and Tamara ZhukabayevaDOI: 10.14736/kyb-2018-4-0748

Abstract:

This paper introduces a new variant of Petri net controlled grammars, namely a \textit{concurrently controlled grammar}, where the control over the application of the productions of a grammar is realized by a Petri net with different parallel firing strategies. The generative capacity of these grammars is investigated with respect to transition labeling strategies, definitions of final marking sets and parallel transition firing modes. It is shown that the labeling strategies do not effect the computational power whereas the maximal firing modes increase the power of concurrently controlled grammars with erasing rules up to Turing machines.

Keywords:

Petri net, parallel computing, controlled grammars, concurrent grammars

Classification:

68Q45, 68Q85

paper.pdf

References:

  1. M. Beek and H. Kleijn: Petri net control for grammar systems. In: Formal and Natural Computing, volume 2300 of LNCS, Springer 2002, pp. 220-243.   DOI:10.1007/3-540-45711-9\_13
  2. H.-D. Burkhard: Ordered firing in petri nets. Inform. Process. Cybernet. 2 (1989), 3, 71-86.   CrossRef
  3. J. Dassow, G. Mavlankulov, M. Othman, S. Turaev, M. Selamat and R. Stiebe: Grammars controlled by petri nets. In: Petri Nets - Manufacturing and Computer Science, InTech 2012, pp. 337-358.   DOI:10.5772/50637
  4. J. Dassow and S. Turaev: Arbitrary Petri net controlled grammars. In: Linguistics and Formal Languages (G. Bel-Enguix and M. Jiménez-López, eds.), Second International Workshop on Non-Classical Formal Languages In Linguistics, Tarragona 2008, pp. 27-39.   CrossRef
  5. J. Dassow and S. Turaev: $\mathit{k}$-Petri net controlled grammars. In: Pre-proceedings of Second International Conference on Language and Automata Theory and Applications. Report 36/08, Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona 2008.   CrossRef
  6. J. Dassow and S. Turaev: $\mathit{k}$-Petri net controlled grammars. In: Language and Automata Theory and Applications (C. Martín-Vide, F. Otto, and H. Fernau, eds.), Second International Conference, LATA 2008. Revised Papers, volume 5196 of LNCS, Springer 2008, pp. 209-220.   DOI:10.1007/978-3-540-88282-4\_20
  7. J. Dassow and S. Turaev: Grammars controlled by special Petri nets. In: Language and Automata Theory and Applications (A. Dediu, A.-M. Ionescu, and C. Martín-Vide, eds.), Third International Conference, LATA 2009, volume 5457 of LNCS, Springer 2009, pp. 326-337.   DOI:10.1007/978-3-642-00982-2\_28
  8. J. Dassow and S. Turaev: Petri net controlled grammars: the case of special Petri nets. J. Universal Computer Sci. 15 (2009), 14, 2808-2835.   CrossRef
  9. J. Dassow and S. Turaev: Petri net controlled grammars: the power of labeling and final markings. Romanian J. Inform. Sci. Technol. 12 (2009), 2, 191-207.   CrossRef
  10. J. Dassow and S. Turaev: Petri net controlled grammars with a bounded number of additional places. Acta Cybernet. 19 (2010), 609-634.   CrossRef
  11. B. Farwer, M. Jantzen, M. Kudlek, H. Rölke and G. Zetzsche: Petri net controlled finite automata. Fundamenta Inform. 85 (2008), 1-4, 111-121.   CrossRef
  12. B. Farwer, M. Kudlek and H. Rölke: Petri-net-controlled Machine Models. Technical Report 274, FBI-Bericht, Hamburg 2006.   CrossRef
  13. B. Farwer, M. Kudlek and H. Rölke: Concurrent Turing machines. Fundamenta Inform. 79 (2007), 3-4, 303-317.   CrossRef
  14. A. Ginzburg and M. Yoeli: Vector addition systems and regular languages. J. Comput. System Sci. 20 (1980), 227-284.   DOI:10.1016/0022-0000(80)90009-4
  15. M. Hack: Petri Net Languages. Computation Structures Group Memo, Project MAC 124, MIT, 1975.   CrossRef
  16. D. Hauschildt and M. Jantzen: Petri net algorithms in the theory of matrix grammars. Acta Inform. 31 (1994), 719-728.   DOI:10.1007/bf01178731
  17. M. Jantzen: On the hierarchy of Petri net languages. RAIRO Theoret. Inform. 13 (1979), 1, 19-30.   DOI:10.1051/ita/1979130100191
  18. M. Jantzen: Language theory of Petri nets. In: Advances in Petri Nets, volume 254 of LNCS, Springer 1987, pp. 397-412.   CrossRef
  19. M. Jantzen, M. Kudlek and G. Zetzsche: Language classes defined by concurrent finite automata. Fundamenta Inform. 85 (2008), 1-4, 267-280.   CrossRef
  20. M. Jantzen and H. Petersen: Cancellation in context-free languages: Enrichment by induction. Theoret. Computer Sci. 127 (1994), 149-170.   DOI:10.1016/0304-3975(94)90104-x
  21. M. Jantzen and G. Zetzsche: Labeled step sequences in Petri nets. In: Applications and Theory of Petri Nets, Proc. 29th International Conference, PETRI NETS 2008, volume 5062, pp. 270-287.   DOI:10.1007/978-3-540-68746-7\_19
  22. V. Marek and M. Češka: Petri nets and random-context grammars. In: Proc. 35th Spring Conference: Modelling and Simulation of Systems, MARQ Ostrava, Hradec nad Moravicí 2001, pp. 145-152.   CrossRef
  23. G. Mavlankulov, M. Othman, M. H. Selamat and S. Turaev: Concurrent context-free grammars. In: Proc. First International Conference on Advanced Data and Information Engineering (DaEng-2013), LNEE, pp. 521-528.   DOI:10.1007/978-981-4585-18-7\_58
  24. G. Mavlankulov, M. Othman, M. H. Selamat and S. Turaev: Some properties of the concurrent grammars. In: International Conference on Mathematical Sciences and Statistics 2013, Springer Singapore 2014, pp. 223-231.   DOI:10.1007/978-981-4585-33-0\_23
  25. G. Mavlankulov, S. Turaev, L. Zhumabaeva and T. Zhukabayeva: Parallel firing strategy on petri nets: A review. In: International Conference On Mathematics, Engineering And Industrial Applications 2014 (ICoMEIA 2014), volume 1660, AIP Publishing, 2015, pp. 5-8.   DOI:10.1063/1.4915713
  26. C. Petri: Kommunication mit Automaten. PhD Thesis, University of Bonn 1962.   CrossRef
  27. M. Selamat and S. Turaev: Grammars controlled by Petri nets with place capacities. In: 2010 International Conference on Computer Research and Development 2010, pp. 51-55.   CrossRef
  28. R. Stiebe and S. Turaev: Capacity bounded grammars. J. Automata, Languages Combinatorics 15 (2009), 1/2, 175-194.   CrossRef
  29. R. Stiebe and S. Turaev: Capacity bounded grammars and Petri nets. EPTCS 3 (2009), 193-203.   DOI:10.4204/eptcs.3.18
  30. R. Stiebe and S. Turaev: Capacity bounded grammars and Petri nets. In: 11th International Workshop on Descriptional Complexity of Formal Systems (J. Dassow, G. Pighizzini, and B. Truthe, eds.), Magdeburg 2009, pp. 247-258.   CrossRef
  31. S. Turaev: Semi-matrix grammars. In: Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS 2006, Mikulov, pp. 245-252.   CrossRef
  32. S. Turaev: Petri net controlled grammars. In Third Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS 2007, Mikulov, pp. 233-240.   CrossRef
  33. S. Turaev, A. Krassovitskiy, M. Othman and M. Selamat: Parsing algorithms for grammars with regulated rewriting. In: Recent Researches in Applied Informatics and Remote Sensing, 11th WSEAS International Conference on Applied Computer Science 2011 (A. Zaharim, K. Sopian, N. Mostorakis, and V. Mladenov, eds.), pp. 103-109.   CrossRef
  34. S. Turaev, A. Krassovitskiy, M. Othman and M. Selamat: Parsing algorithms for regulated grammars. Math. Models Methods Appl. Sci. 6 (2012), 6, 748-756.   CrossRef
  35. R. Valk and G. Vidal-Naquet: Petri nets and regular languages. J. Computer System Sci. 23 (2981), 23, 229-325.   DOI:10.1016/0022-0000(81)90067-2
  36. H. Yen: On the regularity of petri net languages. Inform. Comput. 124 (1996), 168-181.   DOI:10.1006/inco.1996.0013
  37. G. Zetzsche: Erasing in petri net languages and matrix grammars. In: Proc. 13th International Conference on Developments in Language Theory, DLT '09, Berlin, Heidelberg 2009, pp. 490-501.   DOI:10.1007/978-3-642-02737-6\_40
  38. G. Zetzsche: A sufficient condition for erasing productions to be avoidable. In: Developments in Language Theory, 15th International Conference, DLT 2011, Milan 2011, volume 6795 LNCS, Springer 2011, pp. 452-463.   DOI:10.1007/978-3-642-22321-1\_39