Two-Sided Strictly Locally Testable Languages

• Autorzy: Holzer Markus , Kutrib Martin , Otto Friedrich

Identyfikatory

DOI

10.3233/FI-2021-2033

• Języki publikacji: EN

Abstrakty

EN

A two-sided extension of strictly locally testable languages is presented. In order to determine membership within a two-sided strictly locally testable language, the input must be scanned from both ends simultaneously, whereby it is synchronously checked that the factors read are correlated with respect to a given binary relation. The class of two-sided strictly locally testable languages is shown to be a proper subclass of the even linear languages that is incomparable to the regular languages with respect to inclusion. Furthermore, closure properties of the class of two-sided strictly locally testable languages and decision problems are studied. Finally, it is shown that two-sided strictly k-testable languages are learnable in the limit from positive data.

Słowa kluczowe

EN

statistical decision making; language

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 180, nr 1-2
• Strony: 29--51
• Opis fizyczny: Bibliogr. 23 poz., rys., tab.

Twórcy

autor

Holzer Markus

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

autor

Kutrib Martin

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

autor

Otto Friedrich

• Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany

Bibliografia

• [1] Chomsky N, Schützenberger M. The algebraic theory of context-free languages. In: Brafford P, Hirschberg D (eds.), Computer Programming and Formal Systems, volume 26 of Studies in Logic and the Foundations of Mathematics, Elsevier, Amsterdam, 1963. 35:118-161. doi:10.1016/S0049-237X(08)72023-8.
• [2] Berstel J, Pin JE. Local languages and the Berry-Sethi algorithm. Theor. Comput. Sci., 1996. 155(2):439-446. doi:10.1016/0304-3975(95)00104-2.
• [3] Caron P. Families of locally testable languages. Theor. Comput. Sci., 2000. 242(1-2):361-376. doi:10.1016/S0304-3975(98)00332-6.
• [4] Eilenberg S. Automata, Languages and Machines, volume A. Academic Press, New York, 1974.
• [5] Brauer W. Automatentheorie: Eine Einführung in die Theorie endlicher Automaten. Leitfäden und Monographien der Informatik. Teubner, 1984. (in German). doi:10.1007/978-3-322-92151-2.
• [6] Lawson M. Finite Automata. CRC Press, 2005.
• [7] McNaughton R, Papert S. Counter-free automata. Number 65 in Research monographs. MIT Press, 1971. ISBN-10:0262130769, 13:978-0262130769.
• [8] Rosenberg A. A Machine Realization of the Linear Context-Free Languages. Inform. Control, 1967. 10:175-188. doi:10.1016/S0019-9958(67)80006-8.
• [9] Loukanova R. Linear context free languages. In: Jones C, Liu Z, Woodcock J (eds.), “International Colloquium on Theoretical Aspects of Computing (ICTAC 2007)”. Proc., volume 4711 of LNCS, pp. 351-365. Springer, Heidelberg, 2007. doi:10.1007/978-3-540-75292-9_24.
• [10] Nagy B. A family of two-head pushdown automata. In: Freund R, Holzer M, Moreira N, Reis R (eds.), Non-Classical Models of Automata and Applications (NCMA 2015), Proc., volume 318 of [e-mail], pp. 177-191. Austrian Computer Society, 2015.
• [11] Zalcstein Y. Locally Testable Languages. J. Comput. System Sci., 1972. 6:151-167. doi:10.1016/S0022-0000(72)80020-5.
• [12] McNaughton R, Narendran P, Otto F. Church-Rosser Thue Systems and Formal Languages. Journal of the ACM, 1988. 35:324-344.
• [13] Amar V, Putzolu G. On a family of linear grammars. Inform. Control, 1964. 7(3):283-291. doi:10.1016/S0019-9958(64)90294-3.
• [14] Gold E. Language identification in the limit. Inform. Control, 1967. 10(5):447-474. doi:10.1016/S0019-9958(67)91165-5.
• [15] Luca AD, Restivo A. A characterization of strictly locally testable languages and its application to subsemigroups of a free semigroup. Inform. Control, 1980. 44(3):300-319. doi:10.1016/S0019-9958(80)90180-1.
• [16] Yokomori T, Kobayashi S. Learning local languages and their application to DNA sequence analysis. IEEE Trans. Pattern Anal. Mach. Intell., 1998. 20:1067-1079. doi:10.1109/34.722617.
• [17] Jurdziński T, Loryś K. Lower bound technique for length-reducing automata. Inform. Comput., 2007. 205(9):1387-1412. doi:10.1016/j.ic.2007.02.003.
• [18] Niemann G, Otto F. The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. Inform. Comput., 2005. 197(1-2):1-21. doi:10.1016/j.ic.2004.09.003.
• [19] Dahlhaus E, Warmuth M. Membership for growing context-sensitive grammars is polynomial. J. Comput. System Sci., 1986. 33(3):456-472. doi:10.1016/0022-0000(86)90062-0.
• [20] Hopcroft J, Ullman J. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979. ISBN-13:978-0201029888, 10:020102988X.
• [21] Angluin D. Learning regular sets from queries and counter-examples. Inform. Comput., 1987. 75(2):87-106. doi:10.1016/0890-5401(87)90052-6.
• [22] Sempere J, García P. A characterization of even linear languages and its applications to the learning problem. In: International Colloquium on Grammatical Inference and Applications (ICGI 1994), Proc., volume 862 of LNCS, pp. 38-44. Springer, 1994. doi:10.1007/3-540-58473-0_135.
• [23] Takata Y. Grammatical inference for even linear languages based on control sets. Inform. Proc. Letters, 1988. 28(4):193-199. doi:10.1016/0020-0190(88)90208-6.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).