Bruno Guillon
email: bruno.guillon@uca.fr

Giovanna J Lavado
email: lavado@di.unimi.it

Giovanni Pighizzini
email: pighizzini@di.unimi.it§prigioniero@di.unimi.it

Luca Prigioniero

Weakly and Strongly Irreversible Regular Languages

Keywords: Finite automata, reversibility, descriptional complexity

Finite automata whose computations can be reversed, at any point, by knowing the last k symbols read from the input, for a fixed k, are considered. These devices and their accepted languages are called k-reversible automata and k-reversible languages, respectively. The existence of k-reversible languages which are not (k -1)-reversible is known, for each k > 1. This gives an infinite hierarchy of weakly irreversible languages, i.e., languages which are k-reversible for some k. Conditions characterizing the class of kreversible languages, for each fixed k, and the class of weakly irreversible languages are obtained. From these conditions, a procedure that given a finite automaton decides if the accepted language is weakly or strongly (i.e., not weakly) irreversible is described. Furthermore, a construction which allows to transform any finite automaton which is not k-reversible, but which accepts a k-reversible language, into an equivalent k-reversible finite automaton, is presented.

Introduction

The principle of reversibility, which is fundamental in thermodynamics, has been widely investigated for computational devices. The first works on this topic already appeared half a century ago and are due to Landauer and Bennet [START_REF] Bennett | Logical reversibility of computation[END_REF][START_REF] Landauer | Irreversibility and heat generation in the computing process[END_REF]. More recently, several papers presenting investigations on reversibility in space bounded March 26, 2022 20:59 112-IJFCS 2241005

Weakly and Strongly Irreversible Regular Languages 3 language which is k-reversible but not (k -1)-reversible. Here we prove that there are regular languages which are not k-reversible for any k. Such languages are called strongly irreversible, in contrast with the other regular languages which are called weakly irreversible.

As in the case of "standard" reversibility (or 1-reversibility), we provide an automata characterization of the classes of weakly and strongly irreversible languages. Indeed, generalizing the notion of forbidden pattern presented in [START_REF] Holzer | Minimal reversible deterministic finite automata[END_REF], we show that a language is k-reversible if and only if the minimum automaton accepting it does not contain a certain k-forbidden pattern. We also give a construction to transform each automaton which does not contain the k-forbidden pattern, into an equivalent automaton which is k-reversible. Furthermore, using a pumping argument, we prove that if an n-state automaton contains an N -forbidden pattern, for a constant N = O(n 2 ), then it contains a k-forbidden pattern for each k > 0 or equivalently, a certain strong forbidden pattern. Hence, applying this condition to the minimum automaton accepting a language L, we are able to decide if L is weakly or strongly irreversible. We finally present a decision procedure for such problem.

We point out that, according to the approach in [START_REF] Holzer | Minimal reversible deterministic finite automata[END_REF], in this paper we refer to the classical model of deterministic automata, namely automata with a unique initial state, a set of final states and deterministic transitions. Different approaches have been considered in the literature. The notion of reversibility in [START_REF] Angluin | Inference of reversible languages[END_REF] is introduced by considering deterministic devices with one initial state and one final state, while automata with a set of initial states, a set of final states and deterministic transitions have been considered in [START_REF] Pin | On reversible automata[END_REF]. In particular, the notion of reversibility in [START_REF] Angluin | Inference of reversible languages[END_REF] is more restrictive than the one studied in [START_REF] Holzer | Minimal reversible deterministic finite automata[END_REF] and in this paper. Hence, also the notion of kreversibility, introduced and studied here, is different from a notion of k-reversibility studied in [START_REF] Angluin | Inference of reversible languages[END_REF].

Outline. The paper is organized as follows. In Sec. 2, we recall the basic definitions and we introduce the main concepts under consideration (mainly, the notions of k-reversibility, weak and strong irreversibility). In Sec. 3, we prove our main result which characterizes the class of k-reversible languages, for each positive integer k, by using the notion of k-forbidden pattern. To prove this characterization, in Sec. 3.1 we present a construction to transform an automaton into an equivalent k-reversible one, when this is possible. The above-mentioned characterization is then extended to weakly irreversible languages (i.e., k-reversible languages, for some k) in Sec. 4. In Sec. 5 we consider the degree of irreversibility on both automata and their accepted languages, and we show the existence of arbitrarily large (and even infinite) gaps between these degrees. In Sec. 6, we discuss and we present a decision procedure that allows to check whether a minimum automaton accepts a weakly or a strongly irreversible language. The same procedure also allows to compute the degree of irreversibility of a language. We prove the NL-completeness of such decision problem. Finally, we make concluding comments in Sec. 7.

Preliminaries

Automata, words and languages

In this section we recall some basic definitions and results useful in the paper. For more details on automata and formal languages, we refer the reader to a standard textbook as, e.g., [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF].

Given a set S, let us denote by #S its cardinality, by 2 S the family of all its subsets, and by S <k (S k , respectively), for a fixed integer k ≥ 0, the set of sequences of less than (exactly, resp.) k elements from S, where ε is the empty sequence. Given an alphabet Σ, |w| denotes the length of a string w ∈ Σ * .

A deterministic finite automaton (dfa) is a tuple A = (Q, Σ, δ, q I , F ), where Q is the finite set of states, Σ is the input alphabet, q I ∈ Q is the initial state, F ⊆ Q is the set of final states, and δ : Q × Σ → Q is the partial transition function, that can be extended, in the usual way, as a function δ : Q × Σ * → Q applying to strings. We say that two states p, q ∈ Q are equivalent if and only if for all w ∈ Σ * , δ(p, w) ∈ F exactly when δ(q, w) ∈ F . Let A = (Q, Σ, δ, q I , F ) be a dfa. A state p ∈ Q is useful if it is reachable, i.e., there exists w ∈ Σ * such that δ(q I , w) = p, and productive, i.e., if there is w ∈ Σ * such that δ(p, w) ∈ F . In this paper we only consider dfas in which all the states are useful.

Nondeterministic finite automata (nfas) are defined by extending the transition function to δ : Q × Σ → 2 Q and by admitting several initial states (the initial state component is replaced by a subset I ⊆ Q of initial states). In this way, an nfa can reach multiple states at the same time.

