Paper Info
Title
Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order
Abstract
A locally testable language L is a language with the property that for some nonnegative integer k , called the order or the level 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 intermediate substrings of length k of the word u . For given k the language is called k -testable. A finite deterministic automaton is called k -testable if the automaton accepts a k -testable language. In this paper, algorithms to verify 2-testability of order O (n 3 ) , 3-testability of order O (n 4 ) and j -testability for j>3 of order O (n j+1 ) are presented. An O (n n+2 ) time algorithm of finding the precise order of local testability is described. The time complexity of the algorithms improves on the previously known algorithms. We give necessary and sufficient conditions for an automaton to be k -testable in terms of the length of paths of related graphs. Some estimates of the upper and of the lower bound on the order of local testability follow.
Year
DOI
Venue
2000
10.1016/S0304-3975(99)00191-7
Theor. Comput. Sci.
Keywords
DocType
Volume
Locally testable,68Q45,68Q68,local testability,Algorithm,Semigroup,Finite automaton,deterministic finite automaton,20M07,68Q25,Order of local testability
Journal
235
Issue
ISSN
Citations 
1
Theoretical Computer Science
2
PageRank 
References 
Authors
0.40
7
1
Name
Order
Citations
PageRank
A. N. Trahtman19211.68