Right and left locally testable languages
The aim of this paper is to give a definition as well as an algebraic characterization of two new varieties of languages that will be referred to as right (respectively left) locally testable languages and denoted as RLT (resp. LLT), Both families strictly contain the class of locally testable languages. Given k>0, the membership of a word x to a RLT (L-RT) language can be decided by means of exploring the prefix and suffix of length k - 1 of s and the segments of length k, as well as considering the order of appearance of those segments when we scan the prefixes of x. Membership of x to a K-LT can be decided in a similar way, but we have to change the word "prefixes" for "suffixes" in the above description. In this paper we also show that S is a syntactic semigroup, of a k-RT (resp. k-LT) language if and only if the local subsemigroups of S are idempotents and right (resp. left) repetition? free. (C) 2000 Elsevier Science B.V. All rights reserved.
local testability semigroups recognizable languages