Relations between Control Mechanisms for Sequential Grammars

• Autorzy: Alhazov Artiom , Freund Rudolf , Ivanov Sergiu , Oswald Marion

Identyfikatory

DOI

10.3233/FI-2021-2058

• Języki publikacji: EN

Abstrakty

EN

We extend and refine previous results within the general framework for regulated rewriting based on the applicability of rules in sequential grammars [3]. Besides the well-known control mechanisms as control graphs, matrices, permitting and forbidden rules, partial order on rules, and priority relations on rules we also consider the new variant of activation and blocking of rules as investigated in [1, 2, 4]. Moreover, we exhibit special results for strings and multisets as well as for arrays in the general variant defined on Cayley grids of finitely presented groups. Especially we prove that array grammars defined on Cayley grids of finitely presented groups using #-context-free array productions together with control mechanisms as control graphs, matrices, permitting and forbidden rules, partial order on rules, priority relations on rules, or activation and blocking of rules have the same computational power as such array grammars using arbitrary array productions.

Słowa kluczowe

EN

general framework; regulating rewriting; sequential grammars

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 181, nr 2-3
• Strony: 239--271
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Alhazov Artiom

• Vladimir Andrunachievici Institute of Mathematics and Computer Science, Academiei 5, Chişinău, MD-2028, Moldova

autor

Freund Rudolf

• Faculty of Informatics, TU Wien, Favoritenstraße 9-11, 1040 Vienna, Austria

autor

Ivanov Sergiu

• IBISC, Université Évry, Université Paris-Saclay, 23 Boulevard de France, 91025, Évry, France

autor

Oswald Marion

• Faculty of Informatics, TU Wien, Favoritenstraße 9-11, 1040 Vienna, Austria

Bibliografia

• [1] Freund R. Control mechanisms for array grammars on Cayley grids. In: Machines, Computations, and Universality - 8th International Conference, MCU 2018, Fontainebleau, France, June 28-30, 2018, Proceedings, volume 10881 of Lecture Notes in Computer Science. 2018 pp. 1-33. doi:10.1007/978-3-319-92402-1_1.
• [2] Alhazov A, Freund R, Ivanov S. Sequential grammars with activation and blocking of rules. In: Machines, Computations, and Universality - 8th International Conference, MCU 2018, Fontainebleau, France, June 28-30, 2018, Proceedings, volume 10881 of Lecture Notes in Computer Science. 2018 pp. 51-68. doi:10.1007/978-3-319-92402-1_3.
• [3] Freund R, Kogler M, Oswald M. A general framework for regulated rewriting based on the applicability of rules. In: Kelemen J, Kelemenová A (eds.), Computation, Cooperation, and Life - Essays Dedicated to Gheorghe Păun on the Occasion of His 60th Birthday, volume 6610 of Lecture Notes in Computer Science. Springer, 2011 pp. 35-53. doi:10.1007/978-3-642-20000-7_5.
• [4] Alhazov A, Freund R, Ivanov S. P systems with activation and blocking of rules. In: Stepney S, Verlan S (eds.), Unconventional Computation and Natural Computation - 17th International Conference, UCNC 2018, Fontainebleau, France, June 25-29, 2018, Proceedings, volume 10867 of Lecture Notes in Computer Science. Springer, 2018 pp. 1-15. doi:10.1007/978-3-319-92435-9_1.
• [5] Dassow J, Păun Gh. Regulated Rewriting in Formal Language Theory, volume 18 of EATCS Monographs in Theoretical Computer Science. Springer, 1989.
• [6] Freund R. Control mechanisms on #-context-free array grammars. In: Păun Gh (ed.), Mathematical Aspects of Natural and Formal Languages, pp. 97-137. World Scientific Publ., Singapore, 1994. doi:10.1142/9789814447133_0006.
• [7] Păun Gh, Rozenberg G, Salomaa A. The Oxford Handbook of Membrane Computing. Oxford University Press, Inc., New York, NY, USA, 2010.
• [8] The P Systems Website. http://ppage.psystems.eu/.
• [9] Cavaliere M, Freund R, Oswald M, Sburlan D. Multiset random context grammars, checkers, and transducers. Theoretical Computer Science, 2007. 372(2-3):136-151. doi:10.1016/j.tcs.2006.11.022.
• [10] Rozenberg G, Salomaa A (eds.). Handbook of Formal Languages, 3 volumes. Springer, Berlin, 1997.
• [11] Salomaa A. Formal Languages. Academic Press, 1973.
• [12] Holt DF, Eick B, O’Brien EA. Handbook of Computational Group Theory. CRC Press, 2005.
• [13] Kudlek M, Martín-Vide C, Păun Gh. Toward a formal macroset theory. In: Calude CS, Păun Gh, Rozenberg G, Salomaa A (eds.), Multiset Processing - Mathematical, Computer Science and Molecular Computing Points of View, volume 2235 of Lecture Notes in Computer Science, pp. 123-134. Springer, 2001. doi:10.1007/3-540-45523-X_7.
• [14] Cook CR, Wang PSP. A Chomsky hierarchy of isotonic array grammars and languages. Computer Graphics and Image Processing, 1978. 8:144-152. doi:10.1016/S0146-664X(78)80022-7.
• [15] Krithivasan K, Siromoney R. Array automata and operations on array languages. Int. Journal of Comp. Math., 1974. 4(1):3-30. doi:10.1080/00207167408803078.
• [16] Rosenfeld A. Picture Languages. Academic Press, Reading, MA, 1979.
• [17] Rosenfeld A, Siromoney R. Picture languages - a survey. Languages of Design, 1993. 1(3):229-245. URL http://dl.acm.org/citation.cfm?id=198440.198442.
• [18] Wang PSP. An application of array grammars to clustering analysis for syntactic patterns. Pattern Recognition, 1984. 17:441-451. doi:10.1016/0031-3203(84)90073-6.
• [19] Freund R, Oswald M. Array automata on Cayley grids. In: Neary T, Cook M(eds.), Proceedings Machines, Computations and Universality 2013, MCU 2013, Zürich, Switzerland, September 9-11, 2013, volume 128 of EPTCS. 2013 pp. 27-28. doi:10.4204/EPTCS.128.
• [20] Freund R, Oswald M. Array grammars and automata on Cayley grids. Journal of Automata, Languages and Combinatorics, 2014. 19(1-4):67-80. doi:10.25596/jalc-2014-067.
• [21] Aizawa K, Nakamura A. Grammars on the hexagonal array. In: Wang PSP (ed.), Array Grammars, Patterns and Recognizers, volume 18 of Series in Computer Science, pp. 144-152.World Scientific, 1989. doi:10.1142/S0218001489000358.
• [22] Freund R, Ivanov S, Oswald M, Subramanian KG. One-dimensional array grammars and P systems with array insertion and deletion rules. In: Neary T, Cook M (eds.), Proceedings Machines, Computations and Universality 2013, MCU 2013, Zürich, Switzerland, September 9-11, 2013, volume 128 of EPTCS. 2013 pp. 62-75. doi:10.4204/EPTCS.128.
• [23] Freund R. A General Framework for Sequential Grammars with Control Mechanisms. In: Hospodár M, Jirásková G, Konstantinidis S (eds.), Descriptional Complexity of Formal Systems. 21st IFIP WG 1.02 International Conference, DCFS 2019, Košice, Slovakia, July 17-19, 2019, Proceedings, volume 11612 of Lecture Notes in Computer Science. Springer, 2019 pp. 1-34.