The language accepted by a dfa or an nfa A is defined in the classical way as the set L(A) of all strings that define a path from one initial state to one of the final states. Two automata A and A ′ are said to be equivalent if they accept the same language, i.e., if L(A) = L(A ′ ).

A strongly connected component (scc) C of an nfa or a dfa A is a maximal subset of Q such that, for every two states p and q of C, there exists a path from p to q and a path from q to p in the transition graph of A. Let us denote by C q the scc containing the state q ∈ Q. We consider the partial order ⪯ on the set of sccs of A, defined by

C 1 ⪯ C 2 when a state in C 2 is reachable from a state in C 1 . We write C 1 ≺ C 2 when C 1 ⪯ C 2 and C 1 ̸ = C 2 .

Reversibility

In this section we introduce the main notions we consider in this paper, by defining different degree of reversibility of automata or of languages.

Given a dfa A = (Q, Σ, δ, q I , F ), the reverse transition function of A is the function δ

r : Q × Σ → 2 Q such that δ r (p, a) = {q ∈ Q | δ(q, a) = p}.
The reverse automaton of A is the nfa A r = (Q, Σ, δ r , F, {q I }) obtained by reversing the transition function δ and in which the set of initial states coincides with the set of final states of A and the unique final state is q I . A state r ∈ Q is said to be irreversible when #δ r (r, a) > 1 for some a ∈ Σ, i.e., there are at least two transitions on the same letter entering r, otherwise r is said to be reversible. The dfa A is said to be irreversible if it contains at least one irreversible state, otherwise A is reversible (rev-dfa). As pointed out in [START_REF] Kutrib | Reversible and irreversible computations of deterministic finite-state devices[END_REF], the notion of reversibility for a language is related to the computational model under consideration. In this paper we only consider dfas. Hence, by saying that a language L is reversible, we refer to this model, namely we mean that there exists a rev-dfa accepting L. The class of reversible languages is denoted by rev.

We now relax the notion of reversibility, by allowing irreversibility whenever it can be resolved by accessing to a suffix of fixed length of the portion of the input read so far. This yields the notions of k-reversibility and weak-irreversibility. Definition 1. Let k be a positive integer, A = (Q, Σ, δ, q I , F ) be a dfa, and L ⊆ Σ * be a regular language.

• A state r ∈ Q is k-irreversible if there exist two states p and q in Q, a string x ∈ Σ k-1 and a symbol σ ∈ Σ, such that δ(p, x) ̸ = δ(q, x) and δ(p, xσ) = δ(q, xσ) = r, as depicted here:

p ̸ = r q x σ x σ
Otherwise, r is k-reversible. • The automaton A is k-reversible if each of its states is k-reversible.

• The language L is k-reversible if it is accepted by a k-reversible dfa.

• The language L is weakly irreversible if it is k-reversible for some k > 0.

By definition, a state r is 1-reversible if and only if it is reversible. As a consequence, 1-reversibility (of automata or of languages) coincides with reversibility.

In the case of a k-reversible state r, with k > 1, we could have more than one transition on the same symbol σ entering r. However, by knowing the suffix of length k of the part of the input already inspected, i.e., a suffix xσ with |x| = k -1, we can uniquely identify which transition on σ has been used to enter r in the current computation. In other terms, while a reversible automaton is a device which is able to move the computation one state back, by knowing the last symbol that has been read, a k-reversible automaton can do the same, having access to the suffix of length k of the part of the input already inspected (when the length of that part is less than k, the automaton can see all the input inspected so far).

Let us denote by rev k the class of k-reversible languages. As observed previously, rev = rev 1 . Furthermore k-reversible dfas are denoted rev k dfas, for short. From Definition 1, we can immediately prove the following facts: Remark 2. If a state (resp., an automaton or a language) is k-reversible for some positive integer k, then it is k ′ -reversible for every k ′ ≥ k.

q I q 1 q k-1 q k a b b b
As observed by Pin, not all regular languages are reversible [START_REF] Pin | On reversible automata[END_REF]. This result extends to k-reversibility for each k > 0 [START_REF] Kutrib | Degrees of reversibility for DFA and DPDA[END_REF]. In particular there exists an infinite hierarchy of languages, with respect to k-reversibility, as described in the next example.

Example 3 (introduced in [START_REF] Kutrib | Degrees of reversibility for DFA and DPDA[END_REF]). For each integer k > 0, consider the language L k = a * b k b * , which is accepted by the minimum automaton depicted in Fig. 1. The only irreversible state is q k . Suppose that, after reading a string w, the automaton is in q k . If we know a suffix of w of length i, with i ≤ k, (this suffix can only be b i ) then we cannot determine the previous state in the computation, namely, the state entered before reading the last symbol of w. In fact, this state could be either q k-1 or q k . Hence, the automaton is not k-reversible. However, if we know the suffix of length k + 1, then it could be either b k+1 , and in this case the previous state is q k , or ab k , and in this case the previous state is q k-1 . It could be also possible that only k input symbols have been read, i.e., |w| = k. In that case, all w = b k can be seen back and the previous state is q k-1 . Hence, the automaton is (k + 1)-reversible. As shown in [START_REF] Kutrib | Degrees of reversibility for DFA and DPDA[END_REF]Theorem 4] we cannot do better for this language, i.e., L k ∈ rev k+1 \ rev k . This can be also obtained as a consequence of results in Sec. 5.

As a consequence of Remark 2 and Example 3, we have the proper infinite hierarchy of classes:

rev = rev 1 ⊂ rev 2 ⊂ . . . ⊂ rev k ⊂ . . . .

Characterization of k-reversible languages

In [START_REF] Holzer | Minimal reversible deterministic finite automata[END_REF], the authors proved that a regular language is irreversible if and only if the minimum dfa accepting it contains a forbidden pattern, which consists of two different transitions on the same letter entering in the same state r, where one of them arrives from a state p which belongs to the same strongly connected component of r (see Fig. 2(a)).

We now refine this definition in order to consider strings of the same length that lead to the same state. Definition 4. Given a dfa A = (Q, Σ, δ, q I , F ) and an integer k > 0, the kforbidden pattern is formed by three states p, q, r ∈ Q, with a symbol σ ∈ Σ, two strings x ∈ Σ k-1 and w ∈ Σ * , such that δ(p, x) ̸ = δ(q, x), δ(p, xσ) = δ(q, xσ) = r, and δ(r, w) = q (see Fig. 2(b)).

