State machine of place-labelled petri net controlled grammars
DOI:
https://doi.org/10.11113/mjfas.v13n4.736Keywords:
Petri Net, Context-Free, Grammar, State Machine, Structural SubclassAbstract
A place-labelled Petri net controlled grammar is, in general, a context-free grammar equipped with a Petri net and a function which maps places of the net to productions of the grammar. The languages of place-labelled Petri net controlled grammar consist of all terminal strings that can be obtained by parallel application of the rules of multisets which are the images of the sets of input places in a successful occurrence sequence of the Petri net. In this paper, we investigate the structural subclass of place-labelled Petri net controlled grammar which focus on the state machine. We also establish the generative capacity of state machine of place-labelled Petri net controlled grammars.
References
Petri, C. A. (1962). Kommunication mit Automaten. University of Bonn. Ph.D. Thesis.
Ginzburg, A., Yoeli, M. 1980. Vector Addition Systems and Regular Languages. J. Comput. System Sci. 20, 227-284.
Jantzen, M., Petersen, H. 1994. Cancellation in Context-Free Languages: Enrichment by Induction. Theoret. Comput. Sci. 127, 149-170.
Valk, R., Vidal-Naquet, G. 1981. Petri Nets and Regular Languages. J. Comput. System Sci. 23, 229-325.
Yen, H. C. 1996. On the Regularity of Petri Net Languages. Inf. and Comput. 124, 168–181.
ter Beek, M. H., Kleijn, H. C. M. 2002. Petri Net Control for Grammar Systems. Form. and Natur. Comput. 2300, 220–243.
Farwer, B., Jantzen, M., Kudlek, M., Rolke, H., Zetzsche, G. 2008. Petri Net Controlled Finite Automata. Fund. Inform. 85, 111–121.
Farwer, B., Kudlek, M., Rolke, H. 2007. Concurrent Turing Machines. Fund. Inform. 79, 303–317.
Jantzen, M., Kudlek, M., Zetzsche, G. 2008. Language Classes Defined by Concurrent Finite Automata. Fund. Inform. 85, 267–280.
Zetzsche, G 2009, ‘Grid Erasing in Petri Net Languages and Matrix Grammars’, in 13th International Conference on Developments in Language Theory: proceedings of 13th ICDLT, Universität Stuttgart, Stuttgart, Germany, 30 June-3 July 2009, pp. 490-501.
Dassow, J., Turaev, S. 2008. Arbitrary Petri Net Controlled Grammars’, in Language and Automata Theory and Application: proceedings of LATA, Rovira i Virgili University, Tarragona, Spain, 13-19 March 2008, pp. 27-39.
Dassow, J., Turaev, S. 2009. Grammars Controlled by Special Petri Nets’, Language and Automata Theory and Application: proceedings of LATA, Rovira i Virgili University, Tarragona, Spain, 2-8 April 2009, pp. 326-337.
Stiebe, R., Turaev, S. 2009. Capacity Bounded Grammars. J. Autom. Lang. Comb. 15, 175-194.
Turaev, S. (2010). Petri Net Controlled Grammars. Universitat Rovira I Virgili. Ph.D. Thesis.
Dassow, J., Turaev, S. 2009. Petri Net Controlled Grammars: The Power of Labeling and Final Markings. Romanian J. of Inform. Sci. and Tech. 12, 191-207.
Dassow, J., Turaev, S. 2010. Petri Net Controlled Grammars with a Bounded Number of Additional Places. Acta Cybernet. 19, 609-634.
Mohamad Jan, N., Turaev, S., Fong, W. H., Sarmin, N. H. 2015. A New Variant of Petri Net Controlled Grammars. 22th National Symposium on Mathematical Science: proceedings of SKSM22, Grand Blue Wave Hotel, Shah Alam, Selangor, Malaysia, 24-26 November 2014, pp. 24-26.
Reisig, W., Rozenberg, G. 1998, Lectures on Petri Nets I: Basic Models, Berlin: Springer-Verlag.
Linz, P. 2001. An Introduction to Formal Languages and Automata 3rd. Edition. USA: Jones and Bartlett Publishers.
Rozenberg, G., Salomaa, A. 1997, Handbook of Formal Languages. Berlin: Springer-Verlag.
Peterson, J. L., 1976. Computation Sequence Sets. J. Comput. System Sci. 13, 1-24.
