Affiliations: [a] Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany. [email protected], [email protected] | [b] Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany. [email protected]
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.