Without the condition δ(r, w) = q, the definition says exactly that r is a kirreversible state (see first item of Definition 1). With the additional condition, we require that one of the state that "witnesses" the k-irreversibility of r (named q) belongs to same strongly connected component as r, namely C q = C r .

From Definition 4, we can observe that if a dfa A contains a k-forbidden pattern, for some k > 0, then it contains a k ′ -forbidden pattern for each integer k ′ ≤ k.

We will use the notion of k-forbidden pattern to obtain a characterization of the class rev k . In fact, we will prove that a regular language is k-reversible if and only if the minimum dfa accepting it does not contain the k-forbidden pattern. In Sec. 3.1, we present an algorithm that transforms any dfa in which does not occur the k-forbidden pattern into an equivalent k-reversible dfa, while in Sec. 3.2, we show that the absence of the k-forbidden pattern in the minimum dfa is a necessary condition for the accepted language to be k-reversible.

k-reversible simulation

In this section we present a construction to build, given a dfa A = (Q, Σ, δ, q I , F ) and an integer k > 0, an equivalent dfa

A ′ = (Q ′ , Σ, δ ′ , s I , F ′ ), which is k-reversible if A does not contain the k-forbidden pattern.
Let us start by presenting an informal outline of the construction. First of all, we discuss the case k = 1, namely the case of "standard" reversibility.

If A does not contain the 1-forbidden pattern, to make it reversible we can extend its control to remember the sequence of the states from which, during the computation, irreversible transitions have been executed, i.e., all states q ∈ Q such that A executed a transition on a symbol σ from q to a state r with #δ r (r, σ) > 1.

With the information saved in this sequence and looking at the previous input symbol, the automaton is able to reverse its computation. Since A does not contain the 1-forbidden pattern, each time it executes an irreversible transition, it moves from an scc to a different one. This implies that the length of the sequence saved in the control is bounded. Actually, our construction will be slightly redundant: each time A will move from a state q in an scc to a state in a different scc we will add q to the sequence, even if the used transition is not irreversible.

The case k > 1 is more complicated. Since an irreversible state r could also be entered by an irreversible transition arriving from a state in the scc C r , the previous technique would require to remember arbitrarily long sequences of states. We proceed in a different way, still using the previous technique, after the preliminary change in the automaton A that we now illustrate.

For any k-irreversible state r we have the situation in the following picture, for some p 0 , p, q 0 , q ∈ Q, a ∈ Σ, x ∈ Σ k-1 :

p 0 p ̸ = r q 0 q x a x a
Since A does not contain the k-forbidden pattern, the states p 0 and q 0 cannot belong to C r . Hence, along each path from p 0 and q 0 to r on xa, there is a transition which, from another scc, enters C r . In order to know where those transitions are located, we introduce a counter modulo k in the finite control of A. In the initial configuration the counter contains 0. It is incremented by 1 during the execution of each transition that does not change scc, while it is set to 0 when the transition reaches a different scc. In this way, if the state r is reached with 0 in the counter, then both transitions from p and q should arrive from sccs different than C r (otherwise, due to the increment policy of the counter, either p 0 or q 0 should be in C r ). In a similar way, if the counter contains a value ℓ, 0 < ℓ < k, in both paths the transition entering the component C r is the one reading the symbol which precedes the suffix of length ℓ of xa, i.e., the one entering the configuration with 0 in the counter. In this way, if the automaton is in the state r with ℓ in the counter, and it knows the suffix xa of length k of the input read so far and the state which was reached immediately before entering C r , then it can decide if the state before entering r was p or q and, so, it can reverse the last computation step.

Using these ideas, we now define the dfa A ′ . The finite control stores three elements:

• The current state q of A.

• An integer j ∈ {0, . . . , k -1} which is used to count modulo k the visits to states in the current scc of A, namely in the scc C q . • A sequence of pairs from Q × {0, . . . , k -1}. This is the sequence of the first two components of the states in Q ′ which have been reached before simulating a transition that in A changes scc. Since the number of possible sccs is bounded by #Q, we consider sequences of length less than #Q. It is convenient to view these sequences as words over the alphabet Q × {0, . . . , k -1}, using the symbol • to denote concatenation.

Formally, we give the following definition:

• Q ′ = Q × {0, . . . , k -1} × (Q × {0, . . . , k -1}) <#Q ; • for ⟨q, j, α⟩ ∈ Q ′ , if δ(q, a) = p then δ ′ (⟨q, j, α⟩, a) = ⟨p, (j + 1) mod k, α⟩ if C p = C q ⟨p, 0, α • (q, j)⟩ otherwise,
while δ ′ (⟨q, j, α⟩, a) is left undefined when δ(q, a) is not defined;

• s I = ⟨q I , 0, ε⟩ is the initial state; • F ′ = F × {0, . . . , k -1} × (Q × {0, . . . , k -1}) <#Q is the set of final states.
Notice that by dropping the second and the third components off the states of A ′ , we get exactly the automaton A. Hence, A and A ′ are equivalent. Furthermore, if δ ′ (⟨p, h, α⟩, a) = ⟨r, ℓ, γ⟩ for some a ∈ Σ and ⟨p, h, α⟩, ⟨r, ℓ, γ⟩ ∈ Q ′ with 0 < ℓ < k, then the states p and r are in the same scc of A and h = ℓ -1. This fact will be used in the following proof of the main property of A ′ .

Lemma 5. If A does not contain the k-forbidden pattern, then A ′ is k-reversible.

Proof. Assume that A does not contain the k-forbidden pattern and, by contradiction, suppose that A ′ contains a k-irreversible state ⟨r, ℓ, γ⟩ ∈ Q ′ . Then there exist a string x ∈ Σ k-1 , a symbol a ∈ Σ and four states ⟨p 0 , h 0 , α 0 ⟩, ⟨p, h, α⟩, ⟨q 0 , j 0 β 0 ⟩ and ⟨q, j, β⟩ in Q ′ , such that x defines a path from state ⟨p 0 , h 0 , α 0 ⟩ (resp., ⟨q 0 , j 0 , β 0 ⟩) to state ⟨p, h, α⟩ (resp., ⟨q, j, β⟩), there are transitions on a from both states ⟨p, h, α⟩ and ⟨q, j, β⟩ to state ⟨r, ℓ, γ⟩, and ⟨p, h, α⟩ ̸ = ⟨q, j, β⟩. The situation is summarized in the following picture:

⟨p 0 , h 0 , α 0 ⟩ ⟨p, h, α⟩ ̸ = ⟨r, ℓ, γ⟩ ⟨q 0 , j 0 , β 0 ⟩ ⟨q, j, β⟩ x a x a
First, suppose ℓ = 0. We divide the proof in the following cases:

Case α = β = γ.
From the definition of δ ′ , C p = C q = C r . Furthermore h = j = k -1. Hence p ̸ = q. Since |x| = k -1, in the states of A ′ along the path from ⟨q 0 , j 0 , β 0 ⟩ on x, the second component is 0 only at the beginning of the path. This implies that C q0 = C q = C r . Hence, the automaton A should contain the k-forbidden pattern. Case α ̸ = γ and β = γ (and, symmetrically, Case α = γ and β ̸ = γ).

In this case C q = C r , while C p ̸ = C r , which gives p ̸ = q. By the same argument as in the previous case, we obtain C q0 = C q = C r . So, A should contain the k-forbidden pattern.

Case α ̸ = γ and β ̸ = γ.

In this case

C p ̸ = C r , C q ̸ = C r , and γ = α • (p, h) = β • (q, j).
Hence, α = β, p = q, and h = j, which contradicts the hypothesis ⟨p, h, α⟩ ̸ = ⟨q, j, β⟩.

To complete the proof, we are now going to prove that in the case ℓ > 0 we always obtain a contradiction. By the definition of δ ′ , h = j = ℓ -1 and α = β = γ. Hence p ̸ = q. We decompose x as x ′ bx ′′ , where

x ′ , x ′′ ∈ Σ * , b ∈ Σ, |x ′ | = k -ℓ -1, and |x ′′ | = ℓ -1. Then, for suitable ⟨p 1 , h 1 , α 1 ⟩, ⟨q 1 , j 1 , β 1 ⟩ ∈ Q ′ , p 2 , q 2 ∈ Q, we have the following situation: ⟨p 0 , h 0 , α 0 ⟩ ⟨p 1 , h 1 , α 1 ⟩ ⟨p 2 , 0, γ⟩ ⟨p, ℓ -1, γ⟩ ⟨r, ℓ, γ⟩ ⟨q 0 , j 0 , β 0 ⟩ ⟨q 1 , j 1 , β 1 ⟩ ⟨q 2 , 0, γ⟩ ⟨q, ℓ -1, γ⟩ x ′ b x ′′ a x ′ b x ′′ a
Notice that in the two paths on the string x from ⟨p 0 , h 0 , α 0 ⟩ to ⟨p, ℓ -1, γ⟩ and from ⟨q 0 , j 0 , β 0 ⟩ to ⟨q, ℓ -1, γ⟩, the last transitions that could change scc in A are those on the symbol b, immediately after the prefix x ′ . Suppose that one of these transitions does not change scc in A, without loss of generality the one from ⟨q 1 , j 1 , β 1 ⟩ to ⟨q 2 , 0, γ⟩. Then, by the definition of δ ′ , j 1 = k -1, and, since |x ′ | < k, none of the second components of the states on the path from ⟨q 0 , j 0 , β 0 ⟩ to ⟨q 1 , j 1 , β 1 ⟩ on x ′ can be 0. This implies that

C q0 = C q1 = C q2 = C q = C r .
Therefore, A should contain the k-forbidden pattern, which is a contradiction. Thus, in A both transitions on b from p 1 to p 2 and from q 1 to q 2 should change scc. Considering the corresponding transitions in the two paths under consideration, we get that γ = α 1 • (p 1 , h 1 ) = β 1 • (q 1 , j 1 ) and, hence,

p 1 = q 1 .
Since A is deterministic, this implies p 2 = q 2 and, finally, p = q, namely another contradiction.

We now evaluate the size of the automaton obtained by using the previous construction.

Theorem 6. Each n-state dfa which does not contain the k-forbidden pattern can be simulated by an equivalent k-reversible dfa with no more than (k + 1) n-1 states.

Proof. Let A be an n-state dfa not containing the k-forbidden pattern. According to Lemma 5, the automaton A ′ obtained from A with the above presented construction is k-reversible. We now estimate the number of its reachable states.

First, notice that if a state ⟨q, ℓ, α⟩ with α = (p 1 , j 1 )(p 2 , j 2 ) appearing in α (i.e., the letters of α) is given by the ordering of sccs in A, we could represent α as a set. This also allows to interpret the state ⟨q, ℓ, α⟩ as the function

• • • (p h , j h ) is reach- able, then C p1 ≺ C p2 ≺ . . . ≺ C p h ≺ C q . Hence,
f : Q → {-, 0, 1, . . . , k -1}, such that for r ∈ Q: f (r) =      ℓ if r = q, j i if r = p i , 1 ≤ i ≤ h, -otherwise.
By counting the number of possible functions, we obtain a (k + 1) n upper bound for the number of reachable states in A ′ . Now, we show how to reduce this bound to the one claimed in the statement of the theorem. The above presented simulation can be slightly refined by observing that in A all the transitions entering any state in the scc of the initial state q I can arrive only from states in the same scc. Thus, if some state in C q I is k-irreversible, then A should contain the k-forbidden pattern, which is a contradiction. This allows to directly simulate all the states in C q I , without using the counter. As a consequence, in each state ⟨q, ℓ, α⟩ of Q ′ , with q / ∈ C q I , the first element of α, which should represent a state in C q I , is stored without the counter. Hence, such a state can be seen as a pair whose first component is a state in C q I (the first element of α) and the second component is the above function f restricted to the set Q\C q I (representing both the current state q with its counter ℓ and the other pairs in α). Since f (q) = ℓ ∈ {0, . . . , k -1}, f cannot be the constant function f (r) =for r ∈ Q\C q I . Hence, the number of possible functions is bounded by (k +1) n-s -1, where s = #C q I . Considering also the states which are used in Q ′ to simulate the states in C q I , this gives at most s+s((k+1) n-s -1) many reachable states. For k > 0 this amount is bounded by (k + 1) n-1 .

