A Myhill-Nerode Theorem for Generalized Automata, with Applications to Pattern Matching and Compression

Nicola Cotumaccio

arxiv: 2302.06506 · v4 · submitted 2023-02-13 · 💻 cs.FL · cs.DS· cs.LO

A Myhill-Nerode Theorem for Generalized Automata, with Applications to Pattern Matching and Compression

Nicola Cotumaccio This is my paper

Pith reviewed 2026-05-24 10:09 UTC · model grok-4.3

classification 💻 cs.FL cs.DScs.LO

keywords generalized automataMyhill-Nerode theoremWheeler automatapattern matchingdata compressiondeterministic automataformal languages

0 comments

The pith

A set W(A) yields the first full Myhill-Nerode theorem for generalized automata.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that attaching a set W(A) to any generalized automaton A produces a Myhill-Nerode characterization of its states. This set explains why minimal generalized deterministic automata are not necessarily unique, while recovering the textbook theorem as the special case in which every edge label is a single character. The same construction supplies concrete data structures: a Wheeler generalized automaton can be stored in e log sigma (1+o(1)) plus O(e) bits and can answer pattern-matching queries in O(m log log sigma) time.

Core claim

By defining the set W(A) for a generalized automaton A, the paper obtains a complete Myhill-Nerode theorem that classifies states according to their future behavior under the generalized determinism of Giammarresi and Montalbano; the resulting right-congruence is the unique minimal object that respects the richer transition relation, and the same set W(A) directly yields the bit-size and query-time bounds for Wheeler generalized automata.

What carries the argument

The auxiliary set W(A) that augments the usual Nerode equivalence classes to account for the string-labeled edges of a generalized automaton.

If this is right

The classical Myhill-Nerode theorem is recovered exactly when every edge label has length one.
Any Wheeler generalized automaton admits a representation whose size is essentially the total length of its edge labels times log sigma.
Pattern matching on the compressed representation takes time linear in the pattern length, up to a double-logarithmic factor in the alphabet size.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same auxiliary set might be used to obtain canonical forms for other relaxed notions of determinism in automata.
The compression technique could be lifted to indexing structures that store multiple generalized automata simultaneously.
If the determinism definition were altered, the existence of a compact Wheeler representation might fail while the Myhill-Nerode statement still holds.

Load-bearing premise

The determinism notion introduced by Giammarresi and Montalbano is the right definition under which W(A) produces both the Myhill-Nerode characterization and the claimed space and time bounds.

What would settle it

An explicit generalized automaton A together with a string w such that the state reached after reading w under the Giammarresi-Montalbano determinism rule differs from the state predicted by the equivalence classes derived from W(A).

read the original abstract

The model of generalized automata, introduced by Eilenberg in 1974, allows representing a regular language more concisely than conventional automata by allowing edges to be labeled not only with characters, but also strings. Giammarresi and Montalbano introduced a notion of determinism for generalized automata [STACS 1995]. While generalized deterministic automata retain many properties of conventional deterministic automata, the uniqueness of a minimal generalized deterministic automaton is lost. In the first part of the paper, we show that the lack of uniqueness can be explained by introducing a set $ \mathcal{W(A)} $ associated with a generalized automaton $ \mathcal{A} $. In this way, we derive for the first time a full Myhill-Nerode theorem for generalized automata, which contains the textbook Myhill-Nerode theorem for conventional automata as a degenerate case. In the second part of the paper, we show that the set $ \mathcal{W(A)} $ leads to applications for pattern matching and data compression. We show that a Wheeler generalized automata can be stored using $ \mathfrak{e} \log \sigma (1 + o(1)) + O(e) $ bits so that pattern matching queries can be solved in $ O(m \log \log \sigma) $ time, where $ \mathfrak{e} $ is the total length of all edge labels, $ e $ is the number of edges, $ \sigma $ is the size of the alphabet and $ m $ is the length of the pattern.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper extends Myhill-Nerode to generalized automata via W(A) and gives a concrete storage bound for Wheeler versions, but the exact degeneration to the classical case when labels have length 1 needs verification.

read the letter

