The states of a deterministic finite automaton $\mathcal A$ can be identified with collections of words in $\pf{L(\mathcal A})$—the set of prefixes of words belonging to the regular language accepted by $\mathcal A$. But words can be ordered and among the many possible orders a very natural one is the co-lexicographic one. Such naturalness stems from the fact that it suggests a transfer of the order from words to the automaton’s states. This suggestion is, in fact, concrete and in a number of papers  automata admitting a total ordering of states coherent with the ordering of the set of words reaching them  have been proposed, studied, and implemented. Such class of ordered automata—the Wheeler automata—turned out to be efficiently stored/searched using an index and the set of words reaching each of their states have been proved to be intervals of the co-lexicographic ordered $\pf{L(\mathcal A})$.

Unfortunately  not all automata can be totally ordered as previously outlined. That is, in general not all sets of prefixes of $\mathcal L(\mathcal A)$ reaching a given state form an interval in $\pf{L(\mathcal A})$. However, automata can always be partially ordered and an intrinsic measure of their complexity can be defined and effectively determined, as the minimum width of  one of their admissible partial orders.
As    shown in previous works, this new concept of width of an automaton  has useful consequences in the fields of graph compression, indexing data structures, and automata theory.

In this paper we prove that  a canonical, minimum-width, partially-ordered, automaton accepting a language $\mathcal L$—dubbed the Hasse automaton $\mathcal H$ of $\mathcal L$—can be exhibited. $\mathcal H$ provides, in a precise sense, the best possible way to (partially) order the states of any automaton accepting $\mathcal L$, as long as we want to maintain an operational link with the (co-lexicographic) order of $\pf{L(\mathcal A})$.
The difficulty in defining the Hasse automaton is a consequence of the existence of (co-lex) monotone sequences  of words  reaching infinitely many times more than one state of any deterministic automaton accepting L. Properly constructing the Hasse's automaton requires a distribution of these monotone sequences upon $\mathcal H$’s states on different linear components of the underlying partial order.
The number of such linear components (i.e. the width of the underlying partial order) intrinsically constrains the index-ability and, hence, the complexity of $\mathcal L$.
We prove that such a complexity, that is,  the width of the language, can be effectively computed from the minimum  automaton recognizing the language.
Finally, we  explore the relationship between two (often conflicting) objectives: minimizing the width and minimizing the number of states of an automaton.

§ INTRODUCTION

Equipping the domain of a structure with some kind of order is often a fruitful move performed in both Computer Science and Mathematics. An order provides direct access to data or domain elements and sometimes allows to tackle problems too difficult to cope with without some direct manipulation tool. For example, in descriptive complexity it is not known how to logically capture the class $P$ in general, while this can be done using a logic defined on a signature including an order relation (see [16]).
The price to be paid  when imposing an order may be the restriction of the class of admissible structures. If we do not wish to pay such a price, a partial order can be a reasonable alternative. Then the farther the partial order is from a total order, the less we are able to simplify our study. The “distance” from the partial to a total order becomes    a measure of the extent to which we have to “tame”  the class of structures under consideration.

In this paper we cast the above observations onto the class of finite automata.
Partial orders and automata have already met and attracted attention because of their relation with logical, combinatorial, and algebraic characterization of languages (see, among many others,  [20, 4, 21]). In the literature a partially-ordered NFA is an automaton where the transition relation induces a partial order on its states (see  [17], for example,  for recent complexity results on this class of automata). More recently, in an effort to find a simple and unitary way to present a number of different algorithmic techniques related to the Burrows-Wheeler transform [6], in  [14]  Gagie et al.    proposed a different approach. The simple strategy they put forward was based on the idea of enforcing and using  order on a given automaton, based on an a priori fixed order of its alphabet.
The resulting kind of automata, called Wheeler automata, admit an efficient index data structure for searching  subpaths labeled with a given query pattern  and    enable a representation of the graph in a space proportional to that of the edges' labels (as well as enabling more advanced compression mechanisms, see [3, 18]).
This is in contrast with the fact that general graphs require a logarithmic (in the graph's size) number of bits per edge to be represented, as well as with recent results showing that in general, the subpath search problem can not be solved in subquadratic time, unless the strong exponential time hypothesis is false [5, 12, 11, 13, 19].
Wheeler languages—i.e. languages accepted by Wheeler automata—form an interesting   class of languages, where determinization and  membership  verification   become   easy tasks. However, as was to be expected, requiring the presence of a total Wheeler order  over an automaton comes with a price: languages recognized by Wheeler automata constitute a small class, a subclass of star-free languages  [2].

Our results show that, as a matter of fact,  Wheeler (automata and) languages can be seen as a first level—in some sense the optimal level—of a hierachy of languages based on the minimum width of a suitable partial order over the states of  automata accepting the language. In other words, the minimum width of a partial order definable on the collection of states is a measure that (properly, as we   prove in a companion paper in preparation [7]), stratifies finite automata and regular languages.

The  non-deterministic    width   of a language $\mathcal L$, ${\text{width}^N}(\mathcal L)$,   is  defined as the smallest $p$ such that there exists an NFA $\mathcal A$ with ${\text{width}}(\mathcal A)=p$  recognizing the language. The deterministic width of a language, ${\text{width}^D}(\mathcal L)$ is similarly defined using DFAs.

The  non-deterministic/deterministic width allow to define two hierarchies of regular languages and in a     companion paper in preparation [7]  we proved that   the  two hierarchies are  strict and do  not collapse. Except for level one—the Wheeler languages—the corresponding levels in the two hierarchies do not   coincide:
there exist    languages $ \mathcal{L} $ such that $\text{width}^{D}(\mathcal L) > \text{width}^{N}(\mathcal L)$.
Moreover, we proved that   for a regular language $\mathcal L$ it holds:

\[\text{width}^N(\mathcal L)\leq  \text{width}^D(\mathcal L) \leq 2^{\text{width}^N(\mathcal L)} - 1. \]

As shown in [8], this new concept of width of an NFA/DFA has groundbreaking consequences in the fields of graph compression, indexing data structures, and automata theory: consider a finite automaton of width $p$. Then: (i) the automaton can be compressed using just $\Theta(\log p)$ bits per edge (assuming a constant-sized alphabet), (ii) pattern matching on the automaton's path (including  testing membership in the automaton's accepted language) can be solved in time proportional to $p^2$ per matched character, and (iii) the well-known  explosion in the number of states occurring when computing the powerset DFA equivalent to an input NFA is exponential in $p$, rather in the input's size [8].

Having established that the width of a language is a meaningful complexity measure,  in this paper we address the problem of the effectiveness of this measure in the deterministic case:
is the deterministic width of a language $\mathcal L$, presented  by an automaton,  computable?
Notice that the width of a language  is not in general equal to the width of, say,  its  minimum automaton, since already at level one of the deterministic hierarchy there are Wheeler languages whose minimum automaton has deterministic width greater than one [1].

In this paper,  answering positively the above question we prove that any language admits a canonical automaton realising its (best) width.

In particular, we show that, although the deterministic width of a language, $\text{width}^D(\mathcal L)$, differs in general from the width of its (unique) minimum automaton,  $\text{width}^D(\mathcal L)$ can be computed and an automaton realising this width can be exhibited. The key observation for this result is a  combinatorial   property of automata that we called the entanglement number of a DFA. The entanglement of an automaton $\mathcal A$ measures the intrinsic incomparability of the automaton's states, which cannot be reduced even if we duplicate states.

This turns out to exactly correspond to the width of the partial order of sets of words reaching any given state—the partial order obtained as a lifting to sets of the co-lexicographic order of their elements/words. For this reason, the above mentioned canonical automaton is dubbed Hasse automaton and its states can be distributed in $\text{width}^D(\mathcal L)$ linear components.

Next, we prove that the entanglement of a language $\mathcal L$ (i.e. the best possible entanglement for $\mathcal L$) is readable/computable on the minimum DFA accepting $\mathcal L$ and can always be realized as the width of the Hasse automaton. The Hasse automaton is built on top of a  convex decomposition of the trace of $\mathcal L$, which is the linear co-lexicographic order of the prefixes of words belonging to $\mathcal L$.

Finally, we provide a DFA-free interpretation of the width by proving a full Myhill-Nerode theorem. Every linear component determines a partition of some sets of strings into convex sets, and algebraically we can capture this property by considering convex equivalence relations. We also exhibit a minimum automaton and, more generally, we explore the relationship between two (often conflicting) objectives: minimizing the width and minimizing the number of states.

§ NOTATIONS ON AUTOMATA AND ORDERS

Let $\Sigma$ be a finite alphabet and let  $ \Sigma^*$ be the set of  all (possibly empty) finite words on $\Sigma$. A finite  nondeterministic  automaton  (a NFA) accepting strings in $ \Sigma^{*} $ is a tuple  $\mathcal A=(Q, s, \delta,F)$ where $ Q $ is a finite set of states, $ s $  is a unique initial state, $ \delta(\cdot, \cdot): Q \times \Sigma \rightarrow \mathcal Pow(Q) $ is the  transition function  (where $\mathcal Pow(Q)$ is the set of  all subsets of $Q$), and $ F\subseteq Q $ is the set of  final states. Sometimes we write $Q_{\mt A}, s_{\mt A}, \delta_{\mt A}, F_{\mt A}$ when the automaton $ \mathcal{A} $ is not clear from the context.

As customary, we extend $ \delta $ to operate on strings as follows: for all $ q \in Q, a\in \Sigma, $ and $ \alpha \in \Sigma^{*} $:

\begin{align*}
{\delta}(q,\epsilon)=\{q\}, &   \hspace{1cm}
{\delta}(q,\alpha a) = \bigcup_{v\in{\delta}(q,\alpha)} \delta(v,a).
\end{align*}

We denote by   $\mathcal L(\mathcal A)=\{\alpha\in \Sigma^*: \delta(s, \alpha)\cap F\neq \emptyset\}$   the language accepted by the automaton $ \mathcal A $.
In this paper we will mostly consider deterministic  finite  automata (DFA),  where $ |\delta(q,a)|\leq 1 $,  for any $ q \in Q $ and $ a \in \Sigma $.
If the automaton is deterministic we  write  ${\delta}(q,\alpha)=q'$  for   the unique $q'$  such that ${\delta}(q,\alpha)=\{q'\}$  (if defined).

We assume from each state one can reach a final state (possibly the state itself)  and also that every state is reachable from the (unique) initial state.
Hence, $ \text{Pref}(\mathcal L(\mathcal A))$, the collection of prefixes of words accepted by $ \mathcal A $,  consists of the set of  words that can be read on $ \mathcal{A} $ starting from the initial state.
If $q\in Q$, $\alpha \in \pf L$, we denote by $I_q$ the set of words arriving at $q$:

\[I_q=\{\alpha \in\pf L: q\in \delta(s, \alpha)\}.\]

In the paper we will   use the following   consequence of the Myhill-Nerode Theorem for regular languages: if $\mt A$ is the minimum DFA recognizing a language $\mt L$  and $\mt B$ is   any DFA  recognizing $\mt L$, then any $I_q$ with $q\in Q_{\mt A}$ is the union of a finite number of sets $I_u$, for $u\in Q_{\mt B}$.

A  partial order is a pair $ (Z, \le) $,   where     $ Z $ is a set and   $ \le $ is a binary relation on $ Z $ being reflexive, antisymmetric, and transitive. Any $  u, v \in Z $ are said to be $ \le $-comparable if either $ u \le v $ or $ v \le u $. We write $ u < v $ when $ u \le v $ and $ u \not = v $.
We write $ u ~\|~ v $ if $ u $ and $ v $ are not  $\leq$-comparable.

A  partial order $ (Z, \le) $ is a total order     if     every pair of elements in $(Z, \le)$ are $\le$-comparable.   A subset $ Z' \subseteq Z $ is a $\le$-chain if $ (Z', \le) $ is a total order, and a family $ \{Z_i\}_{i = 1}^p $ is a $\le$-chain partition if $ \{Z_i\}_{i = 1}^p $ is a partition of $ Z $ and each $ Z_i $ is a $\le$-chain.

The width of a partial order  $ (Z, \le) $ is the cardinality of a smallest $ \le$-chain partition.  A subset  $ U \subseteq Z $ is an $\le$-antichain if every pair of elements in $ U $ are not $ \le $-comparable. Dilworth's Theorem [9] states that the width of $ (Z, \le) $ is  equal to the cardinality of a largest $\le$-antichain.

A partial order   $\leq$ on $Z$   induces a   partial order over the  non-empty subsets of $Z$, still denoted by $\leq$ and defined   as follows:
$X\leq Y \Leftrightarrow ( X=Y) ~\lor~  \forall x \in X ~ \forall y\in Y ~( x<y)$.   If $ z \in Z $ and $ X \subseteq Z $, then $ z < X $ is a shortcut for $ \{z \} < X $ and $ X < z $ is a shortcut for $ X < \{z\} $.

A monotone sequence in a partial order $(Z, \le)$ is a sequence $(v_n)_{n\in \mathbb N}$ with $v_n\in V$ and either $v_i\le v_{i+1}$, for all $i$, or  $v_i\ge v_{i+1}$, for all $i$.

Throughout the paper, we assume that  there is a fixed total order $ \preceq $ on $ \Sigma $ (in our examples, the alphabetical order), and we extend it co-lexicographically to words in $\Sigma^*$, that is, $ \alpha \prec \beta $ if and only if the the reversed string $ \alpha^R $ is lexicographically smaller than the reversed string $ \beta^R $.

Throughout the paper, we assume that there is a fixed total order $ \preceq $ on $ \Sigma $ (in our examples, the alphabetical order) , and we extend it co-lexicographically to words in $\Sigma^*$. To compare two words  $\alpha, \beta$ we start from their right   end  and compare
the first letter where they differ.  Formally,  using the same notation $\preceq$ on words,
for $\alpha=a_1\ldots a_n, \beta=b_1 \ldots b_k $,  we have $\alpha \preceq \beta $ if and only if either $\alpha$ is a suffix of $\beta$  or  $(\exists i) (a_{n-i}\prec b_{k-i}  \wedge (\forall j<i ) ~ a_{n-j}= b_{k-j})$.