We point out that for k = 1, Theorem 6 gives a 2 n-1 upper bound, which matches with the bound for the conversion of dfas into equivalent rev-dfas, claimed in [START_REF] Holzer | Minimal reversible deterministic finite automata[END_REF]. In the same paper, a lower bound very close to such an upper bound was presented.

The characterization

In this section, we present a characterization of k-reversible languages based on the notion of k-forbidden pattern. This characterization will be obtained by combining Theorem 6 with the following result. Lemma 7. Let L be a regular language and k be a positive integer. If the minimum dfa accepting L contains the k-forbidden pattern, then L / ∈ rev k .

Proof. Let M = (Q, Σ, δ, q I , F ) be the minimum dfa accepting L. By hypothesis there exist three states p, q, r ∈ Q, a symbol σ ∈ Σ, and two strings x ∈ Σ k-1 and w ∈ Σ * such that δ(p, x) ̸ = δ(q, x), δ(p, xσ) = δ(q, xσ) = r and δ(r, w) = q (see Fig. 2(b)). Let A ′ = (Q ′ , Σ, δ ′ , s I , F ′ ) be a dfa accepting L. We are going to prove that A ′ contains a k-irreversible state. Let q 0 ∈ Q ′ be a state equivalent to p. Because A ′ is equivalent to M , for every n ∈ N, the state q n = δ ′ (q 0 , (xσw) n ) is equivalent to q. Since Q ′ is finite, sooner or later, some repetition occur in the so-defined sequence of q i 's. Let i and j be the first two indices such that q i = q j with 1 ≤ i < j (i cannot be equal to 0, because q j is equivalent to q while q 0 is equivalent to p). Now, consider the two paths from q i-1 and q j-1 to q i on string xσw. By minimality of i and j, q i-1 ̸ = q j-1 . Hence, we can decompose the string xσw as uτ v for some u, v ∈ Σ * and τ ∈ Σ, such that δ ′ (q i-1 , u) ̸ = δ ′ (q j-1 , u) and δ ′ (q i-1 , uτ ) = δ ′ (q j-1 , uτ ) = s for some state s ∈ Q ′ . The situation is depicted here:

q i-1 ̸ = s q i q j-1 u τ u τ v
In order to show that s is k-irreversible we proceed in two cases.

Case i = 1.

Since q i-1 = q 0 is equivalent to p and q j-1 is equivalent to q, we get that δ ′ (q i-1 , x) is equivalent to δ(p, x) which is different from δ(q, x). It follows that δ ′ (q i-1 , x) ̸ = δ ′ (q j-1 , x) and, since x is a prefix of u, |u| ≥ |x| = k -1. Thus, s is k-irreversible by Remark 2.

Case i > 1.

We directly obtain that δ(q i-2 , xσwu) ̸ = δ(q j-2 , xσwu), while δ(q i-2 , xσwuτ ) = δ(q j-2 , xσwuτ ) = s. Hence, s is |xσwu|-irreversible and finally k-irreversible by Remark 2.

An immediate consequence of Lemma 7 and Theorem 6, which strengthens the statement of Lemma 7, is that whenever a minimum automaton contains the kforbidden pattern, so does any equivalent dfa. However, the converse is not true in general. The condition in Lemma 7 is indeed on the minimum dfa accepting the language under consideration. If we remove the requirement that the considered dfa has to be minimum, the statement becomes false. For instance, the language L = a * is reversible even though for each k > 0 we can build a dfa accepting it, which contains the k-forbidden pattern (see Fig. 3).

We are now able to characterize k-reversible languages in terms of the structure of minimum dfas: Theorem 8. Let L be a regular language. Given k > 0, L ∈ rev k if and only if the minimum dfa accepting L does not contain the k-forbidden pattern.

Proof. The if part is a consequence of Theorem 6, while the only-if part derives from Lemma 7. From Theorem 8, we observe that to transform each dfa A accepting a kreversible language into an equivalent rev k dfa, firstly we can transform A into the equivalent minimum dfa M and then we can apply to M the construction presented in Sec. 3.1.

As a consequence of Theorem 8, we also obtain:

Corollary 9. L ∈ rev k+1 \ rev k if and only if the maximum h such that the minimum dfa accepting L contains the h-forbidden pattern is k.

Weakly and Strongly Irreversible Languages

By Definition 1, a language is weakly irreversible if it is k-reversible for some k > 0, namely if it is in the class k>0 rev k . A natural question is whether or not the class of weakly irreversible languages coincides with the class of regular languages. In this section we will give a negative answer to this question, thus proving the existence of strongly irreversible languages, which we define now.

Definition 10. Let k be a positive integer, A = (Q, Σ, δ, q I , F ) be a dfa, and L ⊆ Σ * be a regular language.

• A state r ∈ Q is strongly irreversible if it is k-irreversible for each k > 0.
• The automaton A is strongly irreversible if it contains at least one strongly irreversible state. • The language L is strongly irreversible if it is k-irreversible for each k > 0, i.e., if L is not weakly irreversible.

First of all, we observe that, by Theorem 8, a regular language is strongly irreversible if and only if the minimum dfa accepting it contains a k-forbidden pattern for each k > 0. Using a combinatorial argument, we prove that in order to decide if a language is strongly or weakly irreversible, it is enough to consider only a value of k which depends on the size of the minimum dfa. This "large enough" forbidden pattern will actually be proved to be equivalent to the strong forbidden pattern that we introduce now.

Definition 11. Given a dfa A = (Q, Σ, δ, q I , F ), the strong forbidden pattern is formed by three states p, q and r in Q, three strings v ∈ Σ + , x, w ∈ Σ * and a symbol σ ∈ Σ such that δ(q, v) = q, δ(p, v) = p, i.e., v defines self-loops over both p and q, δ(p, x) ̸ = δ(q, x), δ(p, xσ) = δ(q, xσ) = r and δ(r, w) = p (see Fig. 4).

v ∈ Σ + , x ∈ Σ * , σ ∈ Σ, w ∈ Σ * .
The next result states the equivalence of three conditions that allows us to test whether an automaton contains the k-forbidden pattern for each k > 0.

Theorem 12. Let A be an n-state dfa and N = n 2 -n 2 . The three following statements are equivalent:

(1) A contains the (N + 1)-forbidden pattern;

(2) A contains the strong forbidden pattern;