The main contribution is a Myhill-Nerode-style result for generalized automata. They introduce the set W(A) tied to the Giammarresi-Montalbano determinism notion to account for non-uniqueness of minimal generalized deterministic automata, and claim this yields a full theorem that contains the textbook version as the case where every label has length 1. The second part turns the same set into a storage scheme for Wheeler generalized automata that uses e log sigma (1+o(1)) + O(e) bits and answers pattern matching queries in O(m log log sigma) time. That bound is the sort of concrete payoff that makes the characterization worth having. The work sits cleanly on top of the cited Eilenberg and Giammarresi-Montalbano foundations without obvious circularity or extra free parameters. The application to pattern matching follows directly from the new set, which is a plus. The soft spot is the stress-test point: whether W(A) really collapses exactly to ordinary right-language equivalence once all labels are single symbols. The determinism condition could in principle keep extra distinctions even in that degenerate case, which would make the “contains the textbook theorem” claim fail. The abstract asserts it works, so the proof presumably shows the two equivalences coincide, but that step is load-bearing and worth checking line by line. No other internal contradictions jump out from the description. This is aimed at automata theorists and people building compact string indexes. Anyone already working with Wheeler graphs or generalized automata will see the value in the bound and the characterization. It is coherent enough on its own terms to merit referee time rather than a desk reject.

Referee Report

2 major / 2 minor

Summary. The paper introduces a set W(A) associated with a generalized automaton A (under the Giammarresi-Montalbano determinism notion) to explain the non-uniqueness of minimal generalized deterministic automata and derives a Myhill-Nerode theorem for them; this is claimed to contain the classical Myhill-Nerode theorem as the special case of unit-length labels. The second part applies W(A) to Wheeler generalized automata, claiming a representation using e log σ (1+o(1)) + O(e) bits supporting pattern matching in O(m log log σ) time.

Significance. If the degeneration to the classical case holds and the space/time bounds are tight, the work supplies a missing theoretical foundation for generalized automata and yields concrete, parameter-light data structures for compressed pattern matching; the explicit construction of W(A) and the Wheeler-GA bounds are the primary contributions.

major comments (2)

[§3] §3 (Myhill-Nerode theorem for generalized automata): the central claim that the new theorem 'contains the textbook Myhill-Nerode theorem for conventional automata as a degenerate case' is load-bearing. The manuscript must contain an explicit lemma or corollary showing that, when every edge label has length 1, the equivalence induced by W(A) coincides exactly with the classical right-language congruence; without this reduction the 'full theorem' statement does not hold.
[§5] §5 (Wheeler generalized automata and space bound): the stated space bound e log σ (1+o(1)) + O(e) is presented as following from W(A), yet the derivation of the (1+o(1)) factor and the precise dependence on the total label length e versus the number of edges e is not shown to be independent of hidden parameters; this directly supports the claimed query time and must be made fully rigorous.

minor comments (2)

[Abstract] Notation: the distinction between the total label length (mathfrak{e}) and the number of edges (e) is introduced late; define both symbols at first use in the abstract and introduction.
[§2] The determinism definition of Giammarresi-Montalbano is invoked without restating its precise condition; a one-sentence recap in §2 would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major point below and will revise the manuscript to incorporate the requested additions, which will strengthen the presentation of the results.

read point-by-point responses

Referee: [§3] §3 (Myhill-Nerode theorem for generalized automata): the central claim that the new theorem 'contains the textbook Myhill-Nerode theorem for conventional automata as a degenerate case' is load-bearing. The manuscript must contain an explicit lemma or corollary showing that, when every edge label has length 1, the equivalence induced by W(A) coincides exactly with the classical right-language congruence; without this reduction the 'full theorem' statement does not hold.

Authors: We agree that an explicit reduction is required to substantiate the containment claim rigorously. In the revised manuscript we will insert a new corollary immediately after Theorem 3 in Section 3. The corollary will state that, when every edge label has length 1, the equivalence relation induced by the sets W(q) is identical to the classical right-language congruence of the Myhill-Nerode theorem. The short proof will show that each W(q) reduces exactly to the standard right-language of state q under unit-length labels, thereby recovering the textbook statement as a special case. revision: yes
Referee: [§5] §5 (Wheeler generalized automata and space bound): the stated space bound e log σ (1+o(1)) + O(e) is presented as following from W(A), yet the derivation of the (1+o(1)) factor and the precise dependence on the total label length e versus the number of edges e is not shown to be independent of hidden parameters; this directly supports the claimed query time and must be made fully rigorous.

Authors: We acknowledge that the derivation of the space bound must be expanded. In the revision we will add a dedicated subsection in Section 5 that derives the bound 𝔢 log σ (1+o(1)) + O(e) directly from the encoding of the sets in W(A). The proof will explicitly obtain the (1+o(1)) factor from the succinct representation of the ordered partitions and will separate the dependence on total label length 𝔢 from the number of edges e, confirming the absence of hidden parameters. The O(m log log σ) query time will likewise be re-derived step-by-step from the resulting data structure. revision: yes