If $\alpha\preceq  \alpha'\in \Sigma^*$, we define $[\alpha, \alpha']=\{\beta: \alpha\preceq \beta \preceq \alpha'\}$;  if the order among $\alpha, \alpha'$ is not known,  we set
$[\alpha, \alpha']^{\pm}=
[\alpha, \alpha']$, if $\alpha \preceq  \alpha'$, while  $[\alpha, \alpha']^{\pm}=
[\alpha', \alpha]$,  if $\alpha' \preceq  \alpha$.

§ PREVIOUS RESULTS

In this section we contextualise  our work with respect to previously proved results in the field.

Wheeler automata/languages where introduced in [14] as a means for transferring known and efficient string-manipulation indexes and techniques based on the Burrows-Wheeler transform [6] from strings  to languages. Given an ordered alphabet $ (\Sigma, \preceq) $, a  Wheeler order over an NFA  $\mathcal A=(Q, s, \delta, F)$ is   a total  order  $ \leq $  over
$Q$ in which  the initial state $s$  is the minimum and for every
$ v_{1} \in \delta(u_{1},a_{1}) $ and $ v_{2} \in \delta(u_{2},a_{2}) $, with $ a_1, a_2 \in \Sigma $:

(i) $ a_{1}\prec a_{2}\rightarrow v_{1} < v_{2} $;

(ii) $  (a_{1}=a_{2}  \wedge u_{1} < u_{2}) \rightarrow v_{1} \leq v_{2}$.

As stated in the introduction, the class of Wheeler NFAs (i.e., NFAs endowed with a Wheeler order)  reduces membership-query time  from $O(\pi m)$ (where $\pi$ is the length of the query and $m$ is the size of the NFA)  to the optimal $O(\pi)$ after a suitable pre-processing (construction of an index) that can be done in time $O(m)$.    In [15] the problem of deciding whether a given NFA admits a Wheeler order was proved to be NP-complete, while the same problem restricted to DFA or even to reduced NFA (that is automata where different states are reached by different sets of words) becomes polynomial [2]. A regular language is Wheeler if it is recognized by a Wheeler NFA. In [1] it is proved that every Wheeler language is also recognized by some Wheeler deterministic automaton. In [2] it is also proved that it can be decided in polynomial time whether a regular language - given by means of a DFA recognizing the language - is Wheeler.
Notice that the natural  generalization  obtained by considering all possible orders on the alphabet $ \Sigma $   leads to a larger class of languages, but, as proved in [10],  the membership problem becomes  computationally more complicate ($NP$-complete instead of polynomial).

In [8] the totality  requirement  on  the order $\leq$ of states is dropped, thereby obtaining  the notion of co-lexicographic order over an NFA $\mathcal A=(Q, s, \delta, F)$. The order $ \le $ can now be partial and (ii) is replaced with:
(ii)'  $  (a_{1}=a_{2}  \wedge v_{1} < v_{2}) \rightarrow u_{1} \leq u_{2}$.

Notice that (ii) and (ii)' are equivalent on total orders. We measure the complexity of a co-lexicographic order by its width, so a Wheeler order is co-lexicographic order of width 1.

In    [8]  it is   proved that the if an NFA admits a co-lexicographic order of width $p$, then:

* indexed pattern matching can always be solved in $\tilde O(\pi p^2)$ time (assuming constant-sized alphabet for simplicity);

* the standard powerset construction algorithm always produces an output whose size is exponentially bounded in $p$, rather than in the input's size;

* NFAs can be succinctly encoded using $O(1+\log p)$ bits per edge  (assuming constant-sized alphabet for simplicity).

Every automaton admits a co-lexicographic order [8], so for every regular language we can define $ \text{width}^{N}(\mathcal L) $ ($\text{width}^{D}(\mathcal L) $) to be the minimum integer $ p $ such that there exists an NFA (DFA) accepting $ \mathcal{L} $ and admitting a co-lexicographic order of width $ p $. A language is Wheeler if and only if $ \text{width}^{N}(\mathcal L) = \text{width}^{D}(\mathcal L) = 1 $ [1]. The following properties are proved in  a companion paper in preparation [7]:

* $ \text{width}^{N}(\mathcal L) $ and $\text{width}^{D}(\mathcal L) $ can be arbitrarily large;

* There exist infinite languages $ \mathcal{L} $ such that $\text{width}^{D}(\mathcal L) > \text{width}^{N}(\mathcal L)$  (whereas in the Wheeler case equality always holds);

* $\text{width}^N(\mathcal L)\leq  \text{width}^D(\mathcal L) \leq 2^{\text{width}^N(\mathcal L)} - 1 $ for every language $ \mathcal{L} $.

Additionally, in the above mentioned   companion paper  we also  show that, for any given DFA, the best co-lexicographic order (that is, the one with minimum width) is the partial order that we  introduce below  in Definition <ref>.

In this paper we lift our point of view from automata to  a language-theoretic perspective,
tackling natural problems gravitating towards the following natural question: how do we determine the deterministic width of a language?

§ THE  WIDTH OF A REGULAR LANGUAGE: THE HASSE AUTOMATON

By identifying a state $ q $ with the set of strings $ I_q$ arriving at $q$
we are  able to lift the co-lexicographic  order $\preceq$  to an order on the set of states of a DFA. This results in (partially) ordering states of a DFA by comparing strings arriving  at specific pairs of    states, as in the following definition.

Let $ \mathcal A=(Q, s ,\delta, F) $ be a DFA. Let $ \preceq_\mathcal{A} $ be the partial order on $ Q $ such that for all $ q_{1}, q_{2}\in Q $ with $ q_1 \not = q_2 $:

\begin{align*}
q_{1} \prec_{\mathcal A} q_{2} \iff I_{q_{1}} \prec    I_{q_{2}}.
\end{align*}

In the (minimum)  DFA below  states  $1,2$ are incomparable and the same holds for states $3,4,5$ (see Appendix <ref> for details).

[->,>=stealth', semithick, auto, scale=0.7]

[state,accepting,initial] (s)    at (0,0)	$0$;

[state, accepting,label=above:] (1)    at (-2,1)	$1$;
[state,accepting, label=above:] (2)    at (-2,-1)	$2$;

[state, accepting,label=above:] (3)    at (4,0)	$3$;
[state,accepting, label=above:] (4)    at (2,1.5)	$4$;
[state,accepting, label=above:] (5)    at (2,-1.5)	$5$;

(s) edge [] node [above] $a$ (1);
(s) edge [] node [] $b$ (2);

(s) edge [] node [] $k,f$ (3);
(s) edge [] node [] $e,h$ (4);
(s) edge [] node [below] $g$ (5);
(5) edge [] node [below] $d$ (3);
(4) edge [] node [] $e$ (3);
(1) edge  [bend left=60, above] node [] $d$ (3);
(1) edge  [loop above] node $c$ (1);
(2) edge  [loop below] node $c$ (2);

A (minimum) automaton $\mt A$ with  partial order $\preceq_{\mt A}$ of  width $3$.

An important measure of the complexity of a DFA $ \mathcal A$ is the “distance" of the  partial order $\preceq_{\mathcal A}$ from a total order. Formally, such a distance is captured by the notion of width.

The width of a deterministic automaton, $\text {width}(\mathcal A)$,  is the width of the partial order $\preceq_{\mathcal A}$  or,  equivalently,  the maximum cardinality of an  antichain in $\preceq_{\mathcal A}$.

The  automaton in Figure <ref> has width equal to $ 3 $  because $ \{3, 4, 5 \} $ is the largest $ \preceq_\mathcal{A} $-antichain. A $ \preceq_\mathcal{A} $-chain partition of cardinality $ 3 $ is, for example, $ \{\{0, 1, 3 \}, \{2, 4 \}, \{5 \} \} $.

We extend the notion of width from automata to languages, by considering  the best possible width among all automata recognizing the language.

Given a regular language $\mathcal L$, its  deterministic width is defined as follows:

\[\text {width}^D(\mathcal L)= \text{min} \{ \text{width}(\mathcal A)\mid ~ \mathcal A ~\text{is a DFA  } \wedge  \mathcal L(\mathcal A)=\mathcal L\}.\]

Analogously, one may define the non-deterministic width. In this paper, we will only study the deterministic width of a language, so we shall  use the notation  $\text {width}(\mathcal L)$ instead of $\text {width}^D(\mathcal L)$.

It would be convenient to have the width of a language equal to the width of its minimum automaton. Unfortunately, in general, this is not the case.

In Figure <ref>, the automaton  $ \mathcal{A}_1 $ on the left is a minimum DFA of width 3. The automata $ \mathcal{A}_2 $ and $ \mathcal{A}_3 $ in the center and on the right are two non-isomorphic automata of width 2 recognizing the same language recognized by $ \mathcal{A}_1 $ and having only one state more than $ \mathcal{A}_1 $. No DFA of width 1 recognizes this language. Hence, the width of the language is 2, the width of the minimum automaton is 3, and there is not a  unique minimum automaton among all DFAs of minimum width. More details can be found in Appendix <ref>.

Let $\mt A$ be the minimum DFA $\mt A$ of  Example <ref>. We know that $\text{width}(\mt A)=3$.   On the other hand, $\text{width}(\mt L ({\mt A}))=2$ because: 1)  the   automata in Figure <ref> recognize $\text{width}(\mt L ({\mt A}))$ and both  have width two; 2) there are no automata of width $1$ recognizing $\text{width}(\mt L ({\mt A}))$ (see the Appendix for details). Notice that the two automata have minimum number of states among automata of width two recognizing the language $\mt L ({\mt A})$ (they have just one state more than the minimum automaton for the language), but they are not isomorphic.

Although the concept of minimum automaton makes perfect sense for Wheeler languages [1], it may seem that no minimality result holds true for non-Wheeler languages. However, in section <ref> we will explain why Example <ref> is only seemingly undesirable, and we will derive an adequate notion of minimality.

[->,>=stealth', semithick, auto, scale=1]

[state,accepting,initial] (s)    at (0,0)	$0$;

[state, accepting,label=above:] (1)    at (-2,1)	$1$;
[state,accepting, label=above:] (2)    at (-2,-1)	$2$;

[state, accepting,label=above:] (3)    at (4,0)	$3$;
[state,accepting, label=above:] (4)    at (2,1.5)	$4$;
[state,accepting, label=above:] (5)    at (2,-1.5)	$5$;

(s) edge [] node [above] $a$ (1);
(s) edge [] node [] $b$ (2);

(s) edge [] node [] $k,f$ (3);
(s) edge [] node [] $e,h$ (4);
(s) edge [] node [below] $g$ (5);
(5) edge [] node [below] $d$ (3);
(4) edge [] node [] $e$ (3);
(1) edge  [bend left=60, above] node [] $d$ (3);
(1) edge  [loop above] node $c$ (1);
(2) edge  [loop below] node $c$ (2);

[->,>=stealth', semithick, auto, scale=1]

[state,accepting,initial] (s)    at (-3,0)	$0$;

[state, accepting,label=above:] (1)    at (-5,1)	$1$;
[state,accepting, label=above:] (2)    at (-5,-1)	$2$;

[state, accepting,label=above:] (3)    at (1,0)	$3$;
[state, accepting,label=above:] (3')    at (-1,-0.5)	$3'$;
[state,accepting, label=above:] (4)    at (-1,1.3)	$4$;
[state,accepting, label=above:] (5)    at (-1,-1.5)	$5$;

(s) edge [] node [above] $a$ (1);
(s) edge [] node [] $b$ (2);

(s) edge [] node [] $k$ (3');
(s) edge [bend left=10] node [] $f$ (3);
(s) edge [] node [] $e,h$ (4);
(s) edge [] node [below] $g$ (5);
(5) edge [] node [below] $d$ (3);
(4) edge [] node [] $e$ (3);
(1) edge  [bend left=80, above] node [] $d$ (3);
(1) edge  [loop above] node $c$ (1);
(2) edge  [loop below] node $c$ (2);

[->,>=stealth', semithick, auto, scale=1]

[state,accepting,initial] (sb)    at (4,0)	$0$;

[state, accepting,label=above:] (1b)    at (2,1)	$1$;
[state,accepting, label=above:] (2b)    at (2,-1)	$2$;

[state, accepting,label=above:] (3b)    at (8,0)	$3$;
[state,accepting, label=above:] (4b')    at (6,1.3)	$4'$;
[state,accepting, label=above:] (4b)    at (6,0.3)	$4$;
[state,accepting, label=above:] (5b)    at (6,-1.5)	$5$;

(sb) edge [] node [above] $a$ (1b);
(sb) edge [] node [] $b$ (2b);

(sb) edge [bend right=30] node [] $k, f$ (3b);
(sb) edge [] node [] $h$ (4b');
(sb) edge [] node [] $e$ (4b);
(sb) edge [] node [below] $g$ (5b);
(5b) edge [] node [below] $d$ (3b);
(4b) edge [] node [] $e$ (3b);
(4b') edge [] node [] $e$ (3b);
(1b) edge  [bend left=80, above] node [] $d$ (3b);
(1b) edge  [loop above] node $c$ (1b);
(2b) edge  [loop below] node $c$ (2b);

Three DFAs recognizing the same language.

We now exhibit a measure that on the minimum automaton will capture exactly the width of the accepted language: the  entanglement number of a DFA.

Let $\mathcal B$ be a DFA with  set of  states $Q$.

* A subset $Q'\subseteq Q$ is entangled if there exists a monotone sequence  $(\alpha_i)_{i\in \mathbb N}$ such that for all $q' \in Q'$ it holds $\delta(s,\alpha_i)=q'$ for infinitely many $i$'s. In this case  the sequence $(\alpha_i)_{i\in \mathbb N}$ is said to be a witness for $Q'$.

* A set $V\subseteq Pref (\mathcal{L(B)})$ is entangled  if the set  $\{ \delta(s,\alpha)  ~|~ \alpha \in V\}$, consisting of all states occurring in $ V $, is entangled.

Moreover, define:
\begin{align*}
& {\text ent}(\mathcal B) = max\{|Q'| \mid Q'\subseteq Q \text{~and~} Q'\text{ is entangled } \}&\\
&  {\text ent}(\mathcal L) = {\text min} \{ {\text ent}(\mathcal B) ~|~ \mt B ~\text{is a DFA} ~ \land~\mt L(\mt B)=\mt L\}. &\\
\end{align*}

Notice that any singleton $\{q\} \subseteq Q$  turns out to be entangled,  as  witnessed by the trivially monotone sequence $(\alpha_i)_{i\in \mathbb N}$ where all the $\alpha_i$'s are equal and $\delta(s,\alpha_i) = q$.

For example, the entanglement of all  DFAs  in Figure  <ref> is two,   because the only entangled subset of states is $\{1,2\}$.

When two states $q\neq q'$ of a DFA  $ \mathcal{B} $  belong to an entangled set,   there are words $\alpha\prec \beta\prec \alpha'$ such that $\alpha,\alpha'\in I_q, \beta\in I_{q'}$, and so that neither $I_q\prec I_{q'}$ nor  $I_{q'}\prec I_{q}$ can hold. In other words,  two distinct states $q, q'$  belonging to an entangled set are always $\preceq_{\mt B}$-incomparable.  More generally,   the entanglement of a DFA is always smaller than  or equal to its width.

Let $ \mathcal B$ be a DFA. Then
$\text {ent}(\mathcal B)\leq \text{width}(\mathcal B).$

The converse of the above inequality is not always true:   for the (minimum) DFA $\mt A_1 $ on the left of  Figure <ref> we have  $\text {ent}(\mathcal A)=2,  \text{width}(\mathcal A)=3$.

We can easily prove that the    entanglement of a regular  language is realized by the minimum automaton accepting the language.

If  $\mathcal A $ is the minimum   DFA recognizing $\mathcal L$ then
$\text{ent}(\mathcal A)= \text{ent}(\mathcal L)$.

Our aim is to prove  that   $\text{width} (\mt L(\mt A))= \text{ent} (\mt A)$ for $\mathcal A$ minimum. To prove this equality, we proceed as follows.  We first prove that, given a DFA $\mt B$,  there exists an equivalent DFA  $\mt B'$ such that   $\text{ent} (\mt B)= \text{width} (\mt B')$, that is, the automaton $\mt B'$ realizes the entanglement of $\mt B$ as its width.

In order to give some intuition on the construction of the automaton $\mt B'$  we  use the trace of a DFA,  that is the (in general) transfinite   sequence: $(\delta(s, \alpha))_{\alpha \in (\pf L,\preceq)}$ indexed over the totally ordered set $(\pf L,\preceq)$. We depict below a hypothetical $(\pf L,\preceq)$,  together with the  trace left by a  DFA $\mt B$ with set of states $\{q_1, q_2, q_3 \}$ and  $\delta(s, \alpha_i)=\delta(s, \alpha')=q_1$,
$\delta(s, \beta_i)= \delta(s, \beta_i')=q_2$, and  $\delta(s, \gamma_i)=q_3$:

$\alpha_1$    $ \prec $    $\beta_1$    $ \prec $    $\alpha_2$    $ \prec $    $\beta_2$    $ \prec $     $ \ldots $     $ \prec $     $\alpha_i$    $ \prec $    $\beta_i$    $ \prec $     $ \ldots $     $ \prec $    $\beta_1'$     $ \prec $    $\gamma_1$    $ \prec $    $\beta_2'$    $ \prec $    $\gamma_2$    $ \prec $     $ \ldots $     $ \prec $    $\beta_i'$    $ \prec $    $\gamma_i$    $ \prec $     $ \ldots $     $ \prec $     $\alpha'$

$q_1$      $q_2$      $q_1$      $q_2$      $\ldots$      $q_1$      $q_2$      $\ldots $      $q_2$      $q_3$      $q_2$      $q_3$      $\ldots$       $q_2$      $q_3$      $\ldots $      $q_1$

Consider  the entanglement and  width of $\mt B$.  Notice that the sets $\{q_1, q_2\}$ and $\{q_2,q_3\}$ are entangled. The set  $\{q_1, q_3\}$ is not entangled  and therefore the set $\{q_1, q_2, q_3\}$ is not entangled.  However, $\{q_1, q_2, q_3\}$ contains pairwise incomparable states.
Hence the whole triplet $ \{q_1, q_2, q_3 \} $ does not contribute  to the entanglement but does contribute to the width  so that    $\text{ent}(\mt B)=2< \text{width}(\mt B)=3$.

In general,   an automaton where     incomparability  and  entanglement coincide  would have $\text{ent}(\mt B)=  \text{width}(\mt B)$. Hence, we would like   to force all sets of incomparable states in $\mt B'$ to be entangled.
To this end, we will first slice $\pf L$ into  convex sets where incomparable states are entangled,  that is,
we will prove that there always exists a finite, ordered partition $\mt V=\{V_1, \ldots, V_r\}$ of
$\pf L$ composed of  $\mt B$-entangled convex sets. In the    example above  we can write $\pf L=V_1\cup V_2\cup V_3 $, where:

\[V_1=\{\alpha_1,\beta_1\ldots, \alpha_i, \beta_i, \ldots\}, V_2=\{\beta_1',\gamma_1, \ldots \beta_i', \gamma_i\ldots \},V_3=\{\alpha'\}\]

and the states occurring (and entangled) in $V_1,V_2,V_3$, respectively, are: $\{q_1,q_2\}$, $\{q_2,q_3\}$, and $\{q_1\}$.
To eliminate  the pairwise incomparability  of $q_1,q_2,q_3$ we need to duplicate some of the original states. To this end, we will consider an equivalence relation  $\sim_{\mt V}^{\mt B}$ on $\pf L$ such that two strings are equivalent if and only if they are in the same $ I_q $ and all entangled $ V_i$'s between the two strings intersecate $I_q $. In the above example we have $\alpha_i \sim_{\mt V}^{\mt B} \alpha_j$  for all  integers $i,j$ but $\alpha_1\not \sim_{\mt V}^{\mt B} \alpha'$ because $\alpha_1\prec  V_2\prec \alpha'$ and $V_2\cap I_{q_1}=\emptyset$.

In general, we will prove that the equivalence $\sim_{\mt V}^{\mt B}$    decomposes  the  set  of   words arriving in a state $q$ into a finite number of $\sim_{\mt V}^{\mt B}$-classes  and  induces a well-defined quotient automaton $ \mathcal{B'} $ equivalent to $ \mathcal{B} $.
It will turn out   that  if the $\mt B'$-states $ [q_1]_{\sim_{\mt V}^{\mt B}}, \ldots,  [q_k]_{\sim_{\mt V}^{\mt B}}$ are  pairwise $\preceq_{\mt B'}$-incomparable, then there exists $V\in \mt V$ such that $\{q_1, \ldots, q_k\}\subseteq V$; since $V$ is entangled  the set of states $ \{q_1, \ldots, q_k \} $  contribute  to the  entanglement number of $\mt B$ and we  will obtain $\text{width}({\mt B'})= \text{ent}({\mt B}) $.

In our example, the new automaton $\mt B'$  will leave  the following trace:

$\alpha_1$   $ \prec $   $\beta_1$   $ \prec $   $\alpha_2$   $ \prec $   $\beta_2$    $ \prec $   $\ldots$    $ \prec $    $\alpha_i$    $ \prec $   $\beta_i$    $ \prec $   $\ldots$    $ \prec $   $\beta_1'$     $ \prec $   $\gamma_1$    $ \prec $   $\beta_2'$    $ \prec $   $\gamma_2$    $ \prec $   $\ldots$    $ \prec $   $\beta_i'$    $ \prec $   $\gamma_i$    $ \prec $   $\ldots$    $ \prec $    $\alpha'$

$q_1$      $q_2$      $q_1$      $q_2$      $\ldots$      $q_1$      $q_2$      $\ldots$      $q_2$      $q_3$      $q_2$      $q_3$      $\ldots$       $q_2$      $q_3$      $\ldots$       $q_1'$

and     $\text{ent}(\mt B )=\text{width}(\mt B')=2$.

Formally, let us  start with the existence of  a finite decomposition $\mt V$. The following theorem will be a special case of a combinatorial property of convex subsets of an arbitrary linear order (see Theorem  <ref> and Remark <ref> in Appendix <ref>).

If $\mt B$ is a DFA then there exists a finite  partition $\mt V$  of $\pf {L(\mathcal{B})}$ whose elements  are  convex in $(\pf{L(\mathcal{B})}, \preceq)$ and entangled in $\mt B$.

A partition $\mt V$ as  the one above is called an entangled, convex decomposition of $\mt B$, or e.c. decomposition, for short. If $ \mathcal{V} $ has also minimum cardinality, it is called a minimum-size e.c. decomposition.  We are interested in minimum-size e.c. decompositions because they enforce  additional properties (see Remark <ref> in Appendix <ref>) implying that the relation that will be introduced in the following definition is right-invariant, so making it possible to define a quotient automaton. Note that in general a minimum-size e.c. decomposition of a DFA is not unique (see Example <ref> in Appendix <ref>).

Let $ \mathcal B$ be a DFA and let $\mt V$ be a minimum-size e.c. decomposition of $ \mathcal{B} $. The equivalence relation $\sim_{\mt V}^\mt B$  on  $ \pf {L(B)) }$  is defined by:

\begin{align*}
\alpha\sim_{\mt V}^\mt B \alpha' & \ \Leftrightarrow \
\delta(s,\alpha)=\delta(s,\alpha')  \wedge
(\forall V \in \mt V) \;(\min \{\alpha, \alpha'\} \prec V \prec \max \{\alpha, \alpha'\} \rightarrow  V\cap I_{\delta(s,\alpha)}\neq \emptyset)
\end{align*}

When $ \mathcal{B} $ is clear from the context, we will simply write $ \sim_{\mt V} $.

Let $ \mathcal B$ be a DFA and let $\mt V$ be a minimum-size e.c. decomposition of $ Pref (\mathcal{L(B)})$. Then, $\sim_{\mt V}$ has a finite number of classes on  $\pf {L(\mt B)}$ and
$\mt L(\mt B)$ is equal to the union of some $\sim_\mathcal{V}$-classes.

In order to prove that $\sim_{\mt V}$ is a right-invariant equivalence relation, we will first show a convenient consequence of considering $ \emph{minimum-size} $ e.c. decompositions: the relation $\sim_{\mt V}$ does not depend on the choice of $ \mathcal{V} $.

Let $\mt B$ be a DFA and  let $\mt V$ be a minimum-size e.c. decomposition of $\mt B$.
Then  $\alpha \sim_{\mt V} \alpha'$
if and only if $\delta(s,\alpha)= \delta(s, \alpha')$ and   the interval $[\alpha, \alpha']^\pm$ is contained in a  finite union of convex, entangled sets  $C_1, \ldots,C_n$ in $\pf {L( \mt B)}$, with $C_i\cap I_{\delta(s,\alpha)}\neq \emptyset$ for all $i=1, \ldots,n$. In particular, $ \sim_{\mt V} $ is independent of the choice of $ \mathcal{V} $.

In view of the above lemma we shall drop the subscript $\mt V$ from $\sim_{\mt V}^\mt B $ and we will simply write $\sim^{\mt B} $  (or $ \sim $ when $ \mathcal{B} $ is clear from the context). We can now  prove that   $\sim$ is a right-invariant  equivalence relation.

Let $\mt B$ be a DFA. Then, the equivalence relation $\sim$ is right-invariant.

Let $\mt L= \mt {L(B)}$ Non serve definire L, si può direttamente scrivere L(B), tanto c'è solo due volte.
We must prove that if  $\alpha \sim \alpha' $
and $a\in \Sigma$ is such that $\alpha a \in \pf{L }$ then $\alpha' a\in  \pf{L }$ and  $\alpha a\sim \alpha' a$.
Suppose $ \alpha\sim  \alpha'$
and  $\alpha a \in \pf{L }$. Then, $\delta(s, \alpha)=\delta(s, \alpha')$ so that $\delta(s, \alpha a)=\delta(s, \alpha' a)$ and
$\alpha' a \in \pf L$ per ordine logico meglio scrivere "Then, $\delta(s, \alpha)=\delta(s, \alpha')$, so also $\alpha' a \in \pf L $ and $\delta(s, \alpha a)=\delta(s, \alpha' a)$.   We prove that  $\alpha a\sim \alpha' a$ using Lemma <ref>.
From $\alpha \sim \alpha' $ it follows that there are convex, entangled sets $C_1, \ldots,C_n$, with $C_i\cap I_{\delta(s,\alpha)}\neq \emptyset$,  for all $i=1, \ldots,n$,  and $[\alpha, \alpha']^\pm \subseteq C_1\cup \ldots \cup C_n $. Then,
$[\alpha a, \alpha'a]^\pm \subseteq C_1 a\cup \ldots \cup C_n a $. From
$C_i\cap I_{\delta(s, \alpha)}\neq \emptyset$ it follows that $C_i a\cap I_{\delta(s, \alpha a)}\neq \emptyset$, for all $i=1, \ldots, n$. Since the   $C_i a$'s are easily seen to be convex,
we just have to prove that the $C_i a$'s are   entangled.  If $q_1', \ldots, q_k'$ are  the states occurring  in $C_i a$,    let $\gamma_1a, \ldots, \gamma_ka\in C_i a$ be words such that $\delta(s,\gamma_ia)=q_i'$; then
the states $\delta(s,\gamma_1)=q_1, \ldots \delta(s,\gamma_k)=q_k $ occur in $C_i$ and, since $C_i$ is entangled,  there is an infinite monotone sequence $(\alpha_i)_{i\in \mathbb N}$ witnessing their entanglement. But then the monotone sequence  $(\alpha_i a)_{i\in \mathbb N}$  is a witness for the engagement of $q_1', \ldots, q_k'$.  Hence, the $C_i a$ are entangled and, using Lemma <ref>,  this proves that $\alpha a  \sim  \alpha' a$.

We are now ready to complete the construction of the automaton $\mt B'$. The idea of the proof is to use $ \sim $ to build a quotient automaton.

Let  $\mt B $ be  a DFA. Then, there exists a DFA $\mt B'$ such that $ \mathcal{L(B')} = \mathcal{L(B)} $ and $\text{ent}(\mt B)=\text{ent}(\mt B')= \text{width}(\mt B')$.

In the remaining of this section, given a DFA $ \mathcal{B} $, we will always denote by $ \mathcal{B}' $ the DFA obtained by the construction in Theorem <ref>. Let us now apply  the construction to  the minimum automaton $\mt A$ of a regular language $\mt L$.
If $\mt A$ is the minimum automaton of a regular language $\mt L$,  the DFA $\mt A' $
is called the Hasse automaton for $\mt L$ and it is denoted by $\mt H_{\mt L}$.

The name “Hasse” is justified by the fact that, as shown in the following theorem,  $\text{width}(\mt L)= \text{width}(\mt H_{\mt L})$ so that   the Hasse diagram of the partial order $\preceq_{\mt H}$ allows to “visualize”  the width of the language.

If $\mt A$ is the minimum automaton of the regular language $\mt L$, then:

\[\text{width}(\mt L)= \text{width}(\mt H_{\mt L})= \text{ent}(\mt A)=\text{ent}(\mt L).\]

The Hasse automaton $ \mt H_{\mt L} $ captures the width of a language. The following lemma shows that $ \mt H_{\mt L} $, which is defined starting from the minimum DFA $ \mathcal{A} $, also inherits a minimality property with respect to a natural class of automata. This reasonable result should be compared with Example <ref>, which showed that the minimality problem does not admit a trivial interpretation when the concept of width is introduced. A satisfying solution will be provided in Section <ref>.

Let $ \mathcal{L} $ be a language, and consider the class:

\begin{equation*}
\mathscr{C} = \{\mathcal{B'} | \text{$ \mathcal{B} $ is a DFA and $ \mathcal{L(B)} = \mathcal{L} $} \}.
\end{equation*}

Then, there exists exactly one DFA being in $ \mathscr{C}$ and having the minimum number of states, namely, the Hasse automaton  $\mt H_{\mt L}$. In other words, $\mt H_{\mt L}$ is the minimum DFA of $ \mathscr{C} $.

Except for level one, the levels of the width hierarchy lack a minimum automaton: when we require minimum-sizeity both regarding width and number of states we loose uniqueness up to isomorphism (see Example <ref>). In the next lemma we see that the Hasse automaton is a unique minimum automaton, both regarding width and number of states, when we restrict
the class of automata recognizing $\mt L$ to  the family
$\{\mt B': \mt L({\mt B})=\mt L\}$.

In Section <ref> we will see another way to win back minimality and  uniqueness both regarding  width and number of states.

The Hasse automaton  $\mt H_{\mt L}$ is minimal both with respect to the width and with respect to number of states among automata in the  class $\{\mt B' \;|\; \mt L(\mt B')=\mt L\}$. Moreover, any automaton belonging to the previous class and having the same number of states as $\mt H_{\mt L}$ is isomorphic to $\mt H_{\mt L}$.

We already proved that  $\mt H_{\mt L}$ is minimal with respect to the width. If $\mt B$ is a DFA recognizing $\mt L$ we denote by
$\sim_{\mt B}$ the equivalence relation of Definition  <ref>. If $\mt A$ is the minimal automaton for the language $\mt L$ and $\mt B$ is a DFA recognizing $\mt L$, we prove that $\sim_{\mt B}\;\subseteq\; \sim_{\mt A}$. This can be seen as a direct consequence of Definition <ref> once we remark that a set $C$ entangled in $\mt B$ is also entangled with respect to the minimal automaton $\mt A$ (remember that any set $I_q$, for a state $q$ of the minimal automaton, is a union of sets $I_{q'}$ for
$\mt B'$ states $q'$).
Since the number of states of an automaton $\mt B'$ is equal to the index of $\sim_{B}$, we see that the Hasse automaton $\mt H_{\mt L}= \mt A'$ has minimum number of states among the class $\{\mt B' \;|\; \mt L(\mt B')=\mt L\}$. Moreover, if $\mt B'$ as the same number of states as $\mt H_{\mt L}$, then $\sim_{\mt B}= \sim_{\mt A}$,
and  $\mt B'$ is isomorphic to  $\mt H_{\mt L}$.

§ ON COMPUTING THE WIDTH OF A REGULAR LANGUAGE

The problem of computing the width of an automaton is in $ \texttt{P} $ if the automaton is deterministic, and it is $ \texttt{NP} $-hard if the automaton can be nondeterministic [8]. In this section we address the problem of determining the width of the language recognized by an automaton. More precisely, we show that if we are given a regular language $ \mathcal{L} $ by means of any DFA $\mathcal A$ accepting $ \mathcal{L} $, then the problem of computing $ p = width(\mathcal{L}) $ is in the class , that is, solvable in polynomial time for fixed values of $p$. We propose a dynamic programming algorithm that extends the ideas introduced in [2] when solving the corresponding problem for Wheeler languages.

Theorem <ref> suggests that the minimum automaton should contain all topological information required to compute the width of a language.

In the next theorem, we provide a graph-theoretical characterization of the width of a language based on the minimum automaton recognizing the language.

Let $ \mathcal{L} $ be a regular language, and let $ \mathcal{A} $ the minimum DFA of $ \mathcal{L} $, with set of states $ Q $. Let $ k \ge 2 $ be an integer. Then, $ width(\mathcal{L}) \ge k $ if and only if there exist strings $ \mu_1, \dots, \mu_k $ and $ \gamma $ and there exist pairwise distinct $ u_1, \dots, u_k \in Q $ such that:

* $ \mu_j $ labels a path from the initial state $ s $ to $ u_j $, for every $ j = 1, \dots, k $;

* $ \gamma $ labels a cycle starting (and ending) at $ u_j $, for every $ j = 1, \dots, k $;

* either all the $ \mu_j $'s are smaller than $ \gamma $ or $ \gamma $ is smaller than all $ \mu_j $'s;

* $ \gamma $ is not a suffix of $ \mu_j $, for every $ j = 1, \dots, k $.

In Appendix <ref> we prove further results to bound the lengths of $ \mu_1, \dots, \mu_k $ and $ \gamma $, so making it possible to bound the running time of a dynamic programming algorithm based on Theorem <ref>. We can then conclude:

Let $\mathcal L$ be  a regular language, given as input by means of any DFA $\mathcal A = (Q, s, \delta,F)$ recognizing $ \mathcal{L}$.
Then, $p = \text{width}(\mathcal L)$ is  computable in time $|Q|^{O(p)}$.

§ THE CONVEX MYHILL-NERODE THEOREM

The core result in the study of regular languages is Myhill-Nerode theorem Inserire una buona citazione. Recall the definition of right-invariant equivalence relation Vedo ora che nella sezione 4 usate già la nozione di equivalenza right-invariant, quindi fa un po' strano ridefinirla. Forse è il caso di toglierla (ma devo salvare la nozione di equivalenza che rispetta $ Pref (\mathcal{L}) $):

Let $ \mathcal{L} \subseteq \Sigma^* $ be a language and let $ \sim $ be an equivalence relation on $ \pf L $.

* We say that $ \sim $ respects $ \pf L $ if:

\begin{equation*}
(\forall \alpha, \beta \in \pf L)(\forall \phi \in \Sigma^*)(\alpha \sim \beta \land \alpha \phi \in \pf L \to \beta \phi \in \pf L).
\end{equation*}

* If $ \sim $ respects $ \pf L $, we say that $ \sim $ is right-invariant if for every $ \alpha, \beta \in \pf L $ and for every $ \phi \in \Sigma^* $, if $ \alpha \sim \beta $ and $ \alpha \phi \in \pf L $ (and so $ \beta \phi \in \pf L $), then $ \alpha \phi \sim \beta \phi $.

Let $ \mathcal{L} \subseteq \Sigma^* $ be a language. The Myhill-Nerode equivalence for $ \mathcal{L} $ is the right-invariant equivalence relation $ \equiv_\mathcal{L} $ on $ \pf L $ such that for every $ \alpha, \beta \in \pf L $ it holds:

\begin{equation*}
\alpha \equiv_\mathcal{L} \beta \iff \{\gamma \in \Sigma^* | \alpha \gamma \in \mathcal{L}  \} = \{\gamma \in \Sigma^* | \beta \gamma \in \mathcal{L}  \}.
\end{equation*}

Myhill-Nerode's theorem states that, for a language $ \mathcal{L} \subseteq \Sigma^* $, the following conditions are equivalent:

* $ \mathcal{L} $ is recognized by a DFA (i.e., $ \mathcal{L} $ is regular);

* $ \equiv_\mathcal{L} $ has finite index;

* $ \mathcal{L} $ is the union of some classes of a right-invariant equivalence relation on $ \pf L $ of finite index.

Intuitively, if an equivalence relation $ \sim $ on $ Pref(\mathcal{L}) $ satisfies some properties, then there exists a canonical construction that builds a DFA recognizing $ \mathcal{L} $ starting from $ \sim $, so Myhill-Nerode theorem exactly determines the minimal required properties (namely, right-invariance and finite index) and provides a DFA-free characterization of regular languages. The link between the DFA characterization of regular languages and the equivalence relation characterization of regular languages is provided by the equivalence relation $ \sim_\mathcal{A} $ on $ \pf L $ whose equivalence classes are $ \{I_q | q \in Q \} $, where $ \mathcal{A} = (Q, s, \delta, F) $ is a DFA accepting $ \mathcal{L} $. In fact, $ \sim_\mathcal{A} $ is right-invariant and it is has finite index. Finally, it can be proved that $ \equiv_\mathcal{L} $ is the coarsest equivalence relation with the desired properties, which implies that the canonical construction applied to $ \equiv_\mathcal{L} $ returns a (necessarily unique) DFA recognizing $ \mathcal{L} $ and having the minimum number of states (the minimum DFA).

In this paper, we have described the hierarchy of regular languages by means of their widths, thus the natural question is whether a corresponding Myhill-Nerode theorem can be provided. For instance, given a regular languages $ \mathcal{L} $, if we consider all DFAs recognizing $ \mathcal{L} $ and having width equal to $ width (\mathcal{L}) $, is there a unique such DFA having the minimum number of states? In general, the answer is "no", as showed in Example <ref>.

The non-uniqueness can be explained as follows. If a DFA of width $ p $ recognizes $ \mathcal{L} $, then $ \pf L $ can be partitioned into $ p $ sets, each of which consists of the (disjoint) union of some pairwise comparable $ I_q $'s.  However, in general the partition into $ p $ sets is not unique, so it may happen that two distinct partitions lead to two non-isomorphic minimal DFAs with the same number of states.  For example, in Figure <ref>, the chain partition $ \{ \{0,1,4\}, \{2,3, 5, 3'\} \} $ of the DFA in the center induces the partition $ \{ac^*  \cup \{\epsilon, e, h \}, bc^* \cup ac^*d \cup \{gd, ee, he,f,k,g \} \} $ of $ Pref (\mathcal{L}) $, whereas the chain partition $ \{ \{0,1,3\}, \{2,4, 5, 4'\}\} $ of the DFA on the right induces the partition $\{ac^* \cup ac^*d \cup \{\epsilon, gd,  ee,he, f,k \}, bc^* \cup \{e, h, g\}\}$ of $ Pref (\mathcal{L})$.

As a consequence, no uniqueness results can be ensured as long as partitions are not fixed. But what happens if we fix a partition? As we will prove in this section, once a partition is fixed, it is possible to prove a full Myhill-Nerode theorem, so providing a DFA-free characterization of convex languages and a minimum DFA.

More formally, let $ \mathcal{A} = (Q, s, \delta, F) $ be a DFA, and let $ \{Q_i \}_{i = 1}^p $ be a $ \le_\mathcal{A} $-chain partition of $ Q $. For every $ i \in \{1, \dots, p \} $, define:

\begin{equation*}
Pref(\mathcal{L(A)})^i = \{\alpha \in Pref(\mathcal{L(A)}) | \delta(s, \alpha) \in Q_i  \}.
\end{equation*}

Then $ \{Pref(\mathcal{L(A)} \}_{i = 1}^p $ is a partition of $ Pref (\mathcal{L(A)}) $, and from now on we will think of such a partition as fixed. We now consider the class of all DFAs accepting $ \mathcal{L} $ and inducing the considered partition.

Let $ \mathcal{A} = (Q, s, \delta, F) $ be an DFA, and let $ \mathcal{P} = \{U_1, \dots, U_p \} $ be a partition of $ Pref (\mathcal{L(A)}) $. We say that $ \mathcal{A} $ is $ \mathcal{P} $-sortable if there exists a $ \le_\mathcal{A} $-chain partition $ \{Q_i \}_{i = 1}^p $ such that for every $ i \in \{1, \dots, p \} $:

\begin{equation*}
Pref(\mathcal{L(A)})^i = U_i.
\end{equation*}

We wish to give a DFA-free characterization of languages $ \mathcal{L} $ and the partitions $ \mathcal{P} $ of $ \pf L $ for which there exists a $ \mathcal{P} $-sortable DFA. As in the Myhill-Nerode theorem, we aim to determine which properties an equivalence relation $ \sim $ should satisfy to ensure that a canonical construction provides a $ \mathcal{P} $-sortable DFA. First, $ \mathcal{L} $ must be regular, so $ \sim $ is expected to be right-invariant. In order to develop some intuition on the required properties, let us consider an equivalence relation which plays a key role in the classical Myhill-Nerode theorem. Let $ \mathcal{A} = (Q, s, \delta, F) $ be a $ \mathcal{P} $-sortable DFA, and let $ \sim_\mathcal{A} $ the equivalence relation on $ Pref (\mathcal{L(A)})$ whose equivalence classes are $ \{I_q | q \in Q \} $.   Notice that equivalent string  end up in the same state and so in the same element of   $ \mathcal{P}$ ($ \mathcal{P} $-consistency), and since all states in each $ \preceq_\mathcal{A} $-chain $ Q_i $ are comparable, then each $ I_q $ must be convex in the corresponding element of $ \mathcal{P} $ ($ \mathcal{P} $-convexity). Formally:

Let $ \mathcal{L} \subseteq \Sigma^* $ be a language, and let $ \sim $ be an equivalence relation on $ \pf L $. Let $ \mathcal{P} = \{U_1, \dots, U_p \} $ be a partition of $ \pf L $.

* For every $ \alpha \in \pf L $, let $ U_\alpha $ be the unique element $ U_i $ of $ \mathcal{P} $ such that $ \alpha \in U_i $.

* We say that $ \sim $ is $ \mathcal{P} $-consistent if for every $ \alpha, \beta \in \pf L $, if $ \alpha \sim \beta $, then $ U_\alpha = U_\beta $.

* Assume that $ \sim $ is $ \mathcal{P} $-consistent. We say that $ \sim $ is $ \mathcal{P} $-convex if for every $ \alpha \in \pf L $ we have that $ [\alpha]_{\sim} $ is a convex set in $ (U_\alpha, \preceq) $.

As we will prove, these are exactly the required property for a DFA-free characterization. Lastly, we wish to define an equivalence relation with the above properties inducing a (unique) minimum $ \mathcal{P} $-sortable DFA. We expect such relation to be related with the Myhill-Nerode equivalence, so a sensible choice is $ \equiv_\mathcal{L}^\mathcal{P} $, which is the coarsest $ \mathcal{P} $-consistent, $ \mathcal{P} $-convex and right-invariant equivalence relation refining $ \equiv_\mathcal{L} $. The proof that such a coarsest equivalence relation exists is technical and it is provided in the Appendix <ref> (see Corollary <ref>). We now have all the required definitions to state our Myhill-Nerode theorem, which generalizes the one for Wheeler languages [1].

Let $ \mathcal{L} $ be a language. Let $ \mathcal{P} $ be a partition of $ \pf L $. The following are equivalent:

* $ \mathcal{L} $ is recognized by a $ \mathcal{P} $-sortable DFA.

* $ \equiv_\mathcal{L}^\mathcal{P} $ has finite index.

* $ \mathcal{L} $ is the union of some classes of a $ \mathcal{P} $-consistent, $ \mathcal{P} $-convex, right invariant equivalence relation on $ \pf L $ of finite index.

Moreover, if one of the above statements is true (and so all the above statements are true), then there exists a unique minimum $ \mathcal{P} $-sortable DFA (that is, two $ \mathcal{P} $-sortable DFA having the minimum number of states must be isomorphic).

Notice that for a language $ \mathcal{L}$  it holds $ width(\mathcal{L}) = p $ if and only if there exists a partition $ \mathcal{P} $ of $ \pf L $ that satisfies any of the statements in Theorem <ref>.

Given a $ \mathcal{P} $-sortable DFA recognizing $ \mathcal{L} $, it is possible to build the minimum $ \mathcal{P} $-sortable DFA recognizing $ \mathcal{L} $ in polynomial time by generalizing the algorithm for the Wheeler case [1]. More details on the algorithm and its complexity will follow in a companion paper.

§ CONCLUSIONS

The two topics discussed in this paper are regular languages and order. The link between these two important notions is built upon a technique to cast the co-lexicographic order of (sets of) strings over a (partial) order of the states of a finite state automaton accepting a regular language.
Finite state automata are among the most basic models of computation and ordering is among the most basic data-structuring mechanisms.  Hence, it comes as no surprise that the most powerful algorithmic techniques for solving pattern matching obtained over the last decades exploit precisely this notion of ordering.

Proceeding along the same line, the main theorem that we proved here is the existence of a canonical, partially-ordered automaton realising the minimum size of an anti-chain (the “width") of its states. The partial order of this canonical automaton is built from a convex decomposition of the co-lexicographically ordered collection of the prefixes of the language. This suggests an absolute measure of complexity for regular languages: the width of its canonical automaton. Such a measure turns out to be somehow orthogonal to (and sometimes conflicting with) the mere counting of the number of states of the automaton.

At the same time, the width has a clear algorithmic interpretation because it measures the disposition of the language to be “index-able” [8].

Several intriguing questions can be raised at this point: how much of our findings can be extended to other models of computation—starting from non-deterministic finite automata? What is the exact role played by the specific (co-lex) ordering that we used? Are there alternatives? Is it possible to give effective or approximate constructions of the Hasse automaton? A positive answer to this last question would go a long way towards building a minimum-size automaton among those of minimum width accepting a regular language.

Finally, it would be remarkable to determine a regular-expression-like description of the hierarchy of regular languages based on the width, which would imply both theoretical results (a Kleene-like theorem) and concrete applications (regex pattern matching).

Alcune questione "pratiche":

* Si noti che il problema di determinare un automa (eventualmente minimale) di width minima e equivalente a un automa dato è decidibile (prima si determina la width minima con i risultati nel paper e poi si procede per ricerca esaustiva). Con una costruzione effettiva di Hasse si spera di fare meglio. questione interessante: la ricerca esaustiva dipende anche dal numero $n$ di stati dell'automa di Hasse. Abbiamo un bound per $n$?

* Usiamo l'ordine colessicografico molto nei risultati computazioni, ma poco negli altri risultati, quindi bisognerebbe capire fino a che punto serve. Per esempio, dal paper segue che il risultato "L è riconosciuto da un automa P-sortable se e solo se L is the union of some classes ofaP-consistent,P-convex, right invariant equivalence relationon Pref(L)of finite index" è vero per un arbitrario ordine sulle stringhe. anche dal punto di vista degli indici, non è importantissimo che l'ordine sia colex. Basta che gli stati raggiunti da una stringa formino un'intervallo. In effetti questa è anche la definizione più generale possibile (ma purtroppo non costruttiva) dell'ordine parziale.

* Quello che ancora manca è un modo per legare un livello della gerarchia al livello superiore, in modo da ritrovare una caratterizzazione tipo espressioni regolari (e teorema di Kleene). giusto, questo è moolto interessante! se sapessimo combinare le widths per operazioni regolari, potremmo determinare la width di espressioni regolari. Credo che questo catturi la complessità del regular expression matching, il che sarebbe un risultato molto potente.
In tale direzione può aiutare il fatto che ad oggi non abbiamo nessuna caratterizzazione delle partizioni P di Pref(L) per cui esiste un automa P-sortable. Notare che un tale risultato potrebbe anche implicare un bound al numero di "automi minimi" in funzione della width

§ PROOFS OF SECTION <REF>

Let us provide more details about Example <ref>.

*Example <ref>.
Consider the DFA $ \mathcal{A}_1 $ on the left of Figure  <ref> and let $ \mathcal{L} = \mathcal{L}(\mathcal{A}_1) $. Then, $ \mathcal{A}_1 $ is a minimum DFA with states $0, \ldots,5$ and $I_0=\{\epsilon\}$, $I_1=\{ac^*\}$, $I_2=\{bc^*\}$, $I_3=\{ac^*d, gd,  ee,he, f,k \}$, $I_4=\{e,h\}$, $I_5=\{g\}$. States $1 $ and $ 2 $ are $\preceq_{\mt A}$-incomparable because $a\in I_1, b\in I_2, ac\in I_1$ and $a\prec b\prec ac$.
Similarly one checks that states $3,4,5$ are pairwise  $\preceq_{\mt A}$-incomparable. On the other hand, $0$ is the minimum and states $1,2$ precede states $3,4,5 $ in the order $\preceq_{\mt A}$. We conclude:

\begin{equation*}
\preceq_{\mt A}=\{(0,1),(0,2), (0,3), (0,4), (0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)\} \cup \{(i, i) \;|\; 0 \le i \le 5 \}\}.
\end{equation*}

The width of the DFA is $ 3 $  because $ \{3, 4, 5 \} $ is the largest $ \preceq_\mathcal{A} $-antichain. A $ \preceq_\mathcal{A} $-chain partition of cardinality $ 3 $ is, for example, $ \{\{0, 1, 3 \}, \{2, 4 \}, \{5 \} \} $.

Let us prove that $ width(\mathcal{L}) \ge 2 $. Suppose by contradiction that there exists a   DFA $\mt B$ of width $1$    recognizing  $\mt L $. Then, the order $\preceq_{\mt B}$ is  total. Moreover,  there   exists a state $q$ such that two words of the infinite set
$ac^*\in \pf L$, say $ac^i, ac^j$  with $i<j$,    belong to $I_q$.
Since $ac^i\prec bc^i\prec ac^{i+1}$ with
$bc^i\in \pf L$ and
$bc^i\not \equiv_{\mt L} ac^{i+1}$ it follows that $bc^i\not \in I_q$. If $q'$ is such that $bc^i\in I_{q'}$ we have
that $q$ and $q'$ are $\preceq_{\mt B}$-incomparable, a contradiction.

Finally, let $ \mathcal{A}_2 $ be the DFA in the center of Figure  <ref> and let $ \mathcal{A}_3 $ be the DFA on the right of Figure  <ref>. Notice that $ \mathcal{L}(\mathcal{A}_2) = \mathcal{L}(\mathcal{A}_3) = \mathcal{L} $, and $ \mathcal{A}_2 $ and $ \mathcal{A}_3 $ have just one more state than $ \mathcal{A}_1 $ and are non-isomorphic. We know that $ \mathcal{A}_2 $ and $ \mathcal{A}_3 $ cannot have width equal to 1. On the other hand, they both have width 2, as witnessed by $\{ \{0,1,4\}, \{2,3 ,5, 3' \} \}$ (for $ \mathcal{A}_2 $) and $ \{ \{0,1,3\}, \{2,4, 5, 4' \}\} $ (for $ \mathcal{A}_3 $).

*Example <ref>.
Let $\mt A$ be the minimum DFA $\mt A$ of  Example <ref>. We know that $\text{width}(\mt A)=3$.   On the other hand, if $\mt L=\mt L ({\mt A})$, then $\text{width}(\mt L)=2$. Indeed:

* The   automata in Figure <ref> recognize $\mt L$ and both   have width two, because: the chain partition $ \{ \{0,1,3\}, \{2,4, 5, 4' \}\} $ witnesses that the DFA on the right has width 2; similarly, the chain partition $\{ \{0,1,4\}, \{2,3 ,5, 3' \} \}$ witnesses that the DFA on the left has width 2.

* Suppose by contradiction that there exists a   DFA $\mt B$ of width $1$    recognizing  $\mt L $. Then, the order $\preceq_{\mt B}$ is  total. Moreover,  there   exists a state $q$ such that two words of the infinite set
$ac^*\in \pf L$, say $ac^i, ac^j$  with $i<j$,    belong to $I_q$.
Since $ac^i\prec bc^i\prec ac^{i+1}$ with
$bc^i\in \pf L$ and
$bc^i\not \equiv_{\mt L} ac^{i+1}$ it follows that $bc^i\not \in I_q$. If $q'$ is such that $bc^i\in I_{q'}$ we have
that $q$ and $q'$ are $\preceq_{\mt B}$-incomparable, a contradiction.

Here is the proof of Lemma <ref>.

*Statement of Lemma <ref>.
If  $\mathcal A $ is the minimum   DFA recognizing $\mathcal L$ then
$\text{ent}(\mathcal A)= \text{ent}(\mathcal L)$.

We prove that $\text{ent}(\mathcal A)\leq \text{ent}(\mathcal B)$, for any  $\mathcal B$ equivalent to $\mathcal A $. Suppose $q_1, \ldots, q_k$ are pairwise distinct states which are    entangled in $\mathcal A $, witnessed by the monotone sequence $(\alpha_i)_{i\in \mathbb N}$. Since $\mathcal A$ is minimum, each  $I_{q_j}$ is a union of a finite number of  $I_u$, with $u\in Q_{\mt B}$.
The monotone sequence $(\alpha_i)_{i\in \mathbb N}$
goes through $q_j$ infinitely often,  so there must be a state $u_j\in Q_{\mt B}$ such that $I_{u_j}\subseteq I_{q_j}$ and  $(\alpha_i)_{i\in \mathbb N}$
goes through $u_j$ infinitely often.
Then  $(\alpha_i)_{i\in \mathbb N}$ goes through the pairwise distinct states $u_1,\ldots, u_k$ infinitely often  and $u_1, \ldots, u_k$  are entangled in  $\mathcal B$.

§.§ The minimum-size entangled convex  decomposition

This section is devoted to the proof of Theorem <ref>, which will follow from a general result valid for an arbitrary linear order. From now on, we fix a linear order $ (Z, \le) $ and a finite partition $ \mathcal P = \{ P_{1}, \ldots , P_{m}\} $ of $ Z $. Theorem <ref> will follow by letting $ (Z, \le) = (Pref(\mathcal{L(B)}, \preceq) $ and $ \mathcal{P} = \{I_q | q \in Q \} $.

It is convenient to think of  $\mathcal P$ as an alphabet from which we can generate finite or infinite strings. A finite string $P_{ 1}\ldots P_{ k} \in \mathcal P^{*}$  is said to be generated by  $X \subseteq Z $, if there exists a  sequence $x_{1}\leq\ldots  \leq x_{k}$  of elements in $X$   such that
$x_{j}\in P_{j}$, for all $j=1, \ldots,k$.
In these hypotheses, we also say that $P_{ 1}\ldots P_{ k} $ occurs in $ X $  at  $x_{1}, \ldots, x_{k}$.
Similarly,  an infinite string  $P_{1}\ldots P_{k} \ldots   \in \mathcal P^{\omega}$ is  generated by  $X \subseteq Z $ if there exists  a monotone  sequence  $(x_i)_{i\in \mathbb N}$  of elements in $X$   such that
$x_{j}\in P_{j}$, for all  $j\in \mathbb N$.

We can now generalize Definition <ref>.

Let $ (Z, \le) $ be a total order, and let $ \mathcal{P} $ be a partition of $ Z $. Let $ X \subseteq Z $.

* We define $\mathcal P_{X}=\{P\in \mathcal P : P \cap X\neq\emptyset\}$.

* If $\mathcal P'=\{P_1, \ldots, P_m\}\subseteq \mathcal P$, we say that $\mathcal P'$ is  entangled in $X$   if the infinite string $(P_1, \ldots, P_m)^\omega$ is generated by $X$.

* We say that $ X $ is entangled if $ \mathcal P_{X}$ is entangled in $ X $.

The property of being entangled is captured by an infinite string $(P_1, \ldots, P_m)^\omega$. Let us prove that, in fact, arbitrary long strings express the same property.

Let $ (Z, \le) $ be a total order, and let $ \mathcal{P} $ be a partition of $ Z $. Let $ X \subseteq Z $, and let $ \mathcal P'=\{P_1, \ldots, P_m\}\subseteq \mathcal P$. The following are equivalent:

* For every $k\in \mathbb N$, the string $ (P_1, \ldots, P_m)^k$ is generated by $X$.

* $ (P_1, \ldots, P_m)^\omega $ is generated by $ X $

The nontrivial implication is $ (1) \rightarrow (2) $. If $ m = 1 $ the conclusion is immediate, so we can assume $ m \ge 2 $. Let  $ \alpha_k = (x^k_1, \dots, x^k_{mk}) $ be an increasing sequence witnessing that $ (P_{1} \cdots P_{m})^{k} $ occurs in $ X $.
We distinguish two cases:

* There exists an integer $ i_0 $ such that for every integer $ i > i_0 $ and for every integer $ r $ such that $ x_i^r $ is defined there exists an integer $ h(i, r) $ such that $ x^{h(i, r)}_{i + 1} $ is defined and $ x^{h(i, r)}_{i + 1} < x^{r}_{i} $. Let $ i > i_0 $ be such that $ x_i^r \in P_1 $ for every $ r $ such that $ x_i^r $ is defined, fix any such $ r $, and define $ r_{i} := r $. Now, for $ j > i $, define recursively $ r_{j + 1} := h(j, r_j) $. Then, the sequence $ x_{i}^{r_i} $, $ x_{i + 1}^{r_{i + 1}}$, $ x_{i + 2}^{r_{i + 2}} $, $ \dots $ is a decreasing sequence in $ X $ witnessing that $ (P_{1} \cdots P_{m})^{\omega} $ is generated by $ X $.

* For every integer $ i_0 $ there exists an integer $ i > i_0 $ and there exists an integer $ r(i_0) $ such that $ x^{r(i_0)}_{i} $ is defined and for every integer $ h $ for which $ x^{h}_{i + 1} $ is defined it holds $ x^{h}_{i + 1} > x^{r(i_0)}_{i} $ (equality cannot hold because $ m \ge 2$ ). Now, fix $ i_0 = 1 $ and call $ i_1 $ the correspondent $ i > i_0 $. Next, consider $ i_1 $ and call $ i_2 $ the correspondent $ i > i_1 $, and so on. Hence $ i_1 < i_2 < i_3 < \dots $. Consider the sequence $ x_1^{r(i_0)} $, $ x_2^{r(i_0)} $, $ \dots $, $ x_{i_1 - 1}^{r(i_0)} $, $ x_{i_1}^{r(i_0)} $, $ x_{i_1 + 1}^{r(i_1)} $, $ x_{i_1 + 2}^{r(i_1)} $, $ \dots $, $ x_{i_2 -1 }^{r(i_1)} $, $ x_{i_2}^{r(i_1)} $, $ x_{i_2 + 1}^{r(i_2)} $, $ x_{i_2 + 2}^{r(i_2)} $, $ \dots $, $ x_{i_3 -1 }^{r(i_2)} $, $ x_{i_3}^{r(i_2)} $, $ x_{i_3 + 1}^{r(i_3)} $, $ \dots $. We claim that this is an increasing sequence in $ X $ witnessing that $ (P_{1} \cdots P_{m})^{\omega} $ is generated by $ X $. First, notice that all $ x_i^k $'s in the sequence are defined (that is, it actually holds $ i \le mk $ ) because we know that $ x_{i_1}^{r(i_0)} $, $ x_{i_2}^{r(i_1)} $, $ \dots $ are defined. Moreover, since the subscripts of the sequence are $ 1 $, $ 2 $, $ 3 $, $ \dots $, then the sequence witnesses that $ (P_1, \dots, P_m)^\omega $ occurs in $ X $, if we prove that it is monotone. Let us prove that this sequence is increasing. The subsequence $ x_1^{r(i_0)} $, $ x_2^{r(i_0)} $, $ \dots $, $ x_{i_1 - 1}^{r(i_0)} $, $ x_{i_1}^{r(i_0)} $ is increasing because it is contained in $ \alpha_{r(i_0)} $, the subsequence $ x_{i_1 + 1}^{r(i_1)} $, $ x_{i_1 + 2}^{r(i_1)} $, $ \dots $, $ x_{i_2 -1 }^{r(i_1)} $, $ x_{i_2}^{r(i_1)} $ is increasing because it is contained in $ \alpha_{r(i_1)} $, and so on. Finally, $ x_{i_1}^{r(i_0)} < x_{i_1 + 1}^{r(i_1)} $, $ x_{i_2}^{r(i_1)} < x_{i_2 + 1}^{r(i_2)} $ and so on by the definition of $ i_1 $, $ i_2 $, $ \dots $.

Let us generalize the definition of e.c. decomposition given in Section <ref> for DFAs.

Let $ (Z, \le) $ be a total order, and let $ \mathcal{P} $ a partition of $ Z $. We say that a partition  $ \mathcal V  $ of $Z$ is an e.c. decomposition of $ \mathcal P$ in $(Z,\leq)$ if
all elements of $ \mathcal V  $ are entangled and convex in $ (Z, \le) $.

Consider $ (\mathbb{Z}, \le) $, where $\mathbb Z$ is the set of all integers and $ \le $ is the usual order on $\mathbb Z$. Let $\mathcal P=\{P_1,P_2,P_3\}$ the partition of $ \mathbb{Z} $ defined as follows:

\begin{align*}
& P_1=\{n \leq 0 : n \text{~ is odd}\} \cup \{n >  0 : n \equiv 1 ~\text{mod } 3\}&\\
&  P_2=\{n\leq 0 : n \text{~ is even}\}  \cup \{n >  0 : n \equiv 2 ~\text{mod } 3\} , &\\
&P_3=\{n >  0 : n \equiv 0 ~\text{mod } 3\} &
\end{align*}

The partition $\mathcal P$ generate the following trace  over $\mathbb Z$:

\[\ldots P_1P_2P_1P_2 \ldots P_1P_2 P_1P_2P_3P_1P_2P_3\ldots\]

Now define $\mt V=\{V_1,V_2\}$, where
$V_1=\{n\in \mathcal Z : n\leq 0\}$, $V_2=\{n\in \mathcal Z : n>0\}$. It is immediate to check that $ \mathcal{V} $ is an e.c. decomposition of $ \mathcal{P} $ in $ (\mathbb{Z}, \le) $. More trivially, even $\mt V'=\{\mathbb Z\}$ is an e.c. decomposition of $\mathcal P$ in $ (\mathbb{Z}, \le) $.

Let $ (Z, \le) $ be a total order, and let $ \mathcal{P} $ a partition of $ Z $. Notice that $ \mathcal{V} = \{\{z\} | z \in Z \} $ is an e.c. decomposition of $ \mathcal{P} $ in $ (\mathbb{Z}, \le) $. However, if $ Z $ is an infinite set, then $ \mathcal{V} $ is an infinite e.c. decomposition. The main result of this section is that if $ \mathcal{P} $ is a finite partition, then there exists a finite e.c. decomposition of $ \mathcal{P} $ in $ (\mathbb{Z}, \le) $ even when $ Z $ is an infinite set.

Let $ (Z, \le) $ be a total order, and let $ \mathcal{P} = \{P_1, \dots, P_m \} $ be a finite partition of $ Z $. Then, $ \mathcal{P} $ admits a finite e.c. decomposition in $ (Z, \le) $.

We proceed by induction on $ m = |\mathcal{P} | $. If $ m = 1 $, then $ \mathcal{P} = \{Z \} $, so $ \{Z \} $ is an e.c. decomposition of $ \mathcal{P} $ in $ (Z, \le) $. Now assume $ m \ge 2 $. If $ (P_1, \dots, P_m)^\omega $ is generated by $ Z $, then again $ \{Z \} $ is an e.c. decomposition of $ \mathcal{P} $ in $ (Z, \le) $. Otherwise, let $ \pi $ any permutation of the set $ \{1, \dots, m \} $. Since $ (P_1, \dots, P_m)^\omega $ is not generated by $ Z $, then $ (P_{\pi (1)}, \dots, P_{\pi (m)})^\omega $ is not generated by $ Z $, hence by Lemma <ref> there exists an integer $ s_\pi $ such that $ (P_{\pi (1)}, \dots, P_{\pi (m)})^{s_\pi}$ is not generated by $ Z $. Now, consider the following procedure:
[1]
$t \leftarrow 1; Z_{1} \leftarrow Z; \mathcal V \leftarrow \{Z_{1}\}$;
initialise the partition
$ \pi $ being a permutation of $ \{1, \dots, m \}$
$\exists Z_{i} \in \mathcal V$ generating $ (P_{\pi(1)}\cdots P_{\pi(m)})^{2} $
let $ \alpha_{1}  < \cdots < \alpha_{m}  < \alpha_{1}' < \cdots < \alpha_{m}' $ in $ Z_{i} $ be such that $\alpha_{j}, \alpha_{j}' \in P_{\pi(j)}$;
$   Z_{i} \leftarrow \{ \alpha \in Z_{i}\ | \ \alpha \leq \alpha_{m}\}$;
$   Z_{t+1} \leftarrow \{ \alpha \in Z_{i}\ | \ \alpha > \alpha_{m}\}$;
$ \mathcal V \leftarrow \mathcal V \cup \{Z_{t+1}\} $;
$ t \leftarrow t+1 $;
$\mathcal V$

The procedure starts from $ \mathcal{V} = \{Z \} $, and recursively partitions one element from $ \mathcal{V} $ into two nonempty convex subsets as long as $ (P_{\pi (1)}, \dots, P_{\pi (m)})^2 $ occurs in the considered element. Notice the procedure ends after at most $ \sum_{\pi} s_\pi $ iterations, returning a finite partition $ \mathcal{V} $ of $ Z $ into convex sets such that every $ V \in \mathcal{V} $ has the property that for every permutation $ \pi $ the string $ (P_{\pi (1)}, \dots, P_{\pi (m)})^2 $ does not occur in $ V $. It will suffice to prove that for every $ V \in \mathcal{V} $ the partition $ \{P \cap V |P \in \mathcal{P}_V \} $ of $ V $ (whose cardinality is at most $ m $) admits a finite e.c. decomposition in $ (V, \le) $, because then we will obtain a finite e.c. decomposition of $ \mathcal{P} $ in $ (Z, \le) $ by merging the decompositions obtained for each $ V $.

Fix $ V \in \mathcal{V} $. If $ |\{P \cap V |P \in \mathcal{P}_V \}| < m $, the conclusion follows by the inductive hypothesis. Now assume $ |\{P \cap V |P \in \mathcal{P}_V \}| = m $. It will suffice to prove the following: if $ (Z, \le) $ is a total order, and $ \mathcal{P} = \{P_1, \dots, P_m \} $ is a finite partition of $ Z $ such that for every permutation $ \pi $ of $ \{1, \dots, m \} $ the string $ (P_{\pi (1)}, \dots, P_{\pi (m)})^2 $ does not occur in $ Z $, then $ \mathcal{P} $ admits a finite e.c. decomposition in $ (Z, \le) $.

Let $ k \ge 1 $ be the number of distinct permutations $ \pi $ of $ \{1, \dots, m \} $ such that $ (P_{\pi (1)}, \dots, P_{\pi (m)}) $ occurs in $ Z $. We proceed by induction on $ k $. If $ k = 1 $, then each set $ Z \cap P_j $ is convex and trivially entangled, so $ \{Z \cap P_j | 1 \le j \le m \} $ is an e.c. decomposition of $ \mathcal{P} $ in $ (Z, \le) $. Now assume $ k \ge 2 $. Let $ \pi_0 $ be a permutation such that $ (P_{\pi_0 (1)}, \dots, P_{\pi_0 (m)}) $ occurs in $ Z $. Define:

\begin{equation*}
Z_1 = \{\alpha \in Z | \text{$ \exists \alpha_1, \dots, \alpha_m $ with $ \alpha \le \alpha_1 < \dots \alpha_m $ and $ \alpha_i \in P_{\pi_0 (i)}$ \}}
\end{equation*}

and $ Z_2 = Z \setminus Z_1 $. Notice that $ Z_1 $ is nonempty because $ (P_{\pi_0 (1)}, \dots, P_{\pi_0 (m)}) $ occurs in $ Z $. Let us prove that $ (P_{\pi_0 (1)}, \dots, P_{\pi_0 (m)})) $ does not occur in $ Z_1 $ nor in $ Z_2 $, and that $ Z_2 $ is nonempty. Just observe that if $ \alpha_1, \dots, \dots \alpha_m $ is a witness for $ (P_{\pi_0 (1)}, \dots, P_{\pi_0 (m)}) $ in $ Z $, then $ \alpha_1 \in Z_1 $, but $ \alpha_m \in Z_2 $, otherwise $ (P_{\pi_0 (1)}, \dots, P_{\pi_0 (m)})^2 $ would occur in $ Z $. Moreover $ Z_1 $ and $ Z_2 $ are convex. It will suffice to prove that $ \{P \cap Z_i | P \in \mathcal{P}_{Z_i} \} $ admits a finite e.c. decomposition in $ (Z_i, \le) $, for $ i = 1, 2 $, because then (once again) we will only have to merge the two partitions. Fix $ i $. If $ |\{P \cap Z_i | P \in \mathcal{P}_{Z_i} \}| < m $, we conclude by the inductive hypothesis on $ m $. If $ |\{P \cap Z_i | P \in \mathcal{P}_{Z_i} \}| = m $, we conclude by the inductive hypothesis on $ k $: if $ k_i $ is the number of distinct permutations $ \pi $ of $ \{1, \dots, m \} $ such that $ (P_{\pi (1)}, \dots, P_{\pi (m)}) $ occurs in $ Z $, then $ k_i < k $, because $ (P_{\pi_0 (1)}, \dots, P_{\pi_0(m)})) $ occurs in $ Z $ but not in $ Z_i $.

Theorem <ref> follows by picking $ (Z, \le) = (Pref (\mathcal{L(B)}), \preceq) $ and $ \mathcal{P} = \{I_q | q \in Q \} $.

We say that an e.c. decomposition of $ \mathcal{P} $ in $ (Z, \le) $ is a minimum-size e.c. decomposition if it has minimum cardinality among all e.c. decompositions of $ \mathcal{P} $ in $ (Z, \le) $. We will be interested in minimum-size e.c. decompositions because they ensure  additional properties.

Let $ (Z, \le) $ be a total order, let $ \mathcal{P} = \{P_{1}, \ldots, P_{m} \} $ be a finite partition of $ Z $, and let $ \mathcal V= \{V_{1}, \ldots , V_{r} \}$ be a minimum-size e.c. decomposition of $ \mathcal{P} $ in $ (Z, \le) $.
Then, for every $1\leq i<r$, we have $\mathcal P_{V_i}\not \subseteq  \mathcal P_{V_{i+1}}$, because otherwise $ \mathcal V'= \{V_{1}, \ldots , V_{i-1}, V_i\cup V_{i+1}, \ldots V_{r} \}$ would be an e.c. decomposition of $ \mathcal{P} $ in $ (Z, \le) $ having smaller cardinality. Similarly, for every $ 1< i\leq r $, it must be $\mathcal P_{V_i}\not \subseteq  \mathcal P_{V_{i-1}}$. In other words, for every $ i = 1, \dots, r $ there exist $ P_i \in \mathcal{P}_{V_i} \setminus \mathcal{P}_{V_{i + 1}}$ and $ P'_i \in \mathcal{P}_{V_i} \setminus \mathcal{P}_{V_{i - 1}} $, where we assume $ V_0 = V_{r + 1} = \emptyset $.

In the special case of Remark <ref> we conclude that for every $ i = 1, \dots, r $ there exists a state $ q_i $ that occurs in $ V_i $ but not in $ V_{i + 1} $ and a state $ q'_i $ that occurs in $ V_i $ but not in $ V_{i - 1} $.

In general, a minimum-size e.c. decomposition is not unique.

Let $ Z $ be the disjoint union of some infinite sets:

\begin{align*}
P_1 & = \{\alpha, \alpha_1, \alpha_2, \dots, \}; \\
P_2 & = \{\beta, \beta_1, \beta_2, \dots, \beta'_1, \beta'_2, \dots, \}; \\
P_3 & = \{\gamma_1, \gamma_2, \dots \}. \\
\end{align*}

Let $ \le $ be the total order on $ Z $ such that:

\begin{equation*}
\alpha_1 < \beta_1 < \alpha_2 < \beta_2 < \dots < \alpha < \beta < \gamma_1 < \beta'_1 < \gamma_2 < \beta'_2 < \dots
\end{equation*}

Let $ \mathcal{P} = \{P_1, P_2, P_3 \} $. Then, two distinct minimum-size e.c. decompositions of $ \mathcal{P} $ in $ (Z, \le) $ are:

* $ \mathcal{V} = \{\{\alpha_1,  \beta_1,\alpha_2, \beta_2, \dots, \alpha, \beta \}, \{\gamma_1, \beta'_1, \gamma_2, \beta'_2, \dots\}\} $;

* $ \mathcal{V'} = \{\{\alpha_1,  \beta_1, \alpha_2, \beta_2, \dots, \alpha \}, \{\beta, \gamma_1, \beta'_1, \gamma_2, \beta'_2, \dots\}\} $.

Let us show that even in the special case of Remark <ref> minimum-size e.c. decompositions need not be unique.

Notice that a DFA can have  more than one minimum-size e.c. decomposition: in Figure <ref> we see a DFA for which both $\{\{\epsilon\}, V_1,V_2\}$ and $\{\{\epsilon\},V_1',V_2'\}$ are minimum-size e.c. decomposition, where

\begin{align*}
V_1&=ac^*\cup bc^*      &  V_2&=[b(c+d)^*\setminus bc^*]\cup f(c+d)^*\cup gd^*\\
V_1'&=ac^*\cup b(c+d)^*\cup [f(c+d)^*\setminus fd^*]
&  V_2'&= fd^*\cup gd^*,\\
\end{align*}

the states occurring in $V_1, V_1'$ are $1,2$ and the states occurring in $V_2,V_2'$ are $2,3$.

Consider the DFA $ \mathcal{B} $ in figure <ref>. Notice that in every e.c. decomposition of $ \mathcal{B} $ one element is $ \{\epsilon \} $, because $ I_0 = \{\epsilon \} $. Moreover, every e.c. decomposition of $ \mathcal{B} $ must have cardinality at least three, because $ I_1 \prec I_3 $. It is easy to check that:

\begin{equation*}
\mathcal{V} = \{\{\epsilon \}, \{ac^*\cup bc^*\}, \{[b(c+d)^*\setminus bc^*]\cup f(c+d)^*\cup gd^*\}   \}
\end{equation*}

\begin{equation*}
\mathcal{V}' = \{\{\epsilon \}, \{ac^*\cup b(c+d)^*\cup [f(c+d)^*\setminus fd^*]\}, \{fd^*\cup gd^*\}\}
\end{equation*}

are two distinct minimum-size e.c. decompositions of $ \mathcal{B} $.

[->,>=stealth', semithick, auto, scale=1]

[state, initial] (0)    at (0,0)	$0$;
[state, accepting,label=above:] (1)    at (0,2)	$1$;
[state,accepting, label=above:] (2)    at (0,-2)	$2$;
[state, accepting,label=above:] (3)    at (2,0)	$3$;
(0) edge [] node [] $a$ (1);
(0) edge [] node [] $b,f$ (2);
(0) edge [] node [below] $g$ (3);
(1) edge  [loop above] node $c$ (1);
(2) edge  [loop below] node $c,d$ (2);
(3) edge  [loop above] node $d$ (3);

An automaton $\mt B$ admitting two distinct minimum-size e.c. decompositions.

§.§ Versione vecchia

In this appendix we prove Theorem <ref>.
Since the result is a general combinatorial property  on finite partitions over a   total order, we prove it in full generality and obtain Theorem <ref>  as a corollary (Corollary <ref>).

We fix  a finite partition   $ \mathcal P = \{ P_{1}, \ldots , P_{m}\} $   of the domain      of a total order $(Z,\leq)$. When using the results of this appendix in Section <ref>, the set   $(Z,\leq) $ will be $ (\pff{ L}, \preceq)$ and  $ \mathcal P $ will be    $ \{I_{q}\ |\ q \in Q \} $.
It is convenient to think of  $\mathcal P$ as an alphabet from which we can write finite or infinite  “strings”.
A  finite    string $P_{ 1}\ldots P_{ k} \in \mathcal P^{*}$  is said to be generated by  $X \subseteq Z $, if there exists a  sequence $x_{1}\leq\ldots  \leq x_{k}$  of elements in $X$   such that
$x_{j}\in P_{j}$, for all $j=1, \ldots,k$.
In these hypotheses we also say that the sequence $x_{1}, \ldots, x_{k}$ of the $x_{i}$'s is labelled by $P_{ 1}\ldots P_{ k}$ and that    $P_{ 1}\ldots P_{ k} $ occurs in $ X $  at  $x_{1}, \ldots, x_{k}$.
Similarly,  an infinite string  $P_{1}\ldots P_{k} \ldots   \in \mathcal P^{\omega}$ is  generated by  $X \subseteq Z $ if there exists  a monotone  sequence  $(x_i)_{i\in \mathbb N}$  of elements in $X$   such that
$x_{j}\in P_{j}$, for all  $j\in \mathbb N$.

Consider  a subset $\{P_1, \ldots, P_m\}\subseteq \mathcal P$ and $ X \subseteq Z$.
The following are equivalent:

* all finite strings
$(P_1P_2\ldots P_m)^k$, for $k\in \mathbb N$,  occur in $X$;

* for all $k\in \mathbb N$ there exists a permutation $\pi$  of $\{1, \ldots, m\}$, such that     the   string  $(P_{\pi(1)}P_{\pi(2)}\ldots P_{\pi(m)})^k$   occurs in $X$.

Moreover, notice that  an  infinite string  $(P_{ 1}\ldots P_{m})^\omega     \in \mathcal P^{\omega}$ occurs in $X$ if and only if there is a monotone  sequence $(x_i)_{i\in \mathbb N}$  of elements in $X$ going through each $P_{j}$ infinitely many times, for $j=1, \ldots,m$. Lo so che è equivalente, ma scritto così non va bene, bisogna dire che la sequenza va nell'ordine in $ P_1, P_2, P_3, \dots $

If  $\mathcal P$   is  a finite partition of a total order $(Z,\leq)$ and     $X\subseteq Z$, we define $\mathcal P_{X}=\{P\in \mathcal P : P \cap X\neq\emptyset\}$. Moreover,
if $\mathcal P'=\{P_1, \ldots, P_m\}\subseteq \mathcal P$,   we say that:

* $\mathcal P'$ is  entangled in $X$   if   the string
$(P_1, \ldots, P_m)^\omega$ is generated by $X$, that is, if  there is a monotone sequence $(x_i)_{i\in \mathbb N}$ of elements in $X$
going  through each element in $\mathcal P'$ infinitely many times.

* $X$ is   entangled if the set $\mathcal P_{X}$ is entangled.

While the  following lemma is easily proved if  the order type of $Z$ is $\omega$, the same holds also for any order type, as stated   below.

Let  $X\subseteq Z$ with  $\mt P_X=\{P_1, \ldots, P_m\}$ be such that for all $k\in \mathbb N$, the string
$(P_1, \ldots, P_m)^k$ is generated by $X$. Then $X$   is entangled.

Let $\mathcal P=\{P_1, \ldots, P_n\}$.
If $ n = 1 $ the conclusion is trivial, so we can assume $ n \ge 2 $. Let $\mathcal P'=\{P'_{1} \cdots P'_{n}\}=\mathcal P_{X}$ and let  $ \alpha_k = (x^k_1, \dots, x^k_{nk}) $ denote any increasing sequence witnessing that $ (P'_{1} \cdots P'_{n})^{k} $ occurs in $ X $.
We distinguish two cases:

* There exists an integer $ i_0 $ such that for every integer $ i > i_0 $ and for every integer $ r $ such that $ x_i^r $ is defined there exists an integer $ h(i, r) $ such that $ x^{h(i, r)}_{i + 1} $ is defined and $ x^{h(i, r)}_{i + 1} < x^{r}_{i} $. Let $ i > i_0 $ be such that $ x_i^r $ is labeled $ P'_1 $ for every $ r $ such that $ x_i^r $ is defined, fix any such $ r $, and define $ r_{i} := r $. Now, for $ j > i $, define recursively $ r_{j + 1} := h(j, r_j) $. Then, the sequence $ x_{i}^{r_i} $, $ x_{i + 1}^{r_{i + 1}}$, $ x_{i + 2}^{r_{i + 2}} $, $ \dots $ is a decreasing sequence in $ X $ that generates $ (P'_{1} \cdots P'_{n})^{\omega} $.

* For every integer $ i_0 $ there exists an integer $ i > i_0 $ and there exists an integer $ r(i_0) $ such that $ x^{r(i_0)}_{i} $ is defined and for every integer $ h $ for which $ x^{h}_{i + 1} $ is defined it holds $ x^{h}_{i + 1} > x^{r(i_0)}_{i} $ (equality cannot hold because $ n \ge 2$ ). Now, fix $ i_0 = 1 $ and call $ i_1 $ the correspondent $ i > i_0 $. Next, consider $ i_1 $ and call $ i_2 $ the correspondent $ i > i_1 $, and so on. Hence $ i_1 < i_2 < i_3 < \dots $. Consider the sequence $ x_1^{r(i_0)} $, $ x_2^{r(i_0)} $, $ \dots $, $ x_{i_1 - 1}^{r(i_0)} $, $ x_{i_1}^{r(i_0)} $, $ x_{i_1 + 1}^{r(i_1)} $, $ x_{i_1 + 2}^{r(i_1)} $, $ \dots $, $ x_{i_2 -1 }^{r(i_1)} $, $ x_{i_2}^{r(i_1)} $, $ x_{i_2 + 1}^{r(i_2)} $, $ x_{i_2 + 2}^{r(i_2)} $, $ \dots $, $ x_{i_3 -1 }^{r(i_2)} $, $ x_{i_3}^{r(i_2)} $, $ x_{i_3 + 1}^{r(i_3)} $, $ \dots $. We claim that this is an increasing sequence in $ X $ that generates $ (P'_{1} \cdots P'_{n})^{\omega} $. First, notice that all $ x_i^k $'s in the sequence are defined (that is, it actually holds $ i \le nk $ ) because we know that $ x_{i_1}^{r(i_0)} $, $ x_{i_2}^{r(i_1)} $, $ \dots $ are defined. Moreover, since the subscripts of the sequence are $ 1 $, $ 2 $, $ 3 $, then the sequence is labeled $ (P'_1, \dots, P'_n)^\omega $. Hence, we are only left with proving that the sequence is increasing. The subsequence $ x_1^{r(i_0)} $, $ x_2^{r(i_0)} $, $ \dots $, $ x_{i_1 - 1}^{r(i_0)} $, $ x_{i_1}^{r(i_0)} $ is increasing because it is contained in $ \alpha_{r(i_0)} $, the subsequence $ x_{i_1 + 1}^{r(i_1)} $, $ x_{i_1 + 2}^{r(i_1)} $, $ \dots $, $ x_{i_2 -1 }^{r(i_1)} $, $ x_{i_2}^{r(i_1)} $ is increasing because it is contained in $ \alpha_{r(i_1)} $, and so on. Finally, $ x_{i_1}^{r(i_0)} < x_{i_1 + 1}^{r(i_1)} $, $ x_{i_2}^{r(i_1)} < x_{i_2 + 1}^{r(i_2)} $ and so on by the definition of $ i_1 $, $ i_2 $, $ \dots $.

We say that a finite partition  $ \mathcal V  $ of $Z$ is a finite e.c. decomposition of $ \mathcal P$ in $(Z,\leq)$ if
all elements of $ \mathcal V  $ are convex (w.r.t. $\leq$) and  entangled   w.r.t. $\mt P$, that is,  there is a monotone sequence $(x_i)_{i\in \mathbb N}$   in $(Z,\leq)$
going  through each element in $\mathcal P_V$ infinitely many times.

It is easy to see that every partition $\mt P$ over a  finite order $(Z,\leq)$ always admits a finite e.c. decomposition, since singleton subsets of $Z$ are   convex and entangled
(considering a constant sequence  as witnessing sequence). Similarly if $(Z, \leq)$ is an arbitrary order and $|\mt P|=1$.

Let $(Z,\leq)$ be the set of the integers $\mathbb Z$ with the natural order, and let $\mathcal P=\{P_1,P_2,P_3\}$ defined as follows:

\begin{align*}
& P_1=\{n \leq 0 : n \text{~ is odd}\} \cup \{n >  0 : n \equiv 1 ~\text{mod } 3\}&\\
&  P_2=\{n\leq 0 : n \text{~ is even}\}  \cup \{n >  0 : n \equiv 2 ~\text{mod } 3\} , &\\
&P_3=\{n >  0 : n \equiv 0 ~\text{mod } 3\} &
\end{align*}

The partition $\mathcal P$ generate the following  trace  over $\mathbb Z$:

\[\ldots P_1P_2P_1P_2 \ldots P_1P_2 P_1P_2P_3P_1P_2P_3\ldots\]

If   $\mt V=\{V_1,V_2\}$, where
$V_1=\{n\in \mathcal Z : n\leq 0\}$, $V_2=\{n\in \mathcal Z : n>0\}$, then $\mt V$ is a finite e.c. decomposition of
$\mathcal P$. Notice that $\mt V$ is not minimum-size w.r.t. cardinality, since $\mt V'=\{\mathbb Z\}$ is also a finite e.c. decomposition of $\mathcal P$.

In the following Lemma we prove that  any finite partition $\mathcal P$ of $ Z $ admits a finite e.c. decomposition (hence, there is also a minimal one w.r.t. cardinality).

Given $ \mathcal P=\{P_{1}, \ldots, P_{m}\} $ finite partition of $Z$, there exists a   finite e.c. decomposition of $ \mathcal P $ in $(Z,\leq)$.

We proceed by induction on $ m=|\mathcal P| $.

If $ m=1 $ then $ \mathcal P $  itself is a finite e.c. decomposition of $ \mathcal P $ in $ Z $ and we are done.

Assume $ m>1 $.
In the following, given   a permutation $\pi$ of $\{1, \ldots, m\}$   and a finite  string $P_{i_1}\ldots P_{i_k}\in \mathcal P^*$, we say that the  string  $P_{\pi(i_1)}\ldots P_{\pi(i_k)}$  has  type   $P_{i_1}\ldots P_{i_k}$.

We consider two possible cases:

a)  for all $k$ there is  a string  of type $ (P_{1}\cdots P_{m})^{k} $ that is generated by $Z$;

b) there exists $ s \in \nats $ such that no string of type $ (P_{1}\cdots P_{m})^{s} $ is generated by $ Z $.

In case a)  Remark <ref> and Lemma <ref> imply that $ \mathcal V=\{Z\} $ is a finite e.c. decomposition of $ \mathcal P $.

In case b), fix an order $ \pi_{1}, \ldots , \pi_{\ell} $  of all possible permutations of $ \{1, \ldots , m\} $ and let $ \pi_{1} $ be the identity.
We claim that there exists a finite convex partition $\mathcal U= \{ Z_{1}, \ldots , Z_{t} \}$ of $ Z $  such that $ t  < s $ and the string $ \left(P_{\pi_{1}(1)} \cdots P_{\pi_{1}(m)}\right)^{2}$ (that is $(P_{1} \cdots P_{m})^{2}$) is not generated by $ Z_{i} $, for all $ i \in \{ 1, \ldots , t\} $. To see this, consider the following procedure, designed simply to  keep on splitting classes containing at least two consecutive occurrences of $ P_{1}\cdots P_{m} $:

[1]
$t \leftarrow 1; Z_{1} \leftarrow Z; \mathcal U \leftarrow \{Z_{1}\}$;
initialise $ t $ and the partition $ \mathcal U $.

[invariant: $\mathcal{U}$ is convex.] $\exists Z_{i} \in \mathcal U$ generating $ (P_{1}\cdots P_{m})^{2} $
let $ \alpha_{1}  < \cdots < \alpha_{m}  < \alpha_{1}' < \cdots < \alpha_{m}' $ in $ Z_{i} $ be such that $\alpha_{j}, \alpha_{j}' \in P_{j}$;
$   Z_{i} \leftarrow \{ \alpha \in Z_{i}\ | \ \alpha \leq \alpha_{m}\}$;
$   Z_{t+1} \leftarrow \{ \alpha \in Z_{i}\ | \ \alpha > \alpha_{m}\}$;
$ \mathcal U \leftarrow \mathcal U \cup \{Z_{t+1}\} $;
both  $ Z_{i} $ and $ Z_{t+1} $ are  convex and therefore $ \mathcal U $ is convex.
$ t \leftarrow t+1 $;
$\mathcal U$

On the one hand, if $ Z$ does not   generate  $P_1\ldots P_m$,  then the procedure stops immediately producing $\mathcal U= \{ Z\}$. On the other hand, if $Z$       generates  $P_1\ldots P_m$,
at each iteration of the above procedure every class in $\mathcal U$ contains at least one occurrence of   $P_{1} \cdots P_{m}$; from       hypothesis b) it then follows that
the    procedure    stops  after $ t< s $ steps   returning a convex partition $\mathcal U=\{ Z_{1}, \ldots, Z_{t}\}$  where  $(P_{1} \cdots P_{m})^2$ does not occur in any $Z_i$.

At this point, for any $ Z_{i} $ with $ i \in \{1, \ldots , t\} $, using the same argument used for $ \pi_{1} $, we can produce a finite  convex partition $ \{ Z_{i,1}, \ldots, Z_{i,t_{i}}\} $ where in  every $ Z_{i,j} $  neither     $ \left(P_{\pi_{1}(1)} \cdots P_{\pi_{1}(m)}\right)^{2} $ nor    $ \left(P_{\pi_{2}(1)} \cdots P_{\pi_{2}(m)}\right)^{2} $ occur.

Iterating the previous argument over all permutations $ \pi_{1}, \ldots , \pi_{\ell} $, we can determine a finite convex partition $ \{U_{1}, \ldots , U_{n}\} $ of $ Z $ where  every $ U_{i} $  does not   generate    strings of type $(P_{1}\cdots P_{m})^2 $. We now proceed generating a  finite e.c. decomposition  for all $U_i$, for    $i=1, \ldots,n$.

If  $ U_{i} $ does not generate strings    of type $P_{1}\cdots P_{m}$,    there exists a proper subset  $\mathcal P'$  of $ \mathcal P $ which is a  partition  of  $ U_{i} $ and   a finite e.c. decomposition of
$\mathcal P'$  in $U_i$ can be found by induction.

If   $ U_{i} $ generates   strings of type $P_{1}\cdots P_{m}$  we proceed inductively on the number   $ k $   of different permutations $\pi$ such that the string  $ P_{\pi(1)}\cdots P_{\pi(m)} $ occurs in $ U_{i}$.

If $ k=1 $, then  the sets  $ U_{i,j} = U_i \cap P_j$ are  convex, and the  decomposition $ U_{i,1}, \ldots , U_{i,m} $  is a finite e.c. decomposition of $U_i$.

If $k>1$, assuming without loss of generality that $ P_{1}\cdots P_{m} $ occurs in $ U_{i} $, we split $ U_{i} $ in

\begin{align*}
& U^{1}_{i} = \{ \alpha \in U_{i} \ | \ \exists \beta \geq \alpha \ \text{ an occurrence of } P_{1} \cdots P_{m} ~\text{ in $U_i$ starts at } \beta \},  \\
& U^{2}_{i} = U_{i} \setminus U^{1}_{i}.
\end{align*}

Both $ U^{1}_{i} $ and  $ U^{2}_{i} $ are convex. Let $k_1,k_2$   be   the   number of different permutations $\pi$  such that $ P_{\pi(1)}\cdots P_{\pi(m)} $ occurs   in $ U^{1}_{i}, U^{2}_{i} $, respectively.    We claim that $k_1,k_2<k$,  since $ P_{1}\cdots P_{m} $ cannot occur  neither in  $ U^{1}_{i} $ nor in  $ U^{2}_{i} $. In fact, assuming that $ P_{1} \cdots P_{m} $ occurs   in $ U^{1}_{i} $, let $ \alpha \in P_{m}$ the ending position of one such occurrence. Being $ \alpha \in U^{1}_{i} $, by definition a further occurrence of  $ P_{1}\cdots P_{m} $, starting after $ \alpha $,  should be found in $ U_{i} $ and  this leads to a contradiction with the non-occurrence of   $ (P_{1}\cdots P_{m})^2 $ in $U_i$. Moreover, $ P_{1}\cdots P_{m} $ cannot occur in $ U^{2}_{i} $, since its starting position would belong to $ U^{1}_{i} $.

A e.c. decomposition of $ U^{1}_{i} $ and $ U^{2}_{i} $, whose existence follows by induction,   concludes our argument.

Finally, we obtain a e.c. decomposition of $\mathcal P$ in $(Z,<)$ by putting together the e.c. decompositions of the $U_i$'s.

Notice that the minimum-size e.c. decomposition whose existence is guaranteed by the above lemma is not unique, as shown in   the following example.

Suppose the partition in $Z$ has the form $(P_{1}P_{2})^{\omega}  P_{1}P_{2}(P_{3}P_{2})^{\omega}$. Clearly (at least) two different minimum-size decompositions, both partitioning $ Z$  in two classes, exist:

* $ (P_{1}P_{2})^{\omega} P_{1}P_{2}$ and $(P_{3}P_{2})^{\omega}$;

* $ (P_{1}P_{2})^{\omega} P_{1}$ and $P_{2}(P_{3}P_{2})^{\omega}$.

More complicated examples, involving order types higher that $ \omega $, can be easily produced.

Consider a minimum-size e.c. decomposition $ \mathcal V= \{V_{1}, \ldots , V_{r} \}$
of a finite partition $ \mathcal P=\{P_{1}, \ldots, P_{m}\} $  of $(Z, \leq)$ such that $V_{1}<V_2 < \ldots < V_{r}$.  Then, if  $1\leq i<r$,
we have $\mathcal P_{V_i}\not \subseteq  \mathcal P_{V_{i+1}}$:  otherwise,
the e.c. decomposition  $ \mathcal V= \{V_{1}, \ldots , V_{i-1}, V_i\cup V_{i+1}, \ldots V_{r} \}$     would contradict the minimum-sizeity of $\mathcal V$.
Similarly,  if  $1< i\leq r$,
we have $\mathcal P_{V_i}\not \subseteq  \mathcal P_{V_{i-1}}$.

Given a DFA $\mt B$  we can  apply Theorem <ref> with
$(Z,\leq)=(\pf {L (\mt B)}, \preceq)$ and $\mt P=\{I_q|q\in Q\}$ obtaining a proof of Theorem <ref>.

If $\mt B$ is a DFA then there exists a finite  partition $\mt V$  of $\pf {L(B)}$ whose elements  are  convex in $(\pf{L(B)}, \preceq)$ and entangled in $\mt B$.

§.§ On Some Properties of the Equivalence  $\sim$

*Statement of Lemma <ref>.
Let $ \mathcal B$ be a DFA and let $\mt V$ be a minimum-size e.c. decomposition of $ Pref (\mathcal{L(B)})$. Then, $\sim_{\mt V}$ has a finite number of classes on  $\pf {L(\mt B)}$ and
$\mt L(\mt B)$ is equal to the union of some $\sim_\mathcal{V}$-classes.

*Proof The relation $\sim_{\mt V}$ has finite index because each class is the union of some sets of the type $ V \cap I_q $, with $ V \in \mathcal{V} $ and $ q \in Q $. From the definition of $\sim_\mathcal{V}$ it follows that $\alpha\sim_\mathcal{V}\beta$ implies $\delta(s,\alpha)=\delta(s,\beta)$. Hence,   $\alpha\in \mt {L(\mt B)}$ implies  $\beta\in \mt {L(\mt B)}$, proving  that  $\mt L(\mt B)$ is equal to the union of some $\sim_\mathcal{V}$-classes.

We now prove some general results that will lead us to the proof of Lemma <ref>. The difficult implication is $ (\leftarrow) $. To this end  we will prove that without loss of generality we can assume $ C_1 \prec \dots \prec C_n $. This will follow from some results for convex and entangled sets which hold true in the general setting outlined in Definition <ref>.

Let $ (Z, \le) $ be a total order and let $ \mathcal{P} $ be a partition of $ Z $. Let $ C $ be a convex, entangled set. Assume that $ C_1 $ and $ C_2 $ are convex sets such that $C = C_1 \cup C_2 $. Then, there exists $ i \in \{1, 2 \} $ such that $ C_i $ is entangled and $ \mathcal{P}_{ C_i} = \mathcal{P}_{ C} $.

Let $ (z_i)_{i \in \mathbb{N}} $ be a monotone sequence witnessing that $ C $ is entangled. Then, at least one of the following is true:

* $ (\forall i \in \mathbb{N})(\exists j \in \mathbb{N})(j > i \land z_j \in C_1) $

* $ (\forall i \in \mathbb{N})(\exists j \in \mathbb{N})(j > i \land z_j \in C_2) $.

In the first case $ C_1 $ is entangled:   by the convexity of $C_1$, if    $ j_0 > 1 $ is such that $ z_{j_0} \in C_1 $ then  the subsequence $ (z_j)_{j \ge j_0} $ is contained in $ C_1 $ an d clearly we have $\mathcal{P}_{ C_1} = \mathcal{P}_{ C}$.  Analogously, in the second case $C_2$ is entangled and  $\mathcal{P}_{ C_2} = \mathcal{P}_{ C}$.

Let $ (Z, \le) $ be a total order and let $ \mathcal{P} $ be a partition of $ Z $. Let $ C_1, C_2 $ be convex, entangled sets. Then, at least one the following holds true:

* $ C_1 \setminus C_2 $ is a convex, entangled set and $ \mathcal{P}_{ C_1 \setminus C_2} = \mathcal{P}_{ C_1} $;

* $ C_2 \setminus C_1 $ is a convex, entangled set and $ \mathcal{P}_{ C_2 \setminus C_1} = \mathcal{P}_{ C_2} $;

* $ C_1 \cup C_2 $ is a convex, entangled set and   $ \mathcal{P}_{ C_1 \cup C_2} = \mathcal{P}_{C_1} = \mathcal{P}_{ C_2}$.

We can assume $ C_2 \not \subseteq C_1 $, $ C_1 \not \subseteq C_2 $ and $ C_1 \cap C_2 \not = \emptyset $, otherwise the conclusion is immediate (at least one of three sets is equal to $ C_1 $ or $ C_2 $).
Under these assumptions, it is easy to check that $ C_1 \setminus C_2 $, $ C_2 \setminus C_1 $, $ C_1 \cap C_2 $ and $ C_1 \cup C_2 $ are convex (but note that for example $ C_1 \setminus C_2 $ need not be convex if $ C_2 \subseteq C_1 $). Since $ C_1 = (C_1 \setminus C_2) \cup (C_1 \cap C_2) $ and $ C_2 = (C_2 \setminus C_1) \cup (C_1 \cap C_2) $, by Lemma <ref> we conclude that at least one the following holds true:

* $ C_1 \setminus C_2 $ is a convex, entangled set and $ \mathcal{P}_{C_1 \setminus C_2} = \mathcal{P}_{C_1} $;

* $ C_2 \setminus C_1 $ is a convex, entangled set and $ \mathcal{P}_{C_2 \setminus C_1} = \mathcal{P}_{C_2} $;

* $ C_1 \cap C_2 $ is a convex, entangled set and $ \mathcal{P}_{C_1 \cap C_2} = \mathcal{P}_{C_1} = \mathcal{P}_{C_2}$.

In the third case, we have $ \mathcal{P}_{C_1 \cup C_2} = \mathcal{P}_{C_1} \cup \mathcal{P}_{C_2} = \mathcal{P}_{C_1} = \mathcal{P}_{C_2} = \mathcal{P}_{C_1 \cap C_2} $. Since $C_1\cap C_2 \subseteq C_1\cup C_2$  and $C_1\cap C_2$ is entangled,   we conclude that $ C_1 \cup C_2 $ is entangled.

We can now state the result that, for $ (Z, \le) = (Pref (\mathcal{L(B)}), \preceq) $ and $ \mathcal{P} = \{I_q | q \in Q \} $, will imply that in Lemma <ref> we can assume $ C_1 \prec \dots \prec C_n $.

Let $ (Z, \le) $ be a total order and let $ \mathcal{P} $ be a partition of $ Z $. Let $ C_1, \dots, C_n $ be convex,  entangled set. Then, there exist convex, entangled sets $ C'_1, \dots, C'_m $, with $ m \le n $, such that $ C'_1 < \dots < C'_m $  and  $ \cup_{i = 1}^n C_i = \cup_{i = 1}^m C'_i $. Moreover, for every $P\in \mathcal P$ it holds $P\cap C_i\neq \emptyset$ for all $i=1, \ldots, n$ if and only if $P\cap C_i'\neq \emptyset$, for all $i=1, \ldots, m$.

We suppose, without loss of generality,  that the $C_i$'s are non-empty.
We proceed by induction on $ r = |\{(i, j)| 1 \le i < j \le n | C_i \cap C_j \not = \emptyset \}| $. If $ r = 0 $, then every two distinct $ C_i $'s are disjoint,  and since they are convex, it follows that  they are comparable;   let $ C'_1, \dots, C'_n $ be the permutation of the $ C_i $'s such that $ C'_1< \dots< C'_n $. Now assume $ r \ge 1 $. Without loss of generality, we can assume that  $ C_1 \cap C_2 \not = \emptyset $. By Lemma <ref> we know that at least one among $ C_1 \setminus C_2 $, $ C_2 \setminus C_1 $ and $ C_1 \cup C_2 $ is convex and entangled. If $ C_1 \cup C_2 $ is convex and entangled, then consider $ C_1 \cup C_2, C_3, \dots, C_n $ and   notice that the number of intersections between pairs of this sets is smaller (because if $ (C_1 \cup C_2) \cap C_i \not = \emptyset $ for some $ i \ge 3 $, then either $ C_1 \cap C_i \not = \emptyset $ or $ C_2 \cap C_i \not = \emptyset $, so either $ C_1 $  or  $ C_2 $ intersects $C_i$ in the original collection $ C_1, C_2, \dots, C_n $). Now assume that $ C_1 \setminus C_2 $ is entangled (the case $ C_2 \setminus C_1 $ analogous). Consider $ C_1 \setminus C_2, C_2, C_3, \dots, C_n $. Even in this case the number of intersections is smaller, because $ C_1 \setminus C_2 \subseteq C_1 $ and $ (C_1 \setminus C_2) \cap C_2 = \emptyset $.  In both cases Lemma <ref> implies that a $P \in \mathcal{P}$ occurs in all $C_i$'s if and only if it occurs in all elements of the new family and  we can conclude by the inductive hypothesis.

We can now tackle the proof of Lemma <ref>.

*Statement of Lemma <ref>.
Let $\mt B$ be a DFA and  let $\mt V$ be a minimum-size e.c. decomposition of $\mt B$.
Then  $\alpha \sim_{\mt V} \alpha'$
if and only if $\delta(s,\alpha)= \delta(s, \alpha')$ and   the interval $[\alpha, \alpha']^\pm$ is contained in a  finite union of convex, entangled sets  $C_1, \ldots,C_n$ in $\pf {L( \mt B)}$, with $C_i\cap I_{\delta(s,\alpha)}\neq \emptyset$ for all $i=1, \ldots,n$. In particular, $ \sim_{\mt V} $ is independent of the choice of $ \mathcal{V} $.

*Proof $ (\rightarrow) $ follows by considering all sets $ V \in \mathcal{V} $ such that $ V \cap [\alpha, \alpha']^\pm \not = \emptyset $.

Let us prove $ (\leftarrow)$. Pick $ \alpha, \alpha' \in Pref (\mathcal{L(B)}) $ such that $\delta(s,\alpha)= \delta(s, \alpha') $ and the interval $[\alpha, \alpha']^\pm$ is contained in a  finite union of convex, entangled sets $C_1, \ldots,C_n$, with $C_i\cap I_q\neq \emptyset$ for every $i=1, \ldots,n$, where $ q = \delta(s,\alpha)= \delta(s, \alpha') $. By Lemma <ref> we can assume that $C_1\prec C_2 \prec \ldots \prec C_n$. Assume without loss of generality that $ \alpha \prec \alpha' $, and consider $ V \in \mathcal{V} $ such that $ \alpha \prec V \prec \alpha' $. We must prove that $ V\cap I_q\neq \emptyset $. It will suffice to prove that if $V\in \mt V$ is such that $V\subseteq   \bigcup_{i=1}^n C_i$, then $ q $ occurs in $ V $.

Let $ \mathcal{V} = \{V_1, \dots, V_r \} $, with $ V_1 \prec \dots \prec V_r $. Since $ \mathcal{V} $ is minimum-size, by Remark <ref> for every $ i = 1, \dots, r $ there exist two states $ q_i $ and $ q'_i $ such that $ q_i $ occurs in $ V_i $ but not in $ V_{i + 1} $ and $ q'_i $ occurs in $ V_i $ but not in $ V_{i - 1} $ (we assume $ V_0 = V_{r + 1} = \emptyset $).

Assume that $ V = V_s $. If $ C_i \subseteq V_s $ for some $ i $, then the conclusion follows because $C_i\cap I_q\neq \emptyset$. Otherwise, since $C_1\prec C_2 \prec \ldots \prec C_n$, it must be $ V_s \subseteq C_i \cup C_{i + 1} $ for some $ i $. We distinguish three cases.

* $ V_s \cap  C_{i+1}=\emptyset $. In this case, it must be $ V_s \subseteq C_i $. Let $ V_{s - h}, V_{s - h +1},  \ldots, V_s, \ldots, V_{s+k -1}, V_{s+k} $ ($ h, k \ge 0 $) be all elements of $ \mathcal{V} $ contained in $ C_i $. Since $ V_1 \prec \dots \prec V_r $, we conclude:

\begin{equation*}
V_{s - h }\cup \ldots  \cup V_{s}\cup \ldots \cup V_{s+k}\subseteq C_i  \subseteq V_{s-h-1 }\cup V_{s-h}\cup \ldots\cup V_{s}\cup \ldots \cup V_{s+k}\cup V_{s+k+1 }
\end{equation*}

where as usual $ V_0 = V_{r + 1} = \emptyset $. We know that $q'_{s - h}, \ldots,  q'_{s},q_{s}, \ldots q_{s+k}$ occur in $V_{s-h}\cup \ldots \cup V_{s+k}$, so they also occur in $C_i$. Moreover, we also know that $ q $ occurs in $ C_i $. Since $ C_i $ is entangled, in particular there exists a sequence $ \alpha_{s - h} \preceq \dots \preceq \alpha_{s} \preceq \beta \preceq \gamma_{s} \preceq \dots \preceq \gamma_{s + k} $ witnessing that the sequence of states $ q'_{s - h}, \ldots,  q'_{s}, q, q_{s}, \ldots q_{s+k} $ occurs in $ C_i $, and so also in $ V_{s-h -1 }\cup V_{s-h}\cup \ldots\cup V_{s}\cup \ldots \cup V_{s+k}\cup V_{s+k+1 } $. Since $ q'_{s - h} $ does not occur in $ V_{s - h - 1} $, then the sequence $ q'_{s - h + 1}, \ldots,  q'_{s}, q, q_{s}, \ldots q_{s+k} $ occurs in this order in $ V_{s - h}\cup \ldots\cup V_{s}\cup \ldots \cup V_{s+k}\cup V_{s+k+1 } $. Now, $ q'_{s - h + 1} $ does not occur in $ V_{s - h} $, so the sequence $ q'_{s - h + 2}, \ldots,  q'_{s}, q, q_{s}, \ldots q_{s+k} $ occurs in this order in $ V_{s - h + 1}\cup \ldots\cup V_{s}\cup \ldots \cup V_{s+k}\cup V_{s+k+1 } $. Proceeding like that, we obtain that the sequence $ q, q_{s}, \ldots q_{s+k} $ occurs in this order in $ V_{s} \cup \ldots\cup V_{s+k}\cup V_{s+k+1} $. Now suppose by contradiction that $ q $ does not occur in $ V_s $. Then, as before we obtain that $ q_{s}, \ldots q_{s+k} $ occurs in this order in $ V_{s + 1}\cup \ldots\cup V_{s+k}\cup V_{s+k+1 } $, then $ q_{s+ 1}, \ldots q_{s+k} $ occurs in this order in $ V_{s + 2}\cup \ldots\cup V_{s+k}\cup V_{s+k+1 } $, and we finally conclude that $ q_{s + k} $ occurs in $ V_{s+k+1 } $, a contradiction.

* $ V_s \cap  C_{i}=\emptyset $. In this case, it must be $ V \subseteq C_{i + 1} $ and one concludes as in the previous case.

* $ V_s \cap  C_{i} \not = \emptyset $ and $ V\cap  C_{i + 1} \not = \emptyset $. In this case, let $ V_{s - h}, \dots, V_{s - 1} $ ($ h \ge 0 $) be all elements of $ \mathcal{V} $ contained in $ C_i $, and let $ V_{s + 1}, \dots, V_{s + k} $ ($ k \ge 0 $) be all elements of $ \mathcal{V} $ contained in $ C_{i + 1} $. As before:

\begin{equation*}
V_{s - h} \cup \dots \cup V_{s - 1} \subseteq C_i \subseteq V_{s -h - 1} \cup V_{s - h} \cup \dots \cup V_{s - 1} \cup V_s
\end{equation*}

\begin{equation*}
V_{s + 1} \cup \dots \cup V_{s + k} \subseteq C_i \subseteq V_s \cup V_{s + 1} \cup \dots \cup V_{s + k} \cup V_{s + k + 1}.
\end{equation*}

Now, assume by contradiction that $ q $ does not occur in $ V_s $. First, let us prove that $ q'_s $ does not occur in $ C_i $. Suppose by contradiction that $ q'_s $ occurs in $ C_i $. We know that $ q'_{s - h}, \dots, q'_{s - 1} $ occurs in $ C_i $, and we also know that $ q $ occurs in $ C_i $. Since $ C_i $ is entangled, then $ q'_{s - h}, \dots, q'_{s - 1}, q'_s, q $ should occur in this order in $ C_i $ and so also in $ V_{s -h - 1} \cup V_{s - h} \cup \dots \cup V_{s - 1} \cup V_s $, which as in case 1 would imply that $ q $ occurs in $ V_s $, a contradiction. Analogously, one shows that $ q_s $ does not occur in $ C_{i + 1} $.

Since $ q_s $ and $ q'_s $ occur in $ V_s $, then there exists a monotone sequence in $ V_s $ whose trace consists of alternating values of $ q_s $ and $ q'_s $. But $ V_s \subseteq C_i \cup C_{i + 1} $ and $ C_i \prec C_{i + 1} $, so the monotone sequence is definitely contained in $ C_i $ or $ C_{i + 1} $. In the first case we would obtain that $ q'_s $ occurs in $ C_i $, and in the second case we would obtain that $ q_s $ occurs in $ C_{i + 1} $, so in both cases we reach a contradiction.

The $ \mathcal{V} $-free characterization of $ \sim_{\mt V} $ allows us to easily deduce right-invariance.

*Statement of Lemma <ref>. Let $\mt B$ be a DFA. Then, the equivalence relation $\sim$ is right-invariant.

*Proof Assume that $\alpha \sim \alpha' $ and $a\in \Sigma$ is such that $\alpha a \in \pf{L }$. We must prove that $\alpha' a\in  \pf{L }$ and  $\alpha a\sim \alpha' a$. By Lemma <ref>, we know that $\delta(s,\alpha)= \delta(s, \alpha')$ and there exist convex, entangled sets $ C_1, \dots, C_n $ such that $[\alpha, \alpha']^\pm \subseteq C_1 \cup \dots \cup C_n $ and $ C_i\cap I_{\delta(s,\alpha)}\neq \emptyset$ for all $i=1, \ldots,n$. We must prove that $\alpha' a\in  \pf{L }$, $\delta(s,\alpha a)= \delta(s, \alpha' a)$ and there exist convex, entangled sets $ C'_1, \dots, C'_{n'} $ such that $[\alpha a, \alpha' a]^\pm \subseteq C'_1 \cup \dots \cup C'_{n'} $ and $ C'_i\cap I_{\delta(s,\alpha a)}\neq \emptyset$ for all $i=1, \ldots,n'$.

From $\delta(s,\alpha)= \delta(s, \alpha')$ and $\alpha a \in \pf{L }$ we immediately obtain $\alpha' a \in \pf{L }$ and $\delta(s,\alpha a)= \delta(s, \alpha' a)$. Moreover, from $[\alpha, \alpha']^\pm \subseteq C_1 \cup \dots \cup C_n $ we obtain $[\alpha a, \alpha' a]^\pm \subseteq C_1a \cup \dots \cup C_na $, and from $ C_i\cap I_{\delta(s,\alpha)}\neq \emptyset$ we obtain $ C_i a \cap I_{\delta(s,\alpha a)}\neq \emptyset $, so we only have to prove that every $ C_i a $ is convex and entangled. As for convexity, let $ \alpha, \beta, \gamma \in Pref (\mathcal{L(B)}) $ such that $ \alpha \prec \beta \prec \gamma $ and $ \alpha, \gamma \in C_i a $. We must prove that $ \beta \in C_i a $. Since $ \alpha, \gamma \in C_i a $, we can write $ \alpha = \alpha' a $ and $ \gamma = \gamma' a $, with $ \alpha', \gamma' \in C_i$. From $ \alpha' a \prec \beta \prec \gamma' a $ we obtain $ \beta = \beta' a $ for some $ \beta \in Pref(\mathcal{L(B)}) $. Since $ \alpha' \prec \beta' \prec \gamma' $ and $ \alpha', \gamma' \in C_i $ then $ \beta' \in C_i $ by convexity and so $ \beta \in C_i a $. Finally, if $ (\alpha_i)_{i \in \mathbb{N}} $ is a monotone sequence witnessing that $ C_i $ is entangled, then $ (\alpha_i a)_{i \in \mathbb{N}} $ is a monotone sequence witnessing that $ C_i a $ is entangled.

§.§ The Hasse automaton

Let us start with a fairly intuitive lemma which will be used in the proof of Theorem <ref>.

Let $ (Z, \le) $ be a total order. If $ C_1, \ldots , C_{n} $ are convex sets such that $ C_{i}\cap C_{j} \neq \emptyset $ for all pairwise distinct $i, j\in \{ 1 , \ldots , n\} $, then $ \bigcap_{i=1}^{n} C_{i}\neq \emptyset $.

We proceed by induction on $ n $. Cases $ n=1, 2 $ are trivial, so assume $ n \ge 3 $. For every $ i \in \{1, \ldots , n\} $, the set:

\[\bigcap_{\substack{k \in \{1, \ldots , n\} \\ k \neq i}} C_{k}
\]

is nonempty by the inductive hypothesis, so we can pick an element $ d_i $. If for some distinct $ i $ and $ j $ we have $ d_{i}=d_{j} $, then such an element witnesses that $ \bigcap_{i=1}^{n} C_{i}\neq \emptyset $. Otherwise, assume without loss of generality that $ d_{1} < \dots < d_{n} $. Fix any integer $ j $ such that  $ 1 < j < n $, and let us prove that $ d_j $ witnesses that $ \bigcap_{i=1}^{n} C_{i}\neq \emptyset $. We only have to prove that $ d_j \in C_j $. This follows from $ d_1, d_n \in C_j $ and the convexity of $ C_j $.

We can now prove Theorem <ref>.

*Statement of Theorem <ref>.
Let  $\mt B $ be  a DFA. Then, there exists a DFA $\mt B'$ such that $ \mathcal{L(B')} = \mathcal{L(B)} $ and $\text{ent}(\mt B)=\text{ent}(\mt B')= \text{width}(\mt B')$.

*Proof Let $ \sim $ be the equivalence relation $ \sim_\mathcal{B} $ considered in this section, and define $ \mathcal B' =(Q', s', \delta', F') $ by:

* $ Q' = \{  [\alpha]_{\sim}: \alpha \in \pf L\}$;

* $ \delta'([\alpha]_{\sim},a) = [\alpha a]_{\sim} $ for every $ \alpha \in Pref (\mathcal{L(B)}) $ and for every $ a \in \Sigma $ such that $ \alpha a \in Pref (\mathcal{L(B)}) $;

* $ s' = [ \epsilon ]_\sim $, where $ \epsilon $ is the empty string;

* $ F'= \{ [\alpha]_\sim:\alpha \in \mathcal L\} $.

Since $ \sim $ is right-invariant, it has finite index and $ \mathcal{L} $ is the union of some $ \sim $-classes (Lemma <ref> and Lemma <ref>), then $ \mathcal{B'} $ is a well-defined DFA. Moreover, it is easy to check that it holds:

\begin{equation}\label{eq30}
\alpha \in [\beta]_\sim \iff \delta' (s', \alpha) = [\beta]_\sim
\end{equation}

which implies that for every $ \alpha \in Pref(\mathcal{L}) $ it holds:

\begin{equation}\label{eq31}
I_{[\alpha]_\sim} = [\alpha]_\sim
\end{equation}

and so $ \mathcal{L}(\mathcal{B}') = \mathcal{L(\mathcal{B}}) $.

Let us prove that $\text{ent}(\mt B')\leq \text{ent}(\mt B)$. Let $ \{[\alpha_1]_\sim, \dots, [\alpha_{\text{ent}(\mt B')}]_\sim \} $ be an entangled set of (pairwise distinct) states in $ \mathcal{B'} $ having maximum cardinality, as witnessed by some monotone sequence $ (\beta_i)_{i \in \mathbb{N}} $. Let $ \mathcal{V} $ be a minimum-size e.c. decomposition of $\pf {L(B)}$. Since all elements of $ \mathcal{V} $ are convex, then there exists $ V \in \mathcal{V} $ such that $ (\beta_i)_{i \in \mathbb{N}} $ is definitely contained in $ V $, so in particular there exist integers $ i_1, \dots, i_{\text{ent}(\mt B')} $ such that $ \beta_{i_k} \in V $ and $ \delta'(s, \beta_{i_k}) = [\alpha_k]_\sim $ (or equivalently $ [\alpha_k]_\sim = [\beta_{i_k}]_\sim $ by equation <ref>), for every $ k = 1, \dots, \text{ent}(\mt B') $. Now, define $ q_i = \delta (s, \beta_{i_k}) $. Notice that $ q_1, \dots, q_{\text{ent}(\mt B')} $ are pairwise distinct: if for some distinct integers $ r, s $ it were $ q_r = q_s $, then we would conclude $ \beta_{i_r} \sim \beta_{i_s} $ (because $ \delta(s, \beta_{i_r}) = q_r = q_s = \delta(s, \beta_{i_s}) $ and there is no element of $ \mathcal{V} $ between $\beta_{i_r} $ and $\beta_{i_s} $, being $\beta_{i_r}, \beta_{i_r} \in V $), or equivalently, $ [\alpha_r]_\sim = [\alpha_s]_\sim $, a contradiction because $ \{[\alpha_1]_\sim, \dots, [\alpha_{\text{ent}(\mt B')}]_\sim \} $ consists of pairwise distinct states. Moreover, $ \{q_1, \dots, q_{\text{ent}(\mt B')}\} $ is an entangled set in $ \mathcal{B} $, because all these states occur  in $ V $ (as witnessed by $ \beta_{i_1}, \dots, \beta_{i_k} $) and $ V $ is an element of an e.c. decomposition. In particular, $ \{q_1, \dots, q_{\text{ent}(\mt B')}\} $ witnesses that $\text{ent}(\mt B')\leq \text{ent}(\mt B)$.

Let us prove that $\text{ent}(\mt B)\leq \text{ent}(\mt B')$. Let $ \{q_1, \dots, q_{\text{ent}(\mt B)} \} $ be an entangled set of (pairwise distinct) states in $ \mathcal{B} $ having maximum cardinality, as witnessed by some monotone sequence $ (\alpha_i)_{i \in \mathbb{N}} $. Notice that every $ I_{q_k} $ is equal to a (finite) union of some $ I_{q'} $, with $ q' \in Q' $: if $ \beta\in I_{q_k} $ and $\beta, \beta'\in I_{q'}$, where $q'=[\alpha]_\sim$, then by equation <ref> it holds $ \beta \sim \beta' $, from which  $ q_k=\delta(s, \beta) = \delta(s, \beta') $ and  $ \beta' \in I_{q_k} $ follow. Since $ (\alpha_i)_{i \in \mathbb{N}} $ goes through $ q_k $ infinitely many times, then there exist $ q'_k \in Q' $ such that $ I_{q'_k} \subseteq I_{q_k} $ and $ (\alpha_i)_{i \in \mathbb{N}} $ goes through $ q'_k $ infinitely many times. We conclude that $ q'_1, \dots, q'_k $ are pairwise distinct and $ \{q'_1, \dots, q'_k \} $ is an entangled set of states in $ \mathcal{B'} $, which implies $\text{ent}(\mt B)\leq \text{ent}(\mt B')$.

Let us prove that $ \text{width}(\mt B')\leq \text{ent}(\mt B)$. By Dilworth's theorem, there exist states:
\[q_1'=[\alpha_1]_\sim, \dots, q_{\text{width}(\mt B')}'=[\alpha_{\text{width}(\mt B')}]_\sim  \]
being pairwise not $ \le_\mathcal{B'}$-comparable. Define $ q_i = \delta(s, \alpha_i) $. From Definition  <ref> it follows that for all $i=1,\ldots, k$   there exist two integers $ n_i $, $ m_i $, with $n_i\leq m_i$, such that

\[I_{q_i'}\subseteq V_{n_i}\cup V_{n_i+1} \cup \ldots \cup V_{m_i} \text{ and for every $ n_i \le j \le m_i $ it holds $ V_j \cap I_{q_i}\neq \emptyset $}.\]

Let $W_i=V_{n_i}\cup V_{n_i+1} \cup \ldots \cup V_{m_i}$.  Since, for all $i$,   $W_i$ is a  union of consecutive elements of $\mt V$  and   $I_{q_i}$  is a  subset  of   $W_i$,
the incomparability of $q_i', q_j'$ implies $W_i\cap W_j\neq \emptyset$, for all $i\neq j$.  Since all the $ W_{i} $'s are convex, by Lemma <ref> it follows that $ \bigcap_{i=1}^{m}W_{i} \neq \emptyset $ and, since the $W_i$'s are unions of consecutive elements of the partition $\mathcal V$ containing $q_i$, it follows  that    there exists an element $V$  in $ \mathcal V $ which is a subset of all $ W_{i} $'s.
But then $V\cap I_{q_i}\neq \emptyset$, for all $i=1, \ldots, \text{width}(\mt B')$, and since $V$ is entangled it follows  that $q_1, \ldots, q_{\text{width}(\mt B')}$ are entangled in $\mt B$.

Summarizing, we proved that    $ \text{width}(\mt B')\leq \text{ent}(\mt B)= \text{ent}(\mt B')$, so that by   Lemma <ref>  we obtain  $\text{ent}(\mt B)=\text{ent}(\mt B')= \text{width}(\mt B')$.

Here is the proof of our main theorem.

*Statement of Theorem <ref>.
If $\mt A$ is the minimum automaton of the regular language $\mt L$, then:

\[\text{width}(\mt L)= \text{width}(\mt H_{\mt L})= \text{ent}(\mt A)=\text{ent}(\mt L).\]

By  Lemma <ref> we have
$\text{ent}(\mt A)= \text{ent}(\mt L)$. Since $\text{ent}(\mt B)\leq \text{width}(\mt B)$ for all DFAs (Lemma <ref>), we obtain $\text{ent}(\mt L)\leq \text{width}(\mt L), $ and from   Theorem <ref> it follows $ \text{width}(\mt H_{\mt L})= \text{ent}(\mt A) $. We have:

\[\text{width}(\mt H_{\mt L})= \text{ent}(\mt A)= \text{ent}(\mt L) \leq \text{width}(\mt L)\leq \text{width}(\mt H_{\mt L}) \]

and the conclusion follows.

*Statement of Lemma <ref>.  Let $ \mathcal{L} $ be a language, and consider the class:

\begin{equation*}
\mathscr{C} = \{\mathcal{B'} | \text{$ \mathcal{B} $ is a DFA and $ \mathcal{L(B)} = \mathcal{L} $} \}.
\end{equation*}

Then, there exists exactly one DFA being in $ \mathscr{C}$ and having the minimum number of states, namely, the Hasse automaton  $\mt H_{\mt L}$. In other words, $\mt H_{\mt L}$ is the minimum DFA of $ \mathscr{C} $.

Let $ \mt A $ the minimum DFA recognizing $ \mathcal{L} $ and let $ \mathcal{B} $ any DFA recognizing $ \mathcal{L} $. Let us prove that $ \sim_\mathcal{B} $ is a refinement of $ \sim_\mathcal{A} $. If $ \alpha \sim_\mathcal{B} \alpha' $, then by Lemma <ref> we have $\delta(s_\mt B,\alpha)= \delta(s_\mt B, \alpha')$ and   the interval $[\alpha, \alpha']^\pm$ is contained in a  finite union of convex, entangled (with respect to $ \mathcal{B} $) sets  $C_1, \ldots,C_n$ in $\pf {L}$, with $C_i\cap I_{\delta(s_\mt B,\alpha)}\neq \emptyset$  for all $i=1, \ldots,n$. Since $ \mathcal{A} $ is the minimum DFA (and so for every $ q \in Q_\mathcal{A} $ we have that $ I_q $ is the union of some sets $ I_{q'} $, with $ q' \in Q_\mathcal{B} $), then we also have $\delta(s_\mt A,\alpha)= \delta(s_\mt A, \alpha') $, every $ C_i $ is also entangled with respect to $ \mathcal{A} $ and $ C_i\cap I_{\delta(s_\mt A,\alpha)}\neq \emptyset$, so again by Lemma <ref> we conclude $ \alpha \sim_\mathcal{A} \alpha'$. By definition the number of classes of $ \mathcal{B'} $ is equal to index of $ \sim_\mathcal{B} $ and the number of classes of $ \mt H_{\mt L} $ is equal to index of $ \sim_\mathcal{A} $, so $ \mt H_{\mt L}$ is a minimum DFA of $ \mathscr{C} $, being $ \mathcal{B} $ arbitrary. Conversely, if $ \mathcal{B}' $ is a minimum DFA of $ \mathscr{C} $, then $ \sim_\mathcal{A} $ and $ \sim_\mathcal{B} $ are the same equivalence relation and so by construction $ \mathcal{B'} $ and  $ \mt H_{\mt L}$ are the same DFA.

