CIAA2003

START ConferenceManager

Reducing the time complexity of testing of local threshold testability

A.N. Trahtman

Presented at Eighth International Conference on Implementation and Application of Automata (CIAA 2003), July 16-18, 2003 Santa Barbara, CA, USA

Abstract

New necessary and sufficient conditions for an DFA to be locally threshold testable are found. On the basis of these conditions, we modify an algorithm to check local threshold testability and reduce the time complexity. The algorithm is implemented in package TESTAS.