Circularity Check

0 steps flagged

No circularity: W(A) is a new auxiliary construction yielding an independent Myhill-Nerode characterization

full rationale

The paper defines a new set W(A) associated with a generalized automaton A (using the external Giammarresi-Montalbano determinism notion from 1995) and derives a Myhill-Nerode theorem from it. The abstract and provided text present this as a novel explanatory device that recovers the classical theorem only as a special case when labels have length 1; no equation or step is shown to reduce by construction to a fitted parameter, self-citation, or renamed input. The determinism reference is to prior independent work by different authors. The space/time bounds for Wheeler automata are stated as consequences of W(A) rather than tautological rewritings. This is a standard non-circular derivation of a new characterization.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the paper relies on standard automata definitions and prior determinism notions but introduces no free parameters, new entities, or ad-hoc axioms visible at this level.

axioms (1)

domain assumption Generalized automata model and determinism definition from Eilenberg 1974 and Giammarresi-Montalbano STACS 1995
The paper builds directly on these established models for the theorem and application.

pith-pipeline@v0.9.0 · 5807 in / 1287 out tokens · 46855 ms · 2026-05-24T10:09:36.765917+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

[1]

15 Nicola Cotumaccio, Travis Gagie, Dominik Köppl, and Nicola Prezza

doi:10.1145/3607471. 15 Nicola Cotumaccio, Travis Gagie, Dominik Köppl, and Nicola Prezza. Space-time trade-offs for the lcp array of wheeler dfas. In Franco Maria Nardini, Nadia Pisanti, and Rossano Venturini, editors, String Processing and Information Retrieval, pages 143–156, Cham, 2023. Springer Nature Switzerland. 16 Nicola Cotumaccio and Nicola Prez...

work page doi:10.1145/3607471 2023
[2]

URL:https://www.sciencedirect.com/science/article/pii/ B9780124177505500221, doi:10.1016/B978-0-12-417750-5.50022-1

Academic Press, 1971. URL:https://www.sciencedirect.com/science/article/pii/ B9780124177505500221, doi:10.1016/B978-0-12-417750-5.50022-1 . 31 John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman.Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., USA, 2006. 32 Ramana M. Idury and Mich...

work page doi:10.1016/b978-0-12-417750-5.50022-1 1971
[3]

|Q∼|is equal to the index of∼

work page
[4]

Moreover, ifB is aW-GDFA that recognizesL, thenA≡B is isomorphic toB

≡A∼and∼are the same equivalence relation. Moreover, ifB is aW-GDFA that recognizesL, thenA≡B is isomorphic toB. Proof. DefineA∼= (Q∼,E∼,s∼,F∼) as follows. Q∼={[α]∼|α∈W}. s∼= [ϵ]∼. E∼={([α]∼, [αρ]∼,ρ)|α∈W,ρ∈K(Tα)}. F∼={[α]∼|α∈L}. Let us prove thatA∼is a well-defined GDFA. First, the number of states is finite because∼ has finite index. Next,ϵ∈W, sos∼is wel...

work page
[5]

We must prove that(α∈W)∧(α∼β)

Assume that (α∈W(A∼))∧(Iα= [β]∼). We must prove that(α∈W)∧(α∼β). Since α′,α∈W(A∼), α′is the longest strict prefix ofαinW(A∼), α=α′ρ, andIα′= [α′]∼, then by Remark 9 we obtain that([α′]∼, [β]∼,ρ)∈E∼. The definition ofE∼implies α=α′ρ∈Wand α∼β

work page
[6]

We must prove that(α∈W(A∼))∧(Iα= [β]∼)

Assume that(α∈W)∧(α∼β). We must prove that(α∈W(A∼))∧(Iα= [β]∼). Let us prove that([α′]∼, [α]∼,ρ)∈E∼. Sinceα′,α∈W, we only have to show thatρ∈K(Tα′). Since α=α′ρ, we haveρ∈Tα′. If ρ′∈Σ + is a strict prefix ofρ, then it cannot hold α′ρ′∈Wby the maximality ofα′, soρ∈K(Tα′). FromIα′= [α′]∼, ([α′]∼, [α]∼,ρ)∈E∼ and α=α′ρwe obtainα∈W(A∼) and Iα= [α]∼. Sinceα∼β, ...

work page
[7]

The number of states ofA∼is clearly equal to the index of∼

work page
[8]

Finally, suppose thatB = (QB,EB,sB,FB) is aW-GDFA that recognizesL