§ PROOFS OF SECTION <REF>

In [8] it is proved that the width of a regular language is a measure of the difficulty of indexing the languages and, as so, it has interesting application relating to complexity issues on graph pattern matching  and the like. Using the results of the previous sections we now prove that the width of a regular language  is computable.
We start  in Theorem <ref>  with a  combinatorial  characterization  of languages having
width larger than a fixed $k$  and transform it in a decidable condition in Lemma <ref>.
The proof are adaptations of similar results [2] for the case of Wheeler languages (i.e. languages with width equal to 1).

Let us start with a lemma which will be used to provide an upper bound to our dynamic programming algorithm.

Let $ \mathcal{A} $ be an NFA  with set of states $ Q $, and let $ q_1, \dots, q_h \in Q $. If there exist $ \nu_1, \dotsm \nu_h \in Pref (\mathcal{L(A)}) $ such that:

* $ \nu_i \in I_{q_i} $ for every $ i = 1, \dots, h $;

* $ \nu_1 \prec \dots \prec\nu_h $;

then, there exist $ \nu'_1, \dotsm \nu'_h \in Pref (\mathcal{L(A)}) $ such that:

* $ \nu'_i \in I_{q_i} $ for every $ i = 1, \dots, h $;

* $ \nu'_1 \prec \dots \prec \nu'_h $;

