Families of locally testable languages
Kim, McNaughton and McCloskey have produced a polynomial time algorithm in order to test if a deterministic automaton recognizes a locally testable language. We provide a characterization in terms of automata for the strictly locally testable languages and for the strongly locally testable languages, two subclasses of locally testable languages. These two characterizations lead us to polynomial time algorithms for testing these families of languages. (C) 2000 Elsevier Science B.V. All rights reserved.
locally testable languages algorithms automata regular languages