Two-Sided Strictly Locally Testable Languages

Issue title: Non-Classical Models of Automata and Applications IX

Guest editors: Mika Hirvensalo, František Mráz and Daniel Průša

Article type: Research Article

Authors: Holzer, Markus^a | Kutrib, Martin^a | Otto, Friedrich^{b; *}

Affiliations: [a] Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany. holzer@informatik.uni-giessen.de, kutrib@informatik.uni-giessen.de | [b] Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany. f.otto@uni-kassel.de

Correspondence: [*] Address for correspondence: Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany

Abstract: 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.

DOI: 10.3233/FI-2021-2033

Journal: Fundamenta Informaticae, vol. 180, no. 1-2, pp. 29-51, 2021