Paper Info
Title
Optimal estimation on the order of local testability of finite automata
Abstract
A locally testable language L is a language with the property that for some nonnegative integer k , called the order of local testability, whether or not a word u is in the language L depends on (1) the prefix and suffix of the word u of length k−1 and (2) the set of subwords of length k of the word u . For given k the language is called k -testable. We improve the upper bound on the order of local testability of a locally testable deterministic finite automaton with n states to 1 2 (n 2 −n)+1 . This bound is the best possible. We give an answer to the following conjecture of Kim, McNaughton and McCloskey for deterministic finite locally testable automata with n states: “Is the order of local testability no greater than O (n 1.5 ) when the alphabet size is two?” Our answer is negative. In the case of size two the situation is the same as in general case: the order of local testability is Ω (n 2 ) . The necessary and sufficient conditions for the language of an automaton to be k -testable are given in terms of the length of paths of a related graph. Some estimates of the bounds on the order of local testability follow from these results.
Year
DOI
Venue
2000
10.1016/S0304-3975(99)00017-1
Theor. Comput. Sci.
Keywords
DocType
Volume
Locally testable,finite automaton,68Q45,optimal estimation,68Q68,local testability,Language,Semigroup,Finite automaton,20M07,68Q25,Order of local testability
Journal
231
Issue
ISSN
Citations 
1
Theoretical Computer Science
3
PageRank 
References 
Authors
0.56
6
1
Name
Order
Citations
PageRank
A. N. Trahtman19211.68