Journal article

Publication year: 2021

Pages: 29-51

Journal: Fundamenta Informaticae

Volume number: 180

Issue number: 1-2

ISSN: 0169-2968

eISSN: 1875-8681

DOI Link: https://doi.org/10.3233/FI-2021-2033

Publisher: SAGE Publications

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.

Harvard Citation style: Holzer, M., Kutrib, M. and Otto, F. (2021) Two-Sided Strictly Locally Testable Languages, Fundamenta Informaticae, 180(1-2), pp. 29-51. https://doi.org/10.3233/FI-2021-2033

APA Citation style: Holzer, M., Kutrib, M., & Otto, F. (2021). Two-Sided Strictly Locally Testable Languages. Fundamenta Informaticae. 180(1-2), 29-51. https://doi.org/10.3233/FI-2021-2033