Morphic Characterizations of Language Families Based on Local and Star Languages

• Autorzy: Okubo F. , Yokomori T.

Identyfikatory

DOI

10.3233/FI-2017-1569

• Języki publikacji: EN

Abstrakty

EN

New morphic characterizations in the form of a noted Chomsky-Schützenberger theorem are established for the classes of regular languages, of context-free languages and of languages accepted by chemical reaction automata. Our results include the following: (i) Each λ-free regular language R can be expressed as R = h(T_k ∩ F_R) for some 2-star language F_R, an extended 2-star language T_k and a weak coding h. (ii) Each λ-free context-free language L can be expressed as L = h(D_n ∩ F_L) for some 2-local language F_L and a projection h. (iii) A language L is accepted by a chemical reaction automaton iff there exist a 2-local language F_L and a weak coding h such that L = h(B_n ∩ F_L), where Dn and Bn are a Dyck set and a partially balanced language defined over the n-letter alphabet, respectively. These characterizations improve or shed new light on the previous results.

Słowa kluczowe

EN

regular languages; context free languages; chemical reaction automata; morphic characterizations; star languages; local languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 323--341
• Opis fizyczny: Bibliogr. 22 poz., rys.

Twórcy

autor

Okubo F.

• Faculty of Arts and Science, Kyushu University, 744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan

autor

Yokomori T.

• Faculty of Education and Integrated Arts and Science, Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku, Tokyo 169-8050 Japan

Bibliografia

• [1] Chomsky N, Schützenberger MP. The algebraic theory of context-free languages, in Studies in Logic and the Foundations of Mathematics, 1963;35:118–161. doi:10.1016/S0049-237X(08)72023-8.
• [2] Greibach SA. The hardest context-free language, SIAM Journal on Computing, 1973;2(4):304–310. URL https://doi.org/10.1137/0202025.
• [3] Fujioka K. Refinement of representation theorems for context-free languages, IEICE Transactions, 2010;E93-D(2): 227–232. URL http://doi.org/10.1587/transinf.E93.D.227.
• [4] Okubo F, Yokomori T. Morphic characterizations of language families in terms of insertion systems and star languages, Intern. J. Found. Comput. Sci., 2011;22(1): 247–260. URL https://doi.org/10.1142/S012905411100799X.
• [5] McNaughton R, Papert S. Counter-Free Automata, The MIT Press, 1971. ISBN:0262130769.
• [6] Latteux M, Turakainen P. A new normal form for the compositions of morphisms and inverse morphisms, Mathematical Systems Theory, 1987;20:261–271. doi:10.1007/BF01692069.
• [7] Pǎun Gh, Pérez-Jiménez MJ, Yokomori T. Representations and characterizations of languages in Chomsky hierarchy by means of insertion-deletion systems, Intern. J. Found. Comput. Sci., 2008;19(4):859–871. URL https://doi.org/10.1142/S0129054108006005.
• [8] Fujioka K. Morphic characterizations of languages in Chomsky hierarchy with insertion and locality, Information and Computation, 2011;209(3): 397–408. URL https://doi.org/10.1016/j.ic.2010.11.011.
• [9] Okubo F, Yokomori T. The computational capability of chemical reaction automata, Natural Computing, 2016;15(2):215–224. doi:10.1007/s11047-015-9504-7.
• [10] Okubo F, Kobayashi S, Yokomori T. Reaction automata, Theoretical Computer Science, 2012;429:247–257. URL https://doi.org/10.1016/j.tcs.2011.12.045.
• [11] Ehrenfeucht A, Rozenberg G. Reaction systems, Fundamenta Informaticae, 2007;75: 263–280. URL http://content.iospress.com/journals/fundamenta-informaticae/145/2.
• [12] Salomaa A. Formal Languages, Academic Press, 1973. URL https://books.google.pl/books?id=aOhQAAAAMAAJ.
• [13] Rozenberg G, Salomaa A (Eds.). Handbook of Formal Languages: Volume 1.Word, Language, Grammar, Springer, 1997. ISBN:3-540-60420-0.
• [14] Hopcroft JE, Motwani T, Ullman JD. Introduction to automata theory, languages and computation - 2nd edition, Addison-Wesley, 2003. ISBN-10:0321210298, 13:9780321210296.
• [15] Calude C, Pǎun G, Rozenberg G, Salomaa A (Eds.): Multiset Processing, LNCS 2235, Springer, Heidelberg, 2001. doi:10.1007/3-540-45523-X.
• [16] Culik K II, Maurer H. On simple representations of language families, R.A.I.R.O. Theoretical Informatics, 1979;13(3):241–250. URL https://doi.org/10.1051/ita/1979130302411.
• [17] Harju T, Karhumäki J, Kleijn HCM. On morphic generation of regular languages, Discrete Applied Mathematics, 1986;15:55–60. URL https://doi.org/10.1016/0166-218X(86)90018-1.
• [18] Peterson JL. Petri Net Theory and the Modeling of System, Prentice-Hall, Englewood Cliffs, 1981. ISBN:0136619835.
• [19] Yokomori T. On purely morphic characterizations of context-free languages, Theoretical Computer Science, 1987;51(3):301–308. URL https://doi.org/10.1016/0304-3975(87)90038-7.
• [20] Karhumäki J, Linna M. A note on morphic characterization of languages, Discrete Applied Mathematics, 1983;5(2):243–246. URL \https://doi.org/10.1016/0166-218X(83)90045-8.
• [21] Salomaa A. Jewels of Formal Language Theory, Computer Science Press, 1981. ISBN-10:0914894692, 13:978-0914894698.
• [22] Yokomori T., Wood D.: An inverse homomorphic characterization full principal AFL, Information Sciences, 1984;33:209–215. URL https://doi.org/10.1016/0020-0255(84)90029-X.