Parallel decision procedures for finite state automata

Abstract

A new technique is presented for solving, in parallel, the classification problem of finite state automata: given a finite state machine M, is L(M) empty, finite or infinite. This method employs the reachability information implicit in the transition matrix of the automata and hence is effective for both deterministic and nondeterministic finite state machines. Previous approaches required an exponential amount of acceptance testing of long strings. We present a parallel algorithm and combinatorial circuit which requires only O(n) time, where n is the number of states of the automata.

Keywords:

• Combinatorial circuits
• decidable predicates
• finite state automata
• parallel algorithms

C.R. Categories:

• F.1.1
• F1.2
• F4.3
• B6.1