A package TESTAS for checking some kinds of testability

2021/05/26 by A. N. Trahtman, Trahtman, A. N.
Computer Science · #68w25 68Q25 05C85 #F.2.2 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #I.2.7 #acm:05C85 #acm:68Q25 #acm:68w25 #cs.FL #msc:05C85 #msc:68Q25 #msc:68w25

paper · pdf · doi:10.48550/arxiv.2105.12583

5 pages, Lecture Notes in Computer Science 2608(2003), 228-232

arxiv created 2021/05/26 · arxiv updated 2021/05/27

Abstract

We implement a set of procedures for deciding whether or not a language given by its minimal automaton or by its syntactic semigroup is locally testable, right or left locally testable, threshold locally testable, strictly locally testable, or piecewise testable. The bounds on order of local testability of transition graph and order of local testability of transition semigroup are also found. For given k, the k-testability of transition graph is verified. Some new effective polynomial time algorithms are used. These algorithms have been implemented as a C/C++ package.

Related

• Polynomial time algorithm for left [right] local testability
• Reducing the time complexity of testing for local threshold testability
• An algorithm to verify local threshold testability of deterministic finite automata
• Precise estimation on the order of local testability of deterministic finite automaton
• On k-piecewise testability (preliminary report)