Word Matrix Rewriting Systems

• Autorzy: Bisht Raj Kishor , Nishida Taishin Yasunobu , Yamamoto Kouhei

Identyfikatory

DOI

10.3233/FI-2019-1800

• Języki publikacji: EN

Abstrakty

EN

We introduce word matrices and word matrix rewriting systems. A word matrix over an alphabet ∑ of k letters is a k × n rectangular matrix with entries of nonnegative integers. A word matrix represents a set of words. The i-th row corresponds to the i-th letter in ∑ (thus the letters in ∑ are ordered as a₁, . . . , a_k). Each column vector represents a set of words which have the vector as the Parikh vector. The word matrix represents the concatenation of all sets represented by column vectors. A word matrix rewriting system consists of a set of rewriting rules which rewrite word matrices and an initial word matrix (the axiom). A word matrix rewriting system generates a set of word matrices by iterated applications of rules to the axiom and generates a language which is the union of all sets represented by the matrices. A word matrix rewriting system is a kind of (restricted) parallel rewriting system with scattered context dependency and hence can generate non-context-free languages, e.g., {aⁿbⁿcⁿ | 1 ≤ n}. We define variants of word matrix rewriting systems and show an infinite hierarchy among them. Some language theoretical problems, including relations among Chomsky hierarchy, closure properties, and decision properties, are considered.

Słowa kluczowe

EN

context-free language; Parikh vectors; regular languages; restricted parallel rewriting

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 166, nr 3
• Strony: 199--226
• Opis fizyczny: Bibliogr. 14 poz., rys., tab.

Twórcy

autor

Bisht Raj Kishor

• Department of Applied Sciences, Amrapali Institute of Technology and Sciences, Lamachaur, Haldwani, (Nainital) Uttarakhand 263139, India

autor

Nishida Taishin Yasunobu

• Department of Information Systems, Toyama Prefectural University, Imizu 939-0398, Japan

autor

Yamamoto Kouhei

• Department of Information Systems, Toyama Prefectural University, Imizu 939-0398, Japan

Bibliografia

• [1] Siromony R, Krithivasan K. Parallel context-free languages. Information and Control, 1974. 24:155-162. doi:10.1016/S0019-9958(74)80054-9.
• [2] Skyum S. Parallel context-free languages. Information and Control, 1974. 26:280-285. doi:10.1016/S0019-9958(74)91399-0.
• [3] Kleijn HCM, Rozenberg G. Context-free like restrictions on selective rewriting. Theoretical Computer Science, 1981. 16:237-269. doi:10.1016/0304-3975(81)90097-9.
• [4] Gonczarowski J, Shamir E. Pattern selector grammars and several parsing algorithms in the context-free style. Journal of Computer and System Sciences, 1985. 30:249-273. doi:10.1016/0022-0000(85)90046-7.
• [5] Dassow J. On some extensions of Russian parallel context-free grammars. Acta Cybernetica, 1984. 6:355-360.
• [6] Moreau P, Ringeissen C, Vittek M. A pattern matching compiler for multiple target languages. In: Hedin G (ed.), Compiler Construction, LNCS 2622, pp. 61-76. Springer-Verlag, Berlin, Heidelberg, 2003. doi:10.1007/3-540-36575-6_5.
• [7] Rozenberg G, Salomaa A (eds.). Handbook of Formal Language, volume 1, 2, 3. Springer-Verlag, Berlin, 1997. doi: 10.1007/978-3-642-59136-5, 10.1007/978-3-662-07675-0, 10.1007/978-3-642-59126-6.
• [8] Narahari Y. Petri nets - overview and foundations. Resonance - Journal of Science Education, 1999. pp. 58-69. URL https://doi.org/10.1007/BF02837068.
• [9] Freund R, Kogler M, Oswald M. A general framework for the regulated rewriting based on the applicability of rules. In: Kelemen J, Kelmenová A (eds.), Computatoin, Cooperation, and Life, LNCS 6610, pp. 35-53. Springer-Verlag, Berlin, Heidelberg, 2011. doi:10.1007/978-3-642-20000-7_5.
• [10] Mayr EW. An algorithm for the general Petri net reachability problem. SIAM Journal of Computing, 1984. 13:441-459. doi:10.1145/800076.802477.
• [11] Lipton R. The reachability problems is exponential-space-hard. Technical Report No. 62, Dept. CS, Yale University, 1976.
• [12] Karp RM, Miller RE. Parallel program schemata. Journal of Computer and System Sciences, 1969. 3:147-195. doi:10.1016/S0022-0000(69)80011-5.
• [13] Rackoff C. The covering and boundedness problem for vector addition systems. Theoretical Computer Science, 1978. 6:223-231. doi:10.1016/0304-3975(78)90036-1.
• [14] Hauschildt D, Jantzen M. Petri net algorithms in the theory of matrix grammars. Acta Informatica, 1994. 31:719-728. doi:10.1007/BF01178731.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).