Geodesic
Concurrently controlled grammars
Kybernetika, Tome 54 (2018) no. 4, pp. 748-764
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2018-4-0748
Classification : 68Q45, 68Q85
Keywords: parallel computing; controlled grammars; Petri net; concurrent grammars 
@article{10_14736_kyb_2018_4_0748,
     author = {Mavlankulov, Gairatzhan and Othman, Mohamed and Turaev, Sherzod and Selamat, Mohd Hasan and Zhumabayeva, Laula and Zhukabayeva, Tamara},
     title = {Concurrently controlled grammars},
     journal = {Kybernetika},
     pages = {748--764},
     year = {2018},
     volume = {54},
     number = {4},
     doi = {10.14736/kyb-2018-4-0748},
     mrnumber = {3863254},
     zbl = {06987032},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2018-4-0748/}
}
TY  - JOUR
AU  - Mavlankulov, Gairatzhan
AU  - Othman, Mohamed
AU  - Turaev, Sherzod
AU  - Selamat, Mohd Hasan
AU  - Zhumabayeva, Laula
AU  - Zhukabayeva, Tamara
TI  - Concurrently controlled grammars
JO  - Kybernetika
PY  - 2018
SP  - 748
EP  - 764
VL  - 54
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2018-4-0748/
DO  - 10.14736/kyb-2018-4-0748
LA  - en
ID  - 10_14736_kyb_2018_4_0748
ER  - 
%0 Journal Article
%A Mavlankulov, Gairatzhan
%A Othman, Mohamed
%A Turaev, Sherzod
%A Selamat, Mohd Hasan
%A Zhumabayeva, Laula
%A Zhukabayeva, Tamara
%T Concurrently controlled grammars
%J Kybernetika
%D 2018
%P 748-764
%V 54
%N 4
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2018-4-0748/
%R 10.14736/kyb-2018-4-0748
%G en
%F 10_14736_kyb_2018_4_0748
Mavlankulov, Gairatzhan; Othman, Mohamed; Turaev, Sherzod; Selamat, Mohd Hasan; Zhumabayeva, Laula; Zhukabayeva, Tamara. Concurrently controlled grammars. Kybernetika, Tome 54 (2018) no. 4, pp. 748-764. doi: 10.14736/kyb-2018-4-0748

[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 | MR

[2] Burkhard, H.-D.: Ordered firing in petri nets. Inform. Process. Cybernet. 2 (1989), 3, 71-86. | MR

[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

[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

[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 | MR

[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 | MR

[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

[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

[10] Dassow, J., Turaev, S.: Petri net controlled grammars with a bounded number of additional places. Acta Cybernet. 19 (2010), 609-634. | MR

[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

[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

[14] Ginzburg, A., Yoeli, M.: Vector addition systems and regular languages. J. Comput. System Sci. 20 (1980), 227-284. | DOI | MR

[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 | MR

[17] Jantzen, M.: On the hierarchy of Petri net languages. RAIRO Theoret. Inform. 13 (1979), 1, 19-30. | DOI | MR

[18] Jantzen, M.: Language theory of Petri nets. In: Advances in Petri Nets, volume 254 of LNCS, Springer 1987, pp. 397-412. | MR

[19] Jantzen, M., Kudlek, M., Zetzsche, G.: Language classes defined by concurrent finite automata. Fundamenta Inform. 85 (2008), 1-4, 267-280. | MR

[20] Jantzen, M., Petersen, H.: Cancellation in context-free languages: Enrichment by induction. Theoret. Computer Sci. 127 (1994), 149-170. | DOI | MR

[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

[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

[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

[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

[26] Petri, C.: Kommunication mit Automaten. PhD Thesis, University of Bonn 1962. | MR

[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

[29] Stiebe, R., Turaev, S.: Capacity bounded grammars and Petri nets. EPTCS 3 (2009), 193-203. | DOI | MR

[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 | MR

[36] Yen, H.: On the regularity of petri net languages. Inform. Comput. 124 (1996), 168-181. | DOI | MR

[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 | MR

[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 | MR

Cité par Sources :