An algebraic method for solving decision problems in finite automata theory
Hing Leung · 1987
We study three different decision problems in finite automata theory. Each of the problems had been solved previously using different techniques. We propose a consistent algebraic approach to tackle these problems. (1) A regular set R has the finite power property if R$\sp{*}$ = ($\{\varepsilon\} \cup$ R)$\sp{\rm m}$ for some integer m $\geq$ 1. Is it decidable whether a given regular set has the finite power property? (2) A finite automaton M has finite ambiguity if there is a positive integer k such that, for each accepted string w in the language of M, the number of different accepting paths for w in M is bounded by k. Is it decidable whether a given finite automaton has finite ambiguity? (3) A distance function on a finite automaton M is defined by assigning to each transition a distance of nonnegative integer value. M is said to be limited in distance if$$\vbox{\vskip36pt}$$==>>>is finite. Is it decidable whether a given finite automaton with a distance function is limited in distance? We can formulate these problems using semigroups of matrices. The first two problems would be reduced to asking whether a finitely generated semigroup of matrices is finite or infinite. We obtain simple decision algorithms by applying Brown's theorem on locally finite semigroups. The algorithm for the finite ambiguity problem runs in polynomial time, whereas the algorithm for the finite power property problem runs in polynomial space. It can be easily verified that the finite power property problem is a special case of the limitedness problem. We introduce a topology and reduce the limitedness problem to the problem of finding an algorithm for computing a certain homomorphic image of the topological closure of a finitely generated semigroup of matrices. Using Brown's theorem and Green's relations for analysing the structure of a semigroup, we are able to present a simple algorithm that runs in time 4$\sp{\rm O(n\sp2)}$, where n is the number of states in the finite automaton. In addition, we prove that the problem is PSPACE-hard.