Concurrently controlled grammars

Gairatzhan Mavlankulov; Mohamed Othman; Sherzod Turaev; Mohd Hasan Selamat; Laula Zhumabayeva; Tamara Zhukabayeva

Kybernetika (2018)

  • Volume: 54, Issue: 4, page 748-764
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Mavlankulov, Gairatzhan, et al. "Concurrently controlled grammars." Kybernetika 54.4 (2018): 748-764. <http://eudml.org/doc/294368>.

@article{Mavlankulov2018,
abstract = {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.},
author = {Mavlankulov, Gairatzhan, Othman, Mohamed, Turaev, Sherzod, Selamat, Mohd Hasan, Zhumabayeva, Laula, Zhukabayeva, Tamara},
journal = {Kybernetika},
keywords = {parallel computing; controlled grammars; Petri net; concurrent grammars},
language = {eng},
number = {4},
pages = {748-764},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Concurrently controlled grammars},
url = {http://eudml.org/doc/294368},
volume = {54},
year = {2018},
}

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
PB - Institute of Information Theory and Automation AS CR
VL - 54
IS - 4
SP - 748
EP - 764
AB - 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.
LA - eng
KW - parallel computing; controlled grammars; Petri net; concurrent grammars
UR - http://eudml.org/doc/294368
ER -

References

top
  1. Beek, M., Kleijn, H., 10.1007/3-540-45711-9_13, In: Formal and Natural Computing, volume 2300 of LNCS, Springer 2002, pp. 220-243. MR2033911DOI10.1007/3-540-45711-9_13
  2. Burkhard, H.-D., Ordered firing in petri nets., Inform. Process. Cybernet. 2 (1989), 3, 71-86. MR0645978
  3. Dassow, J., Mavlankulov, G., Othman, M., Turaev, S., Selamat, M., Stiebe, R., 10.5772/50637, In: Petri Nets - Manufacturing and Computer Science, InTech 2012, pp. 337-358. DOI10.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., 𝑘 -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. MR2540325
  6. Dassow, J., Turaev, S., 10.1007/978-3-540-88282-4_20, 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. MR2540325DOI10.1007/978-3-540-88282-4_20
  7. Dassow, J., Turaev, S., 10.1007/978-3-642-00982-2_28, 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. MR2544426DOI10.1007/978-3-642-00982-2_28
  8. Dassow, J., Turaev, S., Petri net controlled grammars: the case of special Petri nets., J. Universal Computer Sci. 15 (2009), 14, 2808-2835. MR2580567
  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. MR2580567
  10. Dassow, J., Turaev, S., Petri net controlled grammars with a bounded number of additional places., Acta Cybernet. 19 (2010), 609-634. MR2676349
  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. MR2456374
  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. MR2346250
  14. Ginzburg, A., Yoeli, M., 10.1016/0022-0000(80)90009-4, J. Comput. System Sci. 20 (1980), 227-284. MR0584862DOI10.1016/0022-0000(80)90009-4
  15. Hack, M., Petri Net Languages., Computation Structures Group Memo, Project MAC 124, MIT, 1975. 
  16. Hauschildt, D., Jantzen, M., 10.1007/bf01178731, Acta Inform. 31 (1994), 719-728. MR1306096DOI10.1007/bf01178731
  17. Jantzen, M., 10.1051/ita/1979130100191, RAIRO Theoret. Inform. 13 (1979), 1, 19-30. MR0525455DOI10.1051/ita/1979130100191
  18. Jantzen, M., Language theory of Petri nets., In: Advances in Petri Nets, volume 254 of LNCS, Springer 1987, pp. 397-412. MR0902665
  19. Jantzen, M., Kudlek, M., Zetzsche, G., Language classes defined by concurrent finite automata., Fundamenta Inform. 85 (2008), 1-4, 267-280. MR2456383
  20. Jantzen, M., Petersen, H., 10.1016/0304-3975(94)90104-x, Theoret. Computer Sci. 127 (1994), 149-170. MR1271770DOI10.1016/0304-3975(94)90104-x
  21. Jantzen, M., Zetzsche, G., 10.1007/978-3-540-68746-7_19, In: Applications and Theory of Petri Nets, Proc. 29th International Conference, PETRI NETS 2008, volume 5062, pp. 270-287. DOI10.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., 10.1007/978-981-4585-18-7_58, In: Proc. First International Conference on Advanced Data and Information Engineering (DaEng-2013), LNEE, pp. 521-528. DOI10.1007/978-981-4585-18-7_58
  24. Mavlankulov, G., Othman, M., Selamat, M. H., Turaev, S., 10.1007/978-981-4585-33-0_23, In: International Conference on Mathematical Sciences and Statistics 2013, Springer Singapore 2014, pp. 223-231. DOI10.1007/978-981-4585-33-0_23
  25. Mavlankulov, G., Turaev, S., Zhumabaeva, L., Zhukabayeva, T., 10.1063/1.4915713, In: International Conference On Mathematics, Engineering And Industrial Applications 2014 (ICoMEIA 2014), volume 1660, AIP Publishing, 2015, pp. 5-8. DOI10.1063/1.4915713
  26. Petri, C., Kommunication mit Automaten., PhD Thesis, University of Bonn 1962. MR0158806
  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. MR3801322
  29. Stiebe, R., Turaev, S., 10.4204/eptcs.3.18, EPTCS 3 (2009), 193-203. MR3801322DOI10.4204/eptcs.3.18
  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., 10.1016/0022-0000(81)90067-2, J. Computer System Sci. 23 (2981), 23, 229-325. MR0644730DOI10.1016/0022-0000(81)90067-2
  36. Yen, H., 10.1006/inco.1996.0013, Inform. Comput. 124 (1996), 168-181. MR1373973DOI10.1006/inco.1996.0013
  37. Zetzsche, G., 10.1007/978-3-642-02737-6_40, In: Proc. 13th International Conference on Developments in Language Theory, DLT'09, Berlin, Heidelberg 2009, pp. 490-501. MR2544726DOI10.1007/978-3-642-02737-6_40
  38. Zetzsche, G., 10.1007/978-3-642-22321-1_39, In: Developments in Language Theory, 15th International Conference, DLT 2011, Milan 2011, volume 6795 LNCS, Springer 2011, pp. 452-463. MR2862748DOI10.1007/978-3-642-22321-1_39

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.