(3) A contains the k-forbidden pattern for each k > 0.

Proof. (1) ⇒ (2) Suppose now that A contains the (N + 1)-forbidden pattern. Then, there exist p, q, r ∈ Q, σ ∈ Σ, and x ∈ Σ N , such that δ(p, x) ̸ = δ(q, x) while δ(p, xσ) = δ(q, xσ) = r and C r = C q . Let x = σ 1 σ 2 • • • σ N with σ i ∈ Σ for i = 1, . . . , N and let p 0 , . . . , p N (resp., q 0 , . . . , q N ) be the sequence of states entered from p (resp., q) when successively reading the symbols σ i 's, i.e., p = p 0 (resp., q = q 0 ) and p i = δ(p i-1 , σ i ) (resp., q i = δ(q i-1 , σ i )) for i = 1, . . . , N . We furthermore have δ(p N , σ) = δ(q N , σ) = r. Because C q0 = C r , we have C qi = C r for i = 0, . . . , N . Moreover, since p N ̸ = q N and A is deterministic, we get p i ̸ = q i for i = 0, . . . , N . We consider the pairs (p 0 , q 0 ), . . . , (p N , q N ). Notice that there are n 2 -n possible pairs of different states. Thus, there exist two indices i and j, 0 ≤ i < j ≤ N , such that either (p i , q i ) = (p j , q j ) or (p i , q i ) = (q j , p j ). In both cases,

δ(p i , (σ i+1 • • • σ j ) 2 ) = p i and δ(q i , (σ i+1 • • • σ j ) 2 ) = q i .
This directly gives a strong forbidden pattern with states p i , q i and r and self-loops around p i and q i on the nonempty string (

σ i+1 • • • σ j ) 2 .
(2) ⇒ (3) Suppose that A contains the strong forbidden pattern, and fix a positive integer k. By definition, there exist p, q, r ∈ Q, v ∈ Σ + , x ∈ Σ * and σ ∈ Σ such that v defines self-loops around both p and q, δ(p, x) ̸ = δ(q, x) while δ(p, xσ) = δ(q, xσ) = r and C r = C q . Then, by setting x ′ = v k x we obtain a |x ′ |forbidden pattern using the same states p, q and r, the string x ′ and the symbol σ. Since |x ′ | ≥ k, we conclude using Remark 2 that A contains the k-forbidden pattern.

(3) ⇒ (1) Immediate. Combining Theorem 8 with Theorem 12 we obtain:

Corollary 13. Let L be a regular language whose minimum dfa has n states. Then L is strongly irreversible if and only if it is not ( n 2 -n 2 + 1)-reversible. We now present an example of strongly irreversible language.

Example 14. The language L = a * b(a + b) * is strongly irreversible. The minimum automaton accepting it has 2 states (see Fig. 5). We notice that δ(q I , a) ̸ = δ(p, a), while δ(q I , ab) = δ(p, ab) = p. This defines a 2-forbidden pattern. According to Corollary 13, this implies that L is strongly irreversible. Observe that since the string a defines two self-loops around both q I and p, we actually have a strong forbidden pattern, and therefore a k-forbidden pattern for any k > 0 using the string a k b.

Degree of Reversibility: Automata versus Languages

In the following result we present further families of languages, besides that in Example 3, which witness the existence of the proper infinite hierarchy

rev = rev 1 ⊂ rev 2 ⊂ . . . ⊂ rev k ⊂ . . . .
Furthermore, we show that the difference between the "amount" of irreversibility in a minimum dfa and in the accepted language can be arbitrarily large, or even infinite. For k ∈ N, we say that an automaton A (resp., a language L) has degree of irreversibility k if it is (k + 1)-reversible but not k-reversible, namely, if k is the maximum integer such that A is not a rev k dfa (resp., L does not belong to rev k ). If A (resp., L) is strongly irreversible, then we say that it has degree of irreversibility ∞.

Theorem 15. For all k, j ∈ N ∪ {∞} with 0 < k ≤ j, there exists a regular language L k,j such that:

• the minimum dfa accepting L k,j has degree of irreversibility j;

• L k,j has degree of irreversibility k.

Proof. We first consider the case k, j ∈ N. When k = j it is enough to consider the minimum dfa accepting the language a * b k b * (cf. Example 3), which is (k + 1)reversible but contains the k-forbidden pattern. From now on, we suppose k < j. Let L k,j be the language accepted by the automaton A k,j = (Q, Σ, δ, q I , F ) where Σ = {a, b}, Q = {q I , r, q F } ∪ {s 1 , . . . , s j } ∪ {t 1 , . . . , t j }, F = {t j , q F }, and the transition function is defined as follows (see Fig. 6 for an example):

• δ(q I , a) = s 1 and δ(q I , b) = t 1 • δ(s i , a) = s i+1 and δ(t i , a) = t i+1 for 1 ≤ i ≤ j -k • δ(s i , b) = s i+1 and δ(t i , b) = t i+1 for j -k < i < j • δ(s j-1 , b) = δ(t j-1 , b) = δ(r, b) = r • δ(r, a) = q F
Firstly, we can observe that A k,j is a minimum dfa. It contains only one irreversible state, namely r, with δ r (r, b) = {r, s j , t j }. We also notice that δ(s 1 , a j-k b k-1 ) = s j is different from δ(t 1 , a j-k b k-1 ) = t j , while δ(s 1 , a j-k b k ) = δ(t 1 , a j-k b k ) = r. Hence A k,j is not a rev j dfa. However, the knowledge of one more symbol in the suffix of the input read to enter r allows to determine the state of the automaton before reading the last symbol. In particular, it is s j (resp., t j ) if the suffix of length j is a j-k+1 b k (resp., ba j-k b k ). Hence, A k,j is a rev j+1 dfa.

In order to prove that L k,j has degree of irreversibility k, we first show that A k,j contains the k-forbidden pattern. Indeed, denoting by p the state s j-k+1 and by x the string b k-1 , we observe that δ(p, x) = s j is different from δ(r, x) = r, while δ(p, xb) = δ(r, xb) = r (in this case, the states q and r from Definition 4 are equal and therefore in the same scc). Furthermore, it is possible to obtain a rev k+1 dfa A ′ k,j equivalent to A k,j by duplicating r and q F with their transitions and by redistributing the incoming transitions from s j and t j , as in the case presented in Fig. 7. Hence, L k , j has degree of irreversibility k.