* $ |v'_i | \le h - 2 + \sum_{t = 1}^h |Q|^t $ for every $ i = 1, \dots, h $.

For notational simplicity, we will prove the theorem for $ h = 3 $ (the extension to the general case is straightforward).

Given $ \varphi \in \Sigma^* $, we denote by $ \varphi(k)$ the $k$-th letter of $ \varphi $ from the right (if $ |\varphi| < k $ we write $ \varphi (k) = \epsilon $, where $ \epsilon $ is the empty string). For example, $\varphi(1)$ is the last letter of $\varphi$).

Let $\nu_1\prec\nu_2\prec \nu_3$ be strings in $ I_{q_1}, I_{q_2}, I_{q_3} $, respectively. Let  $d_{3,2}$ be the first position from the right where $\nu_3$ and $\nu_2$ differ.  Since $\nu_3\succ \nu_2$, we have $|\nu_3|\geq d_{3,2}$.
Similarly,  let $d_{2,1}$ be the first position from the right in which $\nu_2$ and $\nu_1$ differ. Again, since $\nu_2 \succ \nu_1$, we have $|\nu_2|\geq  d_{2,1}$.
We distinguish three cases.

* $ d_{3, 2} = d_{2, 1} $.

* $d_{3,2} < d_{2,1}$ (see Figure <ref>).

* $ d_{2,1}<d_{3,2}$ (see Figure <ref>).

We will not prove case 3 because it is analogous to case 2 (just consider Figure <ref> rather than Figure <ref>). Moreover, as we will see, case 1 is not the bottleneck of the length bound. Hence, in the following we assume $d_{3,2} \le d_{2,1}$. Since $|\nu_3|\geq  d_{3,2}$ and $|\nu_2| \geq  d_{2,1}\geq d_{3,2}$, then $\nu_3, \nu_2$, and $ \nu_1$ end with  the same word $\xi$ with $|\xi|= d_{3,2}-1$. Note that $\nu_2\prec \nu_3$ implies $ \nu_2(d_{3,2})\prec  \nu_3(d_{3,2})$. To sum up, we can write:

\begin{equation*}
\nu_1=\theta_1 \nu_1(d_{3,2}) \xi\prec \nu_2=\theta_2  \nu_2(d_{3,2}) \xi \prec  \nu_3=\theta_3 \nu_3(d_{3,2})\xi
\end{equation*}

for some strings $ \theta_1, \theta_2, \theta_3 $.

$ \nu_3 \equiv $     3c|$ \cdots \  \theta_3 \ \cdots $      $ \nu_3(d_{3,2}) $     $ \cdots \  \xi \  \cdots $

$ \curlyvee $    3c     1c$ \curlyvee $     1c

2*$ \nu_2 \equiv $     3c|$\cdots \  \theta_2 \ \cdots  $     $ \nu_2(d_{3,2}) $     $ \cdots \  \xi \  \cdots $
$ \cdots \  \theta_{2}'\ \cdots $     $ \nu_2(d_{2,1}) $     $ \cdots \ \xi' \  \cdots $     $ \nu_2(d_{3,2}) $     $ \cdots \  \xi \  \cdots $

$ \curlyvee $    3c$ \curlyvee $     1c$ \shortparallel$     1c

2*$ \nu_1 \equiv $     3c|$\cdots \  \theta_1 \ \cdots  $     $ \nu_1(d_{3,2}) $     $ \cdots \  \xi \  \cdots $
$ \cdots \  \theta'_{1}\ \cdots $     $ \nu_1(d_{2,1}) $     $ \cdots \ \xi' \  \cdots $     $ \nu_1(d_{3,2}) $     $ \cdots \  \xi \  \cdots $

Case $ d_{3,2} < d_{2,1} $.

Without loss of generality, we may assume that   $|\xi|  \leq |\mathcal Q|^3$. Indeed,
if $|\xi|>|\mathcal Q|^3$  then when we consider the triples of states visited while reading the last  $| \xi |$ letters in a computation  of  $\nu_1, \nu_2, \nu_3$ we must meet  a repetition, so we could erase a common factor from $\xi$, obtaining a shorter word $\xi_1$ such that
$\theta_1 \nu_1(d_{3,2})\xi_1\prec \theta_2 \nu_2(d_{3,2}) \xi_1\prec \theta_3\nu_3(d_{3,2}) \xi_1$, with the three strings still ending in $q_1,q_2$, and $q_3$, respectively.

Consider first the case  $d_{3,2}=d_{2,1}$. Let $ s_1, s_2, s_3 $ be the states reached from $ s $ by reading $ \theta_1, \theta_2, \theta_3 $, respectively. Since   $d_{2,1}=d_{3,2} $, then we have $ \nu_1(d_{3, 2}) = \nu_1(d_{2, 1}) \prec \nu_2(d_{2, 1}) = \nu_2 (d_{3, 2}) $ so without loss of generality we may assume that $ \theta_1, \theta_2, \theta_3$   label simple paths from $ s $ to $ s_1, s_2, s_3 $, respectively, and we still have $ \nu_1 \prec \nu_2 \prec \nu_3 $. In other words, we can assume $ | \theta_1|, |\theta_2|, |\theta_3|\leq |\mathcal Q| - 1 $. Hence, in this case we can find $ \nu'_1, \nu'_2, \nu'_3 $ that satisfy the same properties of $ \nu_1, \nu_2, \nu_3 $ and moreover $|\nu_1|, |\nu_2|, |\nu_3|\leq |\mathcal Q| +|\mathcal Q|^3$.

Now consider the case  $d_{3,2}< d_{2,1}$. In this case we have $ \nu_1(d_{3, 2}) = \nu_2 (d_{3, 2}) $. Moreover, $\theta_1 $ and $ \theta_2$ end  with  the same word $\xi'$   with $|\xi'|= d_{2,1}-d_{3,2}-1$, and we can write

\[ \theta_1=\theta_1' \nu_1(d_{2,1})\xi' \prec  \theta_2=\theta'_2\nu_2(d_{2,1})\xi' \]

for some strings $ \theta'_1, \theta'_2 $. Without loss of generality, we can assume that   $|\xi'| \leq |\mathcal Q|^2 $ by arguing as before. Moreover, we have $ \nu_1 (d_{2, 1}) \prec \nu_2 (d_{2, 1})$, so again as before we can assume that $ \theta'_1, \theta'_2 $ and $ \theta_3 $ are simple paths, and so $|\theta'_{1}|,  |\theta'_{2}|, |\theta_{3}|\leq |\mathcal Q| - 1 $.  Hence, in this case we can find $ \nu'_1, \nu'_2, \nu'_3 $ that satisfy the same properties of $ \nu_1, \nu_2, \nu_3 $ and moreover $|\nu_1|, |\nu_2|, |\nu_3|\leq 1 + |\mathcal Q| +|\mathcal{Q}|^2 + |\mathcal Q|^3$.

2*$ \nu_3 \equiv $     3c|$\cdots \  \theta_3 \ \cdots  $     $ \nu_3(d_{2,1}) $     $ \cdots \  \xi \  \cdots $
$ \cdots \  \theta'_3\ \cdots $     $  \nu_3(d_{3,2}) $     $ \cdots \ \xi' \  \cdots $     $ \nu_3(d_{2,1}) $     $ \cdots \  \xi \  \cdots $

$ \curlyvee $    3c$ \curlyvee $     1c$ \shortparallel $     1c

2*$ \nu_2 \equiv $     3c|$\cdots \  \theta_2 \ \cdots  $     $ \nu_2(d_{2,1}) $     $ \cdots \  \xi \  \cdots $
$ \cdots \  \theta'_2\ \cdots $     $ \nu_2(d_{3,2}) $     $ \cdots \ \xi' \  \cdots $     $ \nu_2(d_{2,1}) $     $ \cdots \  \xi \  \cdots $

$ \curlyvee $    3c     1c$ \curlyvee $     1c

$ \nu_1 \equiv $     3c|$ \cdots \  \theta_1 \ \cdots $      $ \nu_1(d_{2,1}) $     $ \cdots \  \xi \  \cdots $

Case $ d_{2,1}<d_{3,2}$.

We can now prove our graph-theoretical characterization of the width.

*Statement of Theorem <ref>.
Let $ \mathcal{L} $ be a regular language, and let $ \mathcal{A} $ the minimum DFA of $ \mathcal{L} $, with set of states $ Q $. Let $ k \ge 2 $ be an integer. Then, $ width(\mathcal{L}) \ge k $ if and only if there exist strings $ \mu_1, \dots, \mu_k $ and $ \gamma $ and there exist pairwise distinct $ u_1, \dots, u_k \in Q $ such that:

* $ \mu_j $ labels a path from the initial state $ s $ to $ u_j $, for every $ j = 1, \dots, k $;

* $ \gamma $ labels a cycle starting (and ending) at $ u_j $, for every $ j = 1, \dots, k $;

* either all the $ \mu_j $'s are smaller than $ \gamma $ or $ \gamma $ is smaller than all $ \mu_j $'s;

* $ \gamma $ is not a suffix of $ \mu_j $, for every $ j = 1, \dots, k $.

*Proof First, note that by Theorem <ref> we have $ width(\mathcal{L}) = ent (\mathcal{A}) $. Let us prove that  if the stated conditions hold true, then $ ent (\mathcal{A}) \ge k $. Notice that for every integer $ i $ we have $ \mu_j \gamma^i \in I_{u_j } $. Moreover, the $ \mu_j $'s are pairwise distinct because the $ u_j $'s are pairwise distinct, so without loss of generality we can assume $ \mu_1 \prec \dots \prec \mu_k $.

* If $ \mu_1 \prec \dots \prec \mu_k \prec \gamma $, consider the increasing sequence:

\begin{equation*}
\mu_1 \prec \dots \prec \mu_k \prec \mu_1 \gamma \prec \dots \mu_k \gamma \prec \mu_1 \gamma^2 \prec \dots \mu_k \gamma^2 \prec \mu_1 \gamma^3 \prec \dots \mu_k \gamma^3 \dots
\end{equation*}

* If $ \gamma \prec \mu_1 \prec \dots \prec \mu_k $, consider the decreasing sequence:

\begin{equation*}
\mu_k \succ \dots \succ \mu_1 \succ \mu_k \gamma \succ \dots \mu_1 \gamma \succ \mu_k \gamma^2 \succ \dots \mu_1 \gamma^2 \succ \mu_k \gamma^3 \succ \dots \mu_1 \gamma^3 \dots
\end{equation*}

where for example $ \mu_k \gamma \prec \mu_1 $ because $ \gamma \prec \mu_1 $ and $ \gamma $ is not a suffix of $ \mu_1 $.

The sequence witnesses that $ \{u_1, \dots, u_k \} $ is an entangled set of distinct states, so $ ent (\mathcal{A}) \ge k $.