Narrow Results

We study reversible deterministic finite automata (REV-DFAs), that are partial deterministic finite automata whose transition function induces an injective mapping on the state set for every letter of the input alphabet. We give a structural characterization of regular languages that can be accepted by REV-DFAs. This characterization is based on the absence of a forbidden pattern in the (minimal) deterministic state graph. Again with a forbidden pattern approach, we also show that the minimality of REV-DFAs among all equivalent REV-DFAs can be decided. Both forbidden pattern characterizations give rise to $NL$-complete decision algorithms. In fact, our techniques allow us to construct the minimal REV-DFA for a given minimal DFA. These considerations lead to asymptotic upper and lower bounds on the conversion from DFAs to REV-DFAs. Thus, almost all problems that concern uniqueness and the size of minimal REV-DFAs are solved.

Reversible forms of computations are often interesting from an energy efficiency point of view. When the computation device in question is an automaton, it is known that the minimal reversible automaton recognizing a given language is not necessarily unique, moreover, there are languages having arbitrarily large reversible recognizers possessing no nontrivial “reversible” congruence. Building atop on our earlier result, we show that the corresponding decision problem is $NL$-complete, and that even in the case when there are only finitely many such reversible recognizers, the largest one among them can be exponentially larger than the minimal automaton. Both results hold for the case of binary alphabets.

We investigate the computational complexity for determining various properties of a finite transformation semigroup given by generators. We introduce a simple framework to describe transformation semigroup properties that are decidable in ${AC}^0$. This framework is then used to show that the problems of deciding whether a transformation semigroup is a group, commutative or a semilattice are in ${AC}^0$. Deciding whether a semigroup has a left (respectively, right) zero is shown to be $NL$-complete, as are the problems of testing whether a transformation semigroup is nilpotent, ${ℛ}$-trivial or has central idempotents. We also give $NL$ algorithms for testing whether a transformation semigroup is idempotent, orthodox, completely regular, Clifford or has commuting idempotents. Some of these algorithms are direct consequences of the more general result that arbitrary fixed semigroup equations can be tested in $NL$. Moreover, we show how to compute left and right identities of a transformation semigroup in polynomial time. Finally, we show that checking whether an element is regular is $PSPACE$-complete.