We now consider the case j = ∞. If k = ∞, it is enough to consider a strongly irreversible language and its minimum automaton, e.g., the language a * b(a + b) * given in Example 14. Otherwise, k ∈ N. Let us first consider the case k = 1. We define the language L 1,∞ ⊆ Σ * by describing its minimum automaton A 1,∞ (see Fig. 8). The automaton uses three states q I , which is the initial state, p and q F which are the final states. There are transitions on b from q I to p and from p to q I , and transitions on a from both p and q I to r. Therefore, r is irreversible. It is in fact strongly irreversible, since the string b n a defines paths from both q I and p to r, for any n ∈ N. However, it does not contain the forbidden pattern (see Fig. 2(a)), and, thus, the accepted language is reversible. To obtain the languages L k,∞ for k > 1, it is enough to consider the concatenation of the above-defined language L k,j for some arbitrary j > k and the language L 1,∞ . Indeed, the minimum automaton (consisting of the minimum automaton accepting L k,j presented above, in which the state q F is replaced by the entire automaton L 1,∞ a ) is strongly irreversible (due to the second part), but the language has degree of irreversibility k (due to the first part).

Decision Problems

In this section we provide a method to decide whether a language L is strongly or weakly irreversible, and, in the latter case, to find the minimum k such that L is k-reversible, namely, the degree of irreversibility of L.

The idea is to simultaneously analyze all the paths entering each irreversible state r ∈ Q of the minimum dfa A accepting L in order to find the longest string z that, with at least two different paths, leads to r and defines the |z|-forbidden pattern, or to discover that there exist arbitrarily long strings with such property. This corresponds to analyze all couples of paths starting from two different states p, q ∈ Q that, with the same string z, lead to r. Intuitively, this can be done by constructing the product automaton of two copies of the reversal automaton of A, i.e., A r × A r , and by analyzing all paths starting from the states of the form (r, r). Since the goal is to establish the nature of the (ir)reversibility of L -not of A -it is useful to recall that by Definition 4 it is enough to consider a In this case, this "concatenation" of automata does not create additional irreversibility, since in A k,j , the state q F is entered only by transitions with label a, while in A 1,∞ , the state q I is entered only by transitions with label b.

only the couples of paths in which one of them is completely included in the same scc of r, i.e., C r = C q . To this aim, we are going to consider the product between A r and a transformation of A r which is obtained by splitting it in sccs.

Let A = (Q, Σ, δ, q I , F ) be a dfa, A r = (Q, Σ, δ r , F, {q I }) be the reversal automaton of A, and A r sccs = (Q, Σ, δ r sccs , F, {q I }) be the nfa obtained by splitting A r in its sccs, i.e., δ r sccs (r, a) = {q | q ∈ δ r (r, a) and C r = C q } for r ∈ Q and a ∈ Σ. Let us define the nondeterministic automaton  as follows:  = ( Q, Σ, δ, Î, F ) where

• Q = Q × Q; • Î = {(r, r) | r ∈ Q}; • F = Q \ Î; • δ((r ′ , r ′′ ), a) = {(p, q) ∈ δ r (r ′ , a) × δ r sccs (r ′′ , a) | p ̸ = q}.
So defined, the resulting automaton  accepts the strings z such that z r defines a |z|-forbidden pattern in A. Formally, this follows from the following lemma: Lemma 16. Given a string x and a symbol σ, in the dfa A, three states p, q and r with x, σ and C q = C r form a |xσ|-forbidden pattern if and only if in  there exists a path on σx r from the state (r, r) to the state (p, q), i.e., (p, q) ∈ δ((r, r), σx r ).

Proof. (only if) Since δ(p, xσ) = δ(q, xσ) = r and C q = C r , we have p ∈ δ r (r, σx r ) and q ∈ δ r sccs (r, σx r ). Moreover, the sequences p 0 , p 1 , . . . , p k and q 0 , q 1 , . . . , q k of states visited in A along the paths defined by xσ respectively from p = p 0 to r = p k and from q = q 0 to r = q k , satisfy p i ̸ = q i for each i < k. Hence, by definition of δ, there exists a path from (r, r) to (p, q) on σx r in Â, i.e., (p, q) ∈ δ((r, r), σx r ).

(if) For the converse implication, we proceed by induction on the length of x. (Basis) If |x| = 0, namely x = ε, then (p, q) ∈ δ ((r, r), σ). By definition of δ, it follows that δ(p, σ) = δ(q, σ) = r while p ̸ = q and C r = C q , namely, p, q and r form a 1-forbidden pattern using σ.

(Induction step) If |x| > 0, then x = τ y where τ is a symbol and |y| = k -1. Assume that there exists a path from (r, r) to (p, q) on the string σx r = σy r τ . Then, there is a path on σy r from (r, r) to some state (p ′ , q ′ ) such that (p, q) ∈ δ ((p ′ , q ′ ), τ ). Again, by definition of δ, we obtain δ(q, τ ) = q ′ , δ(p, τ ) = p ′ and C q ′ = C q . By the induction hypothesis, we get that p ′ , q ′ and r with y and σ form a |yσ|-forbidden pattern in A. Since C r = C q ′ = C q , we finally obtain that p, q and r with x and σ form a |xσ|-forbidden pattern in A.

Considering Theorem 8, this leads to state the following: Lemma 17. Let A be a minimum n-state dfa and  be the above-described nfa defined from A. Then: The same argument can be exploited to prove that the problem of deciding whether L(A) is strongly or weakly irreversible is in NL, namely the class of problems accepted by nondeterministic logarithmic space bounded Turing machines.

Theorem 18. The problem of deciding whether a language is strongly or weakly irreversible is NL-complete.

Proof. From the minimum dfa accepting the language under consideration we derive the above described automaton Â. The problem can be reduced to testing if the transition graph of  contains at least one loop. In such a case, there are arbitrarily long strings in L( Â), namely strings describing k-forbidden patterns for arbitrarily large k, and L(A) is strongly irreversible (see first item of Lemma 17). The problem of verifying the existence of a loop is in NL.

