A condition characterizing the class of regular languages which have several nonisomorphic minimal reversible automata is presented. The condition concerns the structure of the minimum automaton accepting the language under consideration. It is also observed that there exist reduced reversible automata which are not minimal, in the sense that all the automata obtained by merging some of their equivalent states are irreversible. Furthermore, it is proved that if the minimum deterministic automaton accepting a reversible language contains a loop in the “irreversible part” then it is always possible to construct infinitely many reduced reversible automata accepting such a language.
A device is said to be reversible when each configuration has exactly one
predecessor and one successor, thus implying that there is no loss of information
during the computation. On the other hand, as observed by Landauer, logical
irreversibility is associated with physical irreversibility and implies a certain amount
of heat generation [
A lot of work has been done to study reversibility in different computational
devices. Just to give a few examples, in the case of general devices as Turing
machines Bennet proved that each machine can be simulated by a reversible
one [
However, in the case of one-way automata, the situation is different.1 In fact,
as shown by Pin, the regular language a∗b∗ cannot be accepted by any reversible
automaton [
We continue the investigation of minimality in reversible automata and we will refer to the following notions. Let C be the family of reversible automata accepting a given language L and A ∈ C: – The automaton A is reduced in C if every automaton obtained from A by merging some equivalent states does not belong to C. – The automaton A is minimal in C if each automaton in C has at least as many states as A. – The automaton A is the minimum in C if it is the unique (up to isomorphism) minimal automaton in C.
Our first result is a condition that characterizes languages having several different minimal reversible automata. This condition is on the structure of the transition graph of the minimum automaton accepting the language under consideration. As a special case, we show that whenever the “irreversible part” of the minimum automaton contains a loop, it is possible to construct at least two different minimal reversible automata. 1 From now on, we will consider only one-way automata. Hence we will omit to specify “one-way” all the times.
We also observe that there exist reversible automata that are reduced, but
not minimal. Investigating this phenomenon in detail, we were able to find a
language for which there exist arbitrarily large, and hence infinitely many, reduced
reversible automata. Furthermore, we obtained a general construction that allows
to obtain arbitrarily large reversible automata for each language accepted by a
minimum deterministic automaton satisfying the structural condition given in [
Now we introduce a few preliminary notations and notions. A deterministic automaton (d f a) is a tuple A = (Q, Σ, δ, qI , F ) with the usual meaning. We allow the transition function δ to be partial and througthout the paper, we assume that all states are useful, namely they are used to accept some word. This implies that a d f a does not contain any dead state. We denote by δR the reverse transition function that associates with each state r ∈ Q and letter a ∈ Σ the set of states from which r can be reached by reading a, i.e., δR(r, a) = {q ∈ Q | δ(q, a) = r}. A state r is said to be irreversible when there are at least two transitions on the same letter entering r, i.e., #δR(r, a) ≥ 2, otherwise r is reversible. A d f a is said to be reversible (r e v - d f a) when each state is reversible. A language is reversible when there exists a r e v - d f a accepting it.
A d f a A can be split in two parts: the reversible part and the irreversible part. Roughly speaking, the irreversible part consists of all states that can be reached with a path which starts in an irreversible state, and of all transitions connecting those states. The reversible part consists of the remaining states and transitions, namely the states that can be reached from the initial state by visiting only reversible states, and their outgoing transitions.
The above mentioned algorithm [
In this section we present a characterization of the languages having several different minimal reversible automata. From now on, let us fix a reversible language L and the minimum d f a M = (Q, Σ, δ, qI , F ) accepting it.
Theorem 1. The following statements are equivalent: 1. There exists a state q ∈ Q in the irreversible part such that δR(q, a) 6= ∅, δR(q, b) 6= ∅, for two symbols a, b ∈ Σ, with a 6= b. 2. There exist at least two minimal nonisomorphic r e v - d f as accepting L.
As a consequence of Theorem 1 we have the following characterization of reversible languages having a unique minimal (hence a minimum) r e v - d f a:
Corollary 2. There exists a unique (up to isomorphism) minimal r e v - d f a accepting L if and only if for each state p ∈ Q in the irreversible part, all the transitions entering in p are on the same symbol.
We proved that when the minimum d f a accepting a reversible language
contains a loop in the irreversible part the condition in Corollary 2 is always
false, hence there exist at least two minimal nonisomorphic r e v - d f as. As a
consequence, considering Corollary 2, we can observe that when a reversible
language has a unique minimal r e v - d f a, all the loops in the minimum d f a
accepting it should be in the reversible part. However, the converse does not hold,
namely there are languages whose minimum d f a does not contain any loop in
the irreversible part, which does not have a unique minimal r e v - d f a. Indeed,
in [
In this section, we consider reduced r e v - d f as. There exist r e v - d f as which are reduced but not minimal. Furthermore, there exist reversible languages having arbitrarly large reduced r e v - d f as and, hence, infinitely many reduced r e v d f as.
In Figure 2 a reduced r e v - d f a equivalent to the d f as in Figure 1 is depicted. If we try to merge two states in the loop, then the loop collapses to a single state, so producing the minimum d f a, which is irreversible. Actually, this example can be modified by using a loop of N states: if (and only if) N is prime, we get a reduced automaton. This is a special case of the construction we obtained to prove the following: Theorem 3. If M contains a state q in the irreversible part such that the language accepted by computations starting from q is infinite, then there exist infinitely many nonisomorphic reduced r e v - d f as accepting L.
The condition in Theorem 3 is not necessary. In fact, we found an example where the minimum d f a does not contain any loop in the irreversible part, but it is possible to construct infinitely many equivalent reduced r e v - d f as.