Languages and scanners (Q1177931)

The new families of languages defined by factors, prefices and suffices of words are introduced. (If \(u\) and \(x\) are two words on the same finite alphabet, then \(x\) is called a factor of \(u\), if \(x\) occurs in \(u\).) For locally testable languages (LT), the membership of a given word in the language is determined by the set of factors of length \(k\) and by the suffices and prefices of length \(<k\); for strongly locally testable languages (SLT) the condition on suffices and prefices is omitted. The number of occurrences of the factor is taken into account in threshold locally testable languages (TLT) and strongly threshold locally testable languages (STLT). The authors give a combinatorial description of these languages and also define them in terms of a special class of finite automata, the scanners. The three classes of languages, \(LT\), \(TLT\), \(SLT\), are characterized by algebraic properties of their syntactic semigroups. The connections with mathematical logic are considered.