To prove the NL-completeness, we show a reduction from the Graph Accessibility Problem (GAP ) which is NL-complete (for further details see [START_REF] Jones | Space-bounded reducibility among combinatorial problems[END_REF]). Let G = (V, E) be a directed graph where V = {1, . . . , n}. Our goal is to define a dfa A such that A is strongly irreversible if and only if there exists a path from 1 to n in G, i.e., G belongs to GAP.

Let A = (Q, Σ, δ, q I , {♯}) be a dfa where Q = V ∪ {q I , ♯, 0}, Σ = {0, . . . , n, $, ♯}, and δ is defined as follows: (i) δ(i, j) = j, for (i, j) ∈ E (ii) δ(0, 1) = δ(n, 1) = 1 (iii) δ(0, $) = 0 and δ(n, $) = n (iv) δ(q I , i) = i, for i = 0, . . . , n (v) δ(i, ♯) = ♯, for i = 1, . . . , n Notice that the restriction of the underlying graph of A to states 1, . . . , n coincides with G (transitions (i)), plus the edge from n to 1 (from transitions (ii)), if it does not already exists in G. b Furthermore, to states 0 and n we added a self-loop on the symbol $ (transitions (iii)) and a transition on symbol 1 going to state 1 (transitions (ii)), in order to make the state 1 strongly irreversible. Lastly, we made b It may happen that the transition from state n to state 1 on symbol 1 (from transitions (ii)) is already defined as being an edge in G (transitions (i)); we nevertheless ensure that the transition exists in A. each state useful (transitions (iv) enforce reachability while transitions (v) enforce productivity of each state). By observing that, for σ ̸ = $, any transition labeled by σ enters the state σ, we can prove that $1 is the unique string of length 2 that induces irreversibility, and this 2-irreversibility occurs in state 1. Hence, there are no states other than 1 which are strongly irreversible. Thus, we obtain that the strong forbidden pattern occurs in A only if it is formed by the states 0, n and 1. This is possible only if the states 1 and n are in the same scc because, by construction, there is no path from 1 to 0. Observe that transitions (ii) already ensures that a path from n to 1 exists. Hence, we can conclude that L(A) is strongly irreversible if and only if there exists a path from 1 to n in G.

This reduction can be computed in deterministic logarithmic space.

Conclusion

We introduced and studied the notions of strong and weak irreversibility for finite automata and regular languages. As we have seen in Sec. 5 (see also [START_REF] Kutrib | Degrees of reversibility for DFA and DPDA[END_REF]), there exists an infinite hierarchy of weakly irreversible languages, which is itself strictly included in the class of regular languages by the existence of strongly irreversible languages as proved in Sec. 4. In both cases, the witness languages are defined over a binary alphabet, so the question arises whether the same results hold in the case of a one-letter alphabet, i.e., in the case of unary languages. We now briefly discuss this point. First of all, we remind the reader that the transition graph of a unary dfa consists of an initial path, which is followed by a loop (for a recent survey on unary automata, we address the reader to [START_REF] Pighizzini | Investigations on automata and languages over a unary alphabet[END_REF]). Hence, a unary dfa is reversible if and only if the initial path is of length 0, i.e., the automaton consists only of a loop (in this

Fig. 1 .

 1 Fig. 1. The minimum automaton accepting the language a * b k b * .

Fig. 2 .

 2 Fig. 2. The forbidden pattern (a) and the k-forbidden pattern (b), in which σ ∈ Σ, w ∈ Σ * , and x ∈ Σ k-1 .

Fig. 3 .

 3 Fig.3. The minimum dfa accepting the reversible language a * , and an equivalent dfa containing the 3-forbidden pattern

Fig. 4 .

 4 Fig. 4. The strong forbidden pattern:v ∈ Σ + , x ∈ Σ * , σ ∈ Σ, w ∈ Σ * .

Fig. 5 .

 5 Fig. 5. The minimum automaton accepting the language L = a * b(a + b) *

Fig. 6 .

 6 Fig. 6. The minimum automaton A 4,6 accepting the language L 4,6 .

Fig. 7 .Fig. 8 .

 78 Fig. 7. A rev 5 dfa accepting the language L 4,6 .

Fig. 9 .

 9 Fig. 9. The automaton A obtain from a graph G. Only transitions that have been added to G (i.e., transitions (ii) to (v)) are depicted.

  since the ordering of the pairs

			1st Reading
	March 26, 2022 20:59	112-IJFCS	2241005
		Weakly and Strongly Irreversible Regular Languages 11

  For each k > 0, L(A) ∈ rev k if and only if L( Â) contains only strings of length less than k.Proof. The first item directly follows from Theorem 12, Corollary 13, and Lemma 16. The second item follows from Corollary 9 and Lemma 16.

			1st Reading
	March 26, 2022 20:59	112-IJFCS	2241005
		Weakly and Strongly Irreversible Regular Languages 19
	-L( Â) is an infinite language;
	-L( Â) contains a string of length n 2 -n 2	+ 1.
	•
	• The following statements are equivalent:
	-L(A) is strongly irreversible;

March 26, 2022 20:59 112-IJFCS 2241005

Weakly and Strongly Irreversible Regular Languages 21 case the accepted language is said to be cyclic). We can also observe that given an integer k > 0, a unary language is k-reversible if and only if it is accepted by a dfa with an initial path of length less than k states. Hence, for each k, the language a k a * is (k + 1)-reversible, but not k-reversible. This shows the existence of an infinite hierarchy of weakly irreversible languages even in the unary case. Furthermore, from the above discussion, we can observe that if a unary language is accepted by a dfa with an initial path of k states, then it is (k + 1)-reversible. This implies that each unary regular language is weakly irreversible (see also [START_REF] Kutrib | Degrees of reversibility for DFA and DPDA[END_REF]Proposition 10]). Hence, to obtain strongly irreversible languages, we need alphabets of at least two letters.

The definition of k-reversible automata and languages have been given for each positive integer k. One could ask if it does make sense to consider a notion of 0reversibility. According to the interpretation we gave to k-reversibility, a state is 0reversible when in each computation its predecessor can be obtained by knowing the last 0 symbols which have been read from the input, i.e., without the knowledge of any previous input symbol. This means that a 0-irreversible state can have only one entering transition, or no entering transitions if it is the initial state. As a consequence, the transition graph of a 0-reversible automaton is a tree rooted in the initial state and 0-reversible languages are exactly finite languages.