By Equation 2, for everyα,β∈W=W(A∼) we haveα≡A∼β⇐⇒Iα=Iβ⇐⇒[α]∼= [β]∼⇐⇒α∼β, so≡A∼and∼are the same equivalence relation. Finally, suppose thatB = (QB,EB,sB,FB) is aW-GDFA that recognizesL. Notice that by Lemma 17 we have that≡B is right-invariant, it has finite index andL is the union of some ≡B-classes, soA≡B is well-defined, andW(A≡B) =W =W(B). Letϕ:Q≡B→QB...

work page
[9]

s comes first in the total order⪯A

work page
[10]

For every(u′,u,ρ), (v′,v,ρ′)∈E, ifu≺A v and ρ′is not a strict suffix ofρ, thenρ⪯ρ′

work page
[11]

For every(u′,u,ρ), (v′,v,ρ)∈E, ifu≺A v, thenu′≺A v′. Proof. 1. Let u∈Q\{s}. We must prove thats≺A u. Since⪯A is a total order, we only have to prove that ifs and u are⪯A-comparable, then it must bes≺A u. This follows from the fact that for everyα∈Iu we haveϵ≺α, andϵ∈Is

work page
[12]

Letα′∈Iu′and β′∈Iv′

If ρ=ρ′or ρis a strict suffix ofρ′, then the conclusion is immediate, so we can assume that ρ̸=ρ′, ρis not a strict suffix ofρ′and ρ′is not a strict suffix ofρ. Letα′∈Iu′and β′∈Iv′. Then,α′ρ∈Iu and β′ρ′∈Iv. Sinceu≺A v, thenα′ρ≺β′ρ′, Sinceρ̸=ρ′, ρis not a strict suffix ofρ′and ρ′is not a strict suffix ofρ, then we concludeρ≺ρ′

work page
[13]

We must prove thatα′≺β′

Let α′∈Iu′and β′∈Iv′. We must prove thatα′≺β′. From (u′,u,ρ), (v′,v,ρ)∈E we obtain α′ρ∈Iu and β′ρ∈Iv, so fromu≺A v we obtainα′ρ≺β′ρand thusα′≺β′. ◀ Statement of Lemma 25 . LetA = (Q,E,s,F ) be a Wheeler GDFA, and letα∈Σ∗. Then:

work page
[14]

In other words, G≺(α) =Q[1,|G≺(α)|]

If u,v ∈Q are such thatu≺A v and v∈G≺(α), then u∈G≺(α). In other words, G≺(α) =Q[1,|G≺(α)|]

work page
[15]

In other words, G≺ ⊣(α) =Q[1,|G≺ ⊣(α)|]

If u,v ∈Q are such thatu≺A v and v∈G≺ ⊣(α), then u∈G≺ ⊣(α). In other words, G≺ ⊣(α) =Q[1,|G≺ ⊣(α)|]. Proof. 1. If u∈G⊣(α), then there existsβ∈Iu such thatα⊣β. In particular,α⪯β, so u̸∈G≺(α)

work page
[16]

We must prove that v∈G⊣(α)

Assume thatu,v,z ∈Q are such thatu≺A v≺A z and u,z ∈G⊣(α). We must prove that v∈G⊣(α). Sinceu,z∈G⊣(α), then there existβ∈Iu and δ∈Iz such thatα⊣β and α⊣δ. Fix anyγ∈Iv; we only have to prove thatα⊣γ. Fromu≺A v≺A z we obtain β≺γ≺δ. As a consequence, fromα⊣βand α⊣δwe concludeα⊣γ

work page
[17]

We must prove thatβ≺α

Let β∈Iu. We must prove thatβ≺α. Fix anyγ∈Iv. Sinceu≺A v, we haveβ≺γ. Fromv∈G≺(α) we obtainγ≺α, so we concludeβ≺α

work page
[18]

Ifv∈G≺(α), thenu∈G≺(α) by the previous point and sou∈G≺ ⊣(α)

Sincev∈G≺ ⊣(α) , we have eitherv∈G≺(α) orv∈G⊣(α). Ifv∈G≺(α), thenu∈G≺(α) by the previous point and sou∈G≺ ⊣(α). Now assume thatv∈G⊣(α). If u∈G⊣(α), then u∈G≺ ⊣(α) and we are done, so we can assumeu̸∈G⊣(α). Let us prove that it must beu∈G≺(α), which again impliesu∈G≺ ⊣(α). Fix β∈Iu; we must prove that β≺α. Sincev∈G⊣(α), then there existsγ∈Σ∗such thatγα∈Iv....

work page
[19]

the largest integer0≤i≤|Q|such that, ifi≥1, thenQ[i]∈G∗(α)

