Paper Info
Title
Piecewise and Local Threshold Testability of DFA
Abstract
The necessary and sufficient conditions for an automaton to be locally threshold testable are found. We introduce the polynomial time algorithm to verify local threshold testability of the automaton of time complexity O(n5) and an algorithm of order O(n3) for the local threshold testability problem for syntactic semigroup of the automaton. We modify necessary and sufficient conditions for piecewise testability problem for deterministic finite automaton and improve the Stern algorithm to verify piecewise testability for the automaton. The time complexity of the algorithm is reduced from O(n5) to O(n2). An algorithm to verify piecewise testability for syntactic semigroup of the automaton of order O(n2) is presented as well.
Year
DOI
Venue
2001
10.1007/3-540-44669-9_33
FCT
Keywords
Field
DocType
sufficient condition,piecewise testability problem,order o,local threshold testability,local threshold testability problem,stern algorithm,syntactic semigroup,polynomial time algorithm,deterministic finite automaton,piecewise testability,time complexity
Testability,Discrete mathematics,Combinatorics,Deterministic automaton,Deterministic finite automaton,Computer science,Algorithm,Finite-state machine,Timed automaton,Time complexity,Piecewise,Probabilistic automaton
Conference
ISBN
Citations 
PageRank 
3-540-42487-3
12
0.88
References 
Authors
12
1
Name
Order
Citations
PageRank
A. N. Trahtman19211.68