On two-sided locally testable languages. (English) Zbl 1503.68175
Summary: We extend the two-sided strictly locally testable languages to the two-sided locally testable languages, showing that for each integer \(k \geq 1\) and each symmetric binary relation \(R\) on \(\Sigma^k\), the family \(2LT_R(k)\) of \(k\)-\(R\)-testable languages is obtained as a special kind of Boolean closure of the family of two-sided strictly \(k\)-testable languages. We further study closure and non-closure properties, prove that all two-sided locally testable languages are even linear languages that are learnable in the limit from positive data, and we study decision problems for two-sided locally testable languages.
Keywords:
locally testable language; two-sided locally testable language; even linear language; closure property; decision problem; learnability in the limitReferences:
| [1] | V. Amar,G. R. Putzolu, On a family of linear grammars.Information and Control7 (1964), 283-291. · Zbl 0139.00703 |
| [2] | D. Angluin, Learning regular sets from queries and counterexamples.Information and Computation75(1987), 87-106. · Zbl 0636.68112 |
| [3] | E. M. Gold, Language identification in the limit.Information and Control10(1967), 447-474. · Zbl 0259.68032 |
| [4] | M. Holzer,M. Kutrib,F. Otto, Two-sided strictly locally testable languages. In: R. Freund,F. Mráz,D. Průša(eds.),Non-Classical Models of Automata and Applications (NCMA 2017). Number 329 in books@ocg.at, Austrian Computer Society, Vienna, 2017, 135-150. |
| [5] | M. Holzer,M. Kutrib,F. Otto, Two-sided strictly locally testable languages.Fundamenta Informaticae(2017). Submitted. |
| [6] | T. Jurdziński,K. Loryś, Lower bound technique for length-reducing automata.Information and Computation205(2007), 1387-1412. · Zbl 1127.68051 |
| [7] | M. Kutrib,F. Otto, Two-sided locally testable languages. In:R. Freund, M. Hospodár,G. Jirásková,G. Pighizzini(eds.),Non-Classical Models of Automata and Applications (NCMA 2018). Number 332 in books@ocg.at, Austrian Computer Society, Vienna, 2018, 133-148. |
| [8] | R. Loukanova, Linear context free languages. In:C. B. Jones,Z. Liu,J. Woodcock(eds.),Theoretical Aspects of Computing - ICTAC 2007, 4th International Colloquium, Macau, China, September 26-28, 2007, Proceedings. LNCS 4711, Springer, Heidelberg, 2007, 351-365. · Zbl 1147.68560 |
| [9] | R. McNaughton,P. Narendran,F. Otto, Church-Rosser Thue systems and formal languages.Journal of the ACM35(1988), 324-344. · Zbl 0652.68093 |
| [10] | R. McNaughton,S. Papert,Counter-Free Automata. Number 65 in Research monographs, MIT Press, 1971. |
| [11] | B. Nagy, On 50→30sensing Watson-Crick finite automata. In:M. H. Garzon, H. Yan(eds.),DNA Computing, 13th International Meeting on DNA Computing, DNA13, Memphis, TN, USA, June 4-8, 2007, Revised Selected Papers. LNCS 4848, Springer, 2007, 256-262. · Zbl 1137.68401 |
| [12] | B. Nagy, A class of 2-head finite automata for linear languages.Triangle: Languages, Literature, Computation8(2012), 89-99. |
| [13] | B. Nagy, On a hierarchy of 50→30sensing Watson-Crick finite automata languages. Journal of Logic and Computation23(2013), 855-872. · Zbl 1284.68362 |
| [14] | B. Nagy, A family of two-head pushdown automata. In:R. Freund,M. Holzer, N. Moreira,R. Reis(eds.),Non-Classical Models of Automata and Applications (NCMA 2015). Number 318 in books@ocg.at, Austrian Computer Society, Vienna, 2015, 177-191. |
| [15] | A. L. Rosenberg, A machine realization of the linear context-free languages.Information and Control10(1967), 175-188. · Zbl 0149.24804 |
| [16] | J. M. Sempere,P. García, A characterization of even linear languages and its applications to the learning problem. In:R. C. Carrasco,J. Oncina(eds.),Grammatical Inference and Appliations (ICGI 1994). LNCS 862, Springer, 1994, 38-44. |
| [17] | Y. Takada, Grammatical inference for even linear languages based on control sets. Information Processing Letters28(1988), 193-199. · Zbl 0658.68094 |
| [18] | T. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