work page
[20]

the smallest integer0≤j≤|Q|such that, for every0<k <|α|such thatgk >f k, we have in(Q[1,j ],s (α,k))≥gk. Proof. First, note that by Lemma 25 we haveG≺(α) =Q[1,|G≺(α)|],G≺ ⊣(α) =Q[1,|G≺ ⊣(α)|] and, for every 0 < k < α, we have G≺(p(α,|α|−k)) = Q[1,|G≺(p(α,|α|−k)|] and G≺ ⊣(p(α,|α|−k)) = Q[1,|G≺ ⊣(p(α,|α|−k)|]. For every 0 < k < αwe havegk≥fk be- cause G≺(p...

work page
[21]

Let us prove that ifv′,v ∈Q are such thatv∈Q[1,j∗] and (v′,v,s (α,k))∈E, then v′∈Q[1,|G≺(p(α,|α|−k))|]

For everyu′ 1∈Q such that(u′ 1,Q [j∗],s (α,k))∈E we haveu′ 1∈Q[1,|G≺(p(α,|α|−k))|]. Let us prove that ifv′,v ∈Q are such thatv∈Q[1,j∗] and (v′,v,s (α,k))∈E, then v′∈Q[1,|G≺(p(α,|α|−k))|]. This will implyin(Q[1,j∗],s (α,k))≤fk <g k, the desired contradiction. If v = Q[j∗], the conclusion follows because we know that for every u′ 1∈Q such that (u′ 1,Q [j∗],...

work page
[22]

for everyk

For everyu′ 2∈Q such that (u′ 2,Q [j∗],s (α,k))∈E we haveu′ 2∈Q[|G≺ ⊣(p(α,|α|−k))|+ 1,|Q|]. Let us prove that ifv′,v ∈Q are such thatv′∈Q[1,|G≺ ⊣((p(α,|α|−k))|] and (v′,v,s (α,k))∈E, thenv∈Q[1,j∗−1]. This will implyin(Q[1,j∗−1],s (α,k))≥gk, the desired contradiction. It cannot be v = Q[j∗], because this would imply v′∈ Q[|G≺ ⊣(p(α,|α|−k))|+ 1,|Q|]. Now, a...

work page
[23]

|G≺(α)|is the largest integer0≤j≤|Q|such that (i)in(Q[1,j ],s (α,k))≤fk, for every 0 < k <min{r + 1,|α|}, and (ii) everyρ′∈Σk for which there exists1≤ℓ≤j with ρ′∈λ(Q[ℓ]) satisfiesρ′⪯wα,kwith wα,kbeing the largest string inΣk smaller thanα, for every 0<k<r + 1

work page
[24]

|G≺(α)|; b

|G≺ ⊣(α)|is equal to the maximum among: a. |G≺(α)|; b. the largest integer0≤i≤|Q|such that, ifi≥1, then for some0<k <r + 1 there exists ρ′∈Σk∩λ(Q[h]) with α⊣ρ′. c. the smallest integer0≤j≤|Q|such that, for every0<k< min{r + 1,|α|}such that gk >f k, we havein(Q[1,j ],s (α,k))≥gk. Proof. 1. We want to prove that the statement of the corollary is equivalent ...

work page
[25]

Let us prove that the three conditions in the statement are equivalent to the three conditions in Lemma 28. a. The first condition is the same. b. The second condition is equivalent becauseA is ar-GDFA. c. The third condition is equivalent because ifmin{r+1,|α|}≤k< |α|, then|s(α,k)|>r , so gk =fk = 0. ◀ Let us recall the following lemmas for compressed da...

work page
[26]

For every 1≤i≤r, the bit stringOUTi∈{0, 1}ei+n of Definition 29 represented by the data structure of Lemma 34

The number of required bits isnH0(FIN)(1 +o(1)) +O(n)⊆O(n). For every 1≤i≤r, the bit stringOUTi∈{0, 1}ei+n of Definition 29 represented by the data structure of Lemma 34. The total number of required bits is ∑r i=1((ei + n)H0(OUTi)(1 +o(1)) + (ei +n)·O(1)) =O(e +nr). As a consequence, we can solve rank and select queries on eachOUTi in O(1) time. For ever...

work page
[27]

For everyu,v∈Q, ifu≤v, thenu⪯A v

work page
[28]

For every(u′,u,ρ), (v′,v,ρ′)∈E, ifu<v and ρ′is not a strict suffix ofρ, thenρ⪯ρ′

work page
[29]

We say that≤is aWheeler orderonA

For every(u′,u,ρ), (v′,v,ρ)∈E, ifu<v , thenu′≤v′. We say that≤is aWheeler orderonA. Note that if≤is a Wheeler order, thens comes first by Property 1, becauseϵ∈Is and for everyu∈Q\{s}we haveϵ̸∈Iu. As a consequence, Lemma 22 is true also for GNFAs without ϵ-transitions (if in the statement of Lemma 22 we replace⪯A with a Wheeler order ≤). IfA is an NFA, the...

work page

[1] [1]

15 Nicola Cotumaccio, Travis Gagie, Dominik Köppl, and Nicola Prezza

doi:10.1145/3607471. 15 Nicola Cotumaccio, Travis Gagie, Dominik Köppl, and Nicola Prezza. Space-time trade-offs for the lcp array of wheeler dfas. In Franco Maria Nardini, Nadia Pisanti, and Rossano Venturini, editors, String Processing and Information Retrieval, pages 143–156, Cham, 2023. Springer Nature Switzerland. 16 Nicola Cotumaccio and Nicola Prez...

work page doi:10.1145/3607471 2023

[2] [2]

URL:https://www.sciencedirect.com/science/article/pii/ B9780124177505500221, doi:10.1016/B978-0-12-417750-5.50022-1

Academic Press, 1971. URL:https://www.sciencedirect.com/science/article/pii/ B9780124177505500221, doi:10.1016/B978-0-12-417750-5.50022-1 . 31 John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman.Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., USA, 2006. 32 Ramana M. Idury and Mich...

work page doi:10.1016/b978-0-12-417750-5.50022-1 1971

[3] [3]

|Q∼|is equal to the index of∼

work page

[4] [4]

Moreover, ifB is aW-GDFA that recognizesL, thenA≡B is isomorphic toB

≡A∼and∼are the same equivalence relation. Moreover, ifB is aW-GDFA that recognizesL, thenA≡B is isomorphic toB. Proof. DefineA∼= (Q∼,E∼,s∼,F∼) as follows. Q∼={[α]∼|α∈W}. s∼= [ϵ]∼. E∼={([α]∼, [αρ]∼,ρ)|α∈W,ρ∈K(Tα)}. F∼={[α]∼|α∈L}. Let us prove thatA∼is a well-defined GDFA. First, the number of states is finite because∼ has finite index. Next,ϵ∈W, sos∼is wel...

work page

[5] [5]

We must prove that(α∈W)∧(α∼β)

Assume that (α∈W(A∼))∧(Iα= [β]∼). We must prove that(α∈W)∧(α∼β). Since α′,α∈W(A∼), α′is the longest strict prefix ofαinW(A∼), α=α′ρ, andIα′= [α′]∼, then by Remark 9 we obtain that([α′]∼, [β]∼,ρ)∈E∼. The definition ofE∼implies α=α′ρ∈Wand α∼β

work page

[6] [6]

We must prove that(α∈W(A∼))∧(Iα= [β]∼)

Assume that(α∈W)∧(α∼β). We must prove that(α∈W(A∼))∧(Iα= [β]∼). Let us prove that([α′]∼, [α]∼,ρ)∈E∼. Sinceα′,α∈W, we only have to show thatρ∈K(Tα′). Since α=α′ρ, we haveρ∈Tα′. If ρ′∈Σ + is a strict prefix ofρ, then it cannot hold α′ρ′∈Wby the maximality ofα′, soρ∈K(Tα′). FromIα′= [α′]∼, ([α′]∼, [α]∼,ρ)∈E∼ and α=α′ρwe obtainα∈W(A∼) and Iα= [α]∼. Sinceα∼β, ...

work page

[7] [7]

The number of states ofA∼is clearly equal to the index of∼

work page

[8] [8]

Finally, suppose thatB = (QB,EB,sB,FB) is aW-GDFA that recognizesL

By Equation 2, for everyα,β∈W=W(A∼) we haveα≡A∼β⇐⇒Iα=Iβ⇐⇒[α]∼= [β]∼⇐⇒α∼β, so≡A∼and∼are the same equivalence relation. Finally, suppose thatB = (QB,EB,sB,FB) is aW-GDFA that recognizesL. Notice that by Lemma 17 we have that≡B is right-invariant, it has finite index andL is the union of some ≡B-classes, soA≡B is well-defined, andW(A≡B) =W =W(B). Letϕ:Q≡B→QB...

work page

[9] [9]

s comes first in the total order⪯A

work page

[10] [10]

For every(u′,u,ρ), (v′,v,ρ′)∈E, ifu≺A v and ρ′is not a strict suffix ofρ, thenρ⪯ρ′

work page

[11] [11]

For every(u′,u,ρ), (v′,v,ρ)∈E, ifu≺A v, thenu′≺A v′. Proof. 1. Let u∈Q\{s}. We must prove thats≺A u. Since⪯A is a total order, we only have to prove that ifs and u are⪯A-comparable, then it must bes≺A u. This follows from the fact that for everyα∈Iu we haveϵ≺α, andϵ∈Is

work page

[12] [12]

Letα′∈Iu′and β′∈Iv′

If ρ=ρ′or ρis a strict suffix ofρ′, then the conclusion is immediate, so we can assume that ρ̸=ρ′, ρis not a strict suffix ofρ′and ρ′is not a strict suffix ofρ. Letα′∈Iu′and β′∈Iv′. Then,α′ρ∈Iu and β′ρ′∈Iv. Sinceu≺A v, thenα′ρ≺β′ρ′, Sinceρ̸=ρ′, ρis not a strict suffix ofρ′and ρ′is not a strict suffix ofρ, then we concludeρ≺ρ′

work page

[13] [13]

We must prove thatα′≺β′

Let α′∈Iu′and β′∈Iv′. We must prove thatα′≺β′. From (u′,u,ρ), (v′,v,ρ)∈E we obtain α′ρ∈Iu and β′ρ∈Iv, so fromu≺A v we obtainα′ρ≺β′ρand thusα′≺β′. ◀ Statement of Lemma 25 . LetA = (Q,E,s,F ) be a Wheeler GDFA, and letα∈Σ∗. Then:

work page

[14] [14]

In other words, G≺(α) =Q[1,|G≺(α)|]

If u,v ∈Q are such thatu≺A v and v∈G≺(α), then u∈G≺(α). In other words, G≺(α) =Q[1,|G≺(α)|]

work page

[15] [15]

In other words, G≺ ⊣(α) =Q[1,|G≺ ⊣(α)|]

If u,v ∈Q are such thatu≺A v and v∈G≺ ⊣(α), then u∈G≺ ⊣(α). In other words, G≺ ⊣(α) =Q[1,|G≺ ⊣(α)|]. Proof. 1. If u∈G⊣(α), then there existsβ∈Iu such thatα⊣β. In particular,α⪯β, so u̸∈G≺(α)

work page

[16] [16]

We must prove that v∈G⊣(α)

Assume thatu,v,z ∈Q are such thatu≺A v≺A z and u,z ∈G⊣(α). We must prove that v∈G⊣(α). Sinceu,z∈G⊣(α), then there existβ∈Iu and δ∈Iz such thatα⊣β and α⊣δ. Fix anyγ∈Iv; we only have to prove thatα⊣γ. Fromu≺A v≺A z we obtain β≺γ≺δ. As a consequence, fromα⊣βand α⊣δwe concludeα⊣γ

work page

[17] [17]

We must prove thatβ≺α

Let β∈Iu. We must prove thatβ≺α. Fix anyγ∈Iv. Sinceu≺A v, we haveβ≺γ. Fromv∈G≺(α) we obtainγ≺α, so we concludeβ≺α

work page

[18] [18]

Ifv∈G≺(α), thenu∈G≺(α) by the previous point and sou∈G≺ ⊣(α)

Sincev∈G≺ ⊣(α) , we have eitherv∈G≺(α) orv∈G⊣(α). Ifv∈G≺(α), thenu∈G≺(α) by the previous point and sou∈G≺ ⊣(α). Now assume thatv∈G⊣(α). If u∈G⊣(α), then u∈G≺ ⊣(α) and we are done, so we can assumeu̸∈G⊣(α). Let us prove that it must beu∈G≺(α), which again impliesu∈G≺ ⊣(α). Fix β∈Iu; we must prove that β≺α. Sincev∈G⊣(α), then there existsγ∈Σ∗such thatγα∈Iv....

work page

[19] [19]

the largest integer0≤i≤|Q|such that, ifi≥1, thenQ[i]∈G∗(α)

work page

[20] [20]

the smallest integer0≤j≤|Q|such that, for every0<k <|α|such thatgk >f k, we have in(Q[1,j ],s (α,k))≥gk. Proof. First, note that by Lemma 25 we haveG≺(α) =Q[1,|G≺(α)|],G≺ ⊣(α) =Q[1,|G≺ ⊣(α)|] and, for every 0 < k < α, we have G≺(p(α,|α|−k)) = Q[1,|G≺(p(α,|α|−k)|] and G≺ ⊣(p(α,|α|−k)) = Q[1,|G≺ ⊣(p(α,|α|−k)|]. For every 0 < k < αwe havegk≥fk be- cause G≺(p...

work page

[21] [21]

Let us prove that ifv′,v ∈Q are such thatv∈Q[1,j∗] and (v′,v,s (α,k))∈E, then v′∈Q[1,|G≺(p(α,|α|−k))|]

For everyu′ 1∈Q such that(u′ 1,Q [j∗],s (α,k))∈E we haveu′ 1∈Q[1,|G≺(p(α,|α|−k))|]. Let us prove that ifv′,v ∈Q are such thatv∈Q[1,j∗] and (v′,v,s (α,k))∈E, then v′∈Q[1,|G≺(p(α,|α|−k))|]. This will implyin(Q[1,j∗],s (α,k))≤fk <g k, the desired contradiction. If v = Q[j∗], the conclusion follows because we know that for every u′ 1∈Q such that (u′ 1,Q [j∗],...

work page

[22] [22]

for everyk

For everyu′ 2∈Q such that (u′ 2,Q [j∗],s (α,k))∈E we haveu′ 2∈Q[|G≺ ⊣(p(α,|α|−k))|+ 1,|Q|]. Let us prove that ifv′,v ∈Q are such thatv′∈Q[1,|G≺ ⊣((p(α,|α|−k))|] and (v′,v,s (α,k))∈E, thenv∈Q[1,j∗−1]. This will implyin(Q[1,j∗−1],s (α,k))≥gk, the desired contradiction. It cannot be v = Q[j∗], because this would imply v′∈ Q[|G≺ ⊣(p(α,|α|−k))|+ 1,|Q|]. Now, a...

work page

[23] [23]

|G≺(α)|is the largest integer0≤j≤|Q|such that (i)in(Q[1,j ],s (α,k))≤fk, for every 0 < k <min{r + 1,|α|}, and (ii) everyρ′∈Σk for which there exists1≤ℓ≤j with ρ′∈λ(Q[ℓ]) satisfiesρ′⪯wα,kwith wα,kbeing the largest string inΣk smaller thanα, for every 0<k<r + 1

work page

[24] [24]

|G≺(α)|; b

|G≺ ⊣(α)|is equal to the maximum among: a. |G≺(α)|; b. the largest integer0≤i≤|Q|such that, ifi≥1, then for some0<k <r + 1 there exists ρ′∈Σk∩λ(Q[h]) with α⊣ρ′. c. the smallest integer0≤j≤|Q|such that, for every0<k< min{r + 1,|α|}such that gk >f k, we havein(Q[1,j ],s (α,k))≥gk. Proof. 1. We want to prove that the statement of the corollary is equivalent ...

work page

[25] [25]

Let us prove that the three conditions in the statement are equivalent to the three conditions in Lemma 28. a. The first condition is the same. b. The second condition is equivalent becauseA is ar-GDFA. c. The third condition is equivalent because ifmin{r+1,|α|}≤k< |α|, then|s(α,k)|>r , so gk =fk = 0. ◀ Let us recall the following lemmas for compressed da...

work page

[26] [26]

For every 1≤i≤r, the bit stringOUTi∈{0, 1}ei+n of Definition 29 represented by the data structure of Lemma 34

The number of required bits isnH0(FIN)(1 +o(1)) +O(n)⊆O(n). For every 1≤i≤r, the bit stringOUTi∈{0, 1}ei+n of Definition 29 represented by the data structure of Lemma 34. The total number of required bits is ∑r i=1((ei + n)H0(OUTi)(1 +o(1)) + (ei +n)·O(1)) =O(e +nr). As a consequence, we can solve rank and select queries on eachOUTi in O(1) time. For ever...

work page

[27] [27]

For everyu,v∈Q, ifu≤v, thenu⪯A v

work page

[28] [28]

For every(u′,u,ρ), (v′,v,ρ′)∈E, ifu<v and ρ′is not a strict suffix ofρ, thenρ⪯ρ′

work page

[29] [29]

We say that≤is aWheeler orderonA

For every(u′,u,ρ), (v′,v,ρ)∈E, ifu<v , thenu′≤v′. We say that≤is aWheeler orderonA. Note that if≤is a Wheeler order, thens comes first by Property 1, becauseϵ∈Is and for everyu∈Q\{s}we haveϵ̸∈Iu. As a consequence, Lemma 22 is true also for GNFAs without ϵ-transitions (if in the statement of Lemma 22 we replace⪯A with a Wheeler order ≤). IfA is an NFA, the...

work page