Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
parallel computing; controlled grammars; Petri net; concurrent grammars
parallel computing; controlled grammars; Petri net; concurrent grammars
Summary:
This paper introduces a new variant of Petri net controlled grammars, namely a 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.
References:
[1] Beek, M., Kleijn, H.: 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 | MR 2033911
[2] Burkhard, H.-D.: Ordered firing in petri nets. Inform. Process. Cybernet. 2 (1989), 3, 71-86. MR 0645978
[3] Dassow, J., Mavlankulov, G., Othman, M., Turaev, S., Selamat, M., Stiebe, R.: Grammars controlled by petri nets. In: Petri Nets - Manufacturing and Computer Science, InTech 2012, pp. 337-358. DOI 10.5772/50637
[4] Dassow, J., Turaev, S.: 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.
[5] Dassow, J., Turaev, S.: $\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. MR 2540325
[6] Dassow, J., Turaev, S.: $\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 | MR 2540325
[7] Dassow, J., Turaev, S.: 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 | MR 2544426
[8] Dassow, J., Turaev, S.: Petri net controlled grammars: the case of special Petri nets. J. Universal Computer Sci. 15 (2009), 14, 2808-2835. MR 2580567
[9] Dassow, J., Turaev, S.: Petri net controlled grammars: the power of labeling and final markings. Romanian J. Inform. Sci. Technol. 12 (2009), 2, 191-207. MR 2580567
[10] Dassow, J., Turaev, S.: Petri net controlled grammars with a bounded number of additional places. Acta Cybernet. 19 (2010), 609-634. MR 2676349
[11] Farwer, B., Jantzen, M., Kudlek, M., Rölke, H., Zetzsche, G.: Petri net controlled finite automata. Fundamenta Inform. 85 (2008), 1-4, 111-121. MR 2456374
[12] Farwer, B., Kudlek, M., Rölke, H.: Petri-net-controlled Machine Models. Technical Report 274, FBI-Bericht, Hamburg 2006.
[13] Farwer, B., Kudlek, M., Rölke, H.: Concurrent Turing machines. Fundamenta Inform. 79 (2007), 3-4, 303-317. MR 2346250
[14] Ginzburg, A., Yoeli, M.: Vector addition systems and regular languages. J. Comput. System Sci. 20 (1980), 227-284. DOI 10.1016/0022-0000(80)90009-4 | MR 0584862
[15] Hack, M.: Petri Net Languages. Computation Structures Group Memo, Project MAC 124, MIT, 1975.
[16] Hauschildt, D., Jantzen, M.: Petri net algorithms in the theory of matrix grammars. Acta Inform. 31 (1994), 719-728. DOI 10.1007/bf01178731 | MR 1306096
[17] Jantzen, M.: On the hierarchy of Petri net languages. RAIRO Theoret. Inform. 13 (1979), 1, 19-30. DOI 10.1051/ita/1979130100191 | MR 0525455
[18] Jantzen, M.: Language theory of Petri nets. In: Advances in Petri Nets, volume 254 of LNCS, Springer 1987, pp. 397-412. MR 0902665
[19] Jantzen, M., Kudlek, M., Zetzsche, G.: Language classes defined by concurrent finite automata. Fundamenta Inform. 85 (2008), 1-4, 267-280. MR 2456383
[20] Jantzen, M., Petersen, H.: Cancellation in context-free languages: Enrichment by induction. Theoret. Computer Sci. 127 (1994), 149-170. DOI 10.1016/0304-3975(94)90104-x | MR 1271770
[21] Jantzen, M., Zetzsche, G.: 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] Marek, V., Češka, M.: 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.
[23] Mavlankulov, G., Othman, M., Selamat, M. H., Turaev, S.: 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] Mavlankulov, G., Othman, M., Selamat, M. H., Turaev, S.: 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] Mavlankulov, G., Turaev, S., Zhumabaeva, L., Zhukabayeva, T.: 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] Petri, C.: Kommunication mit Automaten. PhD Thesis, University of Bonn 1962. MR 0158806
[27] Selamat, M., Turaev, S.: Grammars controlled by Petri nets with place capacities. In: 2010 International Conference on Computer Research and Development 2010, pp. 51-55.
[28] Stiebe, R., Turaev, S.: Capacity bounded grammars. J. Automata, Languages Combinatorics 15 (2009), 1/2, 175-194. MR 3801322
[29] Stiebe, R., Turaev, S.: Capacity bounded grammars and Petri nets. EPTCS 3 (2009), 193-203. DOI 10.4204/eptcs.3.18 | MR 3801322
[30] Stiebe, R., Turaev, S.: 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.
[31] Turaev, S.: Semi-matrix grammars. In: Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS 2006, Mikulov, pp. 245-252.
[32] Turaev, S.: Petri net controlled grammars. In Third Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS 2007, Mikulov, pp. 233-240.
[33] Turaev, S., Krassovitskiy, A., Othman, M., Selamat, M.: 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.
[34] Turaev, S., Krassovitskiy, A., Othman, M., Selamat, M.: Parsing algorithms for regulated grammars. Math. Models Methods Appl. Sci. 6 (2012), 6, 748-756.
[35] Valk, R., Vidal-Naquet, G.: Petri nets and regular languages. J. Computer System Sci. 23 (2981), 23, 229-325. DOI 10.1016/0022-0000(81)90067-2 | MR 0644730
[36] Yen, H.: On the regularity of petri net languages. Inform. Comput. 124 (1996), 168-181. DOI 10.1006/inco.1996.0013 | MR 1373973
[37] Zetzsche, G.: 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 | MR 2544726
[38] Zetzsche, G.: 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 | MR 2862748
Search
Partner of
