Over the years, bisimulations have emerged as a pervasive paradigm, finding applications in numerous areas, including concurrency theory, model checking, automata theory, logic, programming languages and category theory. In this paper, we establish a connection between bisimulations and data compression. More precisely, we study the relationship between bisimulations and Wheeler automata (Alanko et al., SODA 2020), a class of automata that has received considerable attention in recent years. The standard notion of bisimulation is not appropriate, so we introduce Wheeler bisimulations, that is, bisimulations that respect the convex structure of the considered Wheeler automata. We show that Wheeler bisimilarity induces a unique minimal Wheeler NFA (analogously to standard bisimulations). In particular, in the deterministic case, we retrieve the minimal Wheeler deterministic automaton of a given language. We also show that the minimal Wheeler NFA induced by Wheeler bisimulations can be built in linear time. This is in contrast with standard bisimulations, for which the corresponding minimal NFA can be built in O(m log n) time (where m is the number of edges and n is the number of states) by adapting Paige-Tarjan partition refinement algorithm. Compared to previous state-reduction techniques, our bisimulation-induced construction is the first for which (i) we obtain a canonical Wheeler NFA and (ii) the resulting Wheeler NFA can be built in linear time.

The circular dictionary matching problem is an extension of the classical dictionary matching problem where every string in the dictionary is interpreted as a circular string: after reading the last character of a string, we can move back to its first character. The circular dictionary matching problem is motivated by applications in bioinformatics and computational geometry. In 2011, Hon et al. [ISAAC 2011] showed how to efficiently solve circular dictionary matching queries within compressed space by building on Mantaci et al.’s eBWT and Sadakane’s compressed suffix tree. The proposed solution is based on the assumption that the strings in the dictionary are all distinct and non-periodic, no string is a circular rotation of some other string, and the strings in the dictionary have similar lengths. In this paper, we consider arbitrary dictionaries, and we show how to solve circular dictionary matching queries in O((m + occ) log n) time within compressed space using n log σ (1 + o(1)) + O(n) + O(d log n) bits, where n is the total length of the dictionary, m is the length of the pattern, occ is the number of occurrences, d is the number of strings in the dictionary and σ is the size of the alphabet. Our solution is based on an extension of the suffix array to arbitrary dictionaries and a sampling mechanism for the LCP array of a dictionary inspired by recent results in graph indexing and compression.

In a well-studied variant of the dictionary matching problem, the strings in the dictionary are circular. Hon et al. [ISAAC 2011] showed how to solve circular dictionary queries efficiently within compressed space under some technical assumptions on the dictionary. Several papers studied the problem of building efficiently the required data structures, until Bannai et al. finally achieved linear time [CPM 2021] by presenting an algorithm for building the bijective Burrows-Wheeler transform. More precisely, to support circular dictionary matching queries efficiently, Hon et al. rely on Mantaci et al.’s eBWT, so Boucher et al. described a direct linear-time algorithm for building the eBWT [SPIRE 2021]. Very recently, it was shown how to solve circular dictionary queries in full generality by introducing a suffix array for arbitrary dictionaries [CPM 2025]. To build the suffix array and support circular dictionary queries, one needs to consider a problem more general than constructing the eBWT, because it is necessary to compute the ordered partition of all (infinite) suffixes with respect to the lexicographic order. In this paper, we provide a linear-time construction algorithm that extends Ko and Aluru’s algorithm for building the suffix array. As a by-product, we show that induced sorting yields a new linear-time algorithm to compute the primitive root of a string.

Abstract In the String Matching in Labeled Graphs (SMLG) problem, we need to determine whether a pattern string appears on a given labeled graph or a given automaton. Under the Orthogonal Vectors hypothesis, the SMLG problem cannot be solved in subquadratic time. In typical bioinformatics applications, pattern matching algorithms should be both fast and space-efficient, so we need to determine useful classes of graphs on which the SLMG problem can be solved efficiently. In this paper, we improve on a recent result that shows how to solve the SMLG problem in linear time on the compressed representation of Wheeler generalized automata, a class of string-labeled automata that extend de Bruijn graphs. More precisely, we show how to remove the assumption that the automata contain no $$\epsilon$$ -transitions (namely, edges labeled with the empty string), while retaining the same time and space bounds. This is a significant improvement because $$\epsilon$$ -transitions may considerably reduce the size of an automaton recognizing a given language, while capturing the complexity of regular expressions (through Thompson’s construction for converting a regular expression into an equivalent automaton). We prove that, to enable $$\epsilon$$ -transitions, we only need to store two additional bitvectors that can be constructed in linear time.

The LCP array is an important tool in stringology, allowing to speed up pattern matching algorithms and enabling compact representations of the suffix tree. Recently, Conte et al. [DCC 2023] and Cotumaccio et al. [SPIRE 2023] extended the definition of this array to Wheeler DFAs and, ultimately, to arbitrary labeled graphs, proving that it can be used to efficiently solve matching statistics queries on the graph’s paths. In this paper, we provide the first efficient algorithm building the LCP array of a directed labeled graph with n nodes and m edges labeled over an alphabet of size σ. The first step is to transform the input graph G into a deterministic Wheeler pseudoforest G_{is} with O(n) edges encoding the lexicographically- smallest and largest strings entering in each node of the original graph. Using state-of-the-art algorithms, this step runs in O(min{mlog n, m+n²}) time on arbitrary labeled graphs, and in O(m) time on Wheeler DFAs. The LCP array of G stores the longest common prefixes between those strings, i.e. it can easily be derived from the LCP array of G_{is}. After arguing that the natural generalization of a compact-space LCP-construction algorithm by Beller et al. [J. Discrete Algorithms 2013] runs in time Ω(nσ) on pseudoforests, we present a new algorithm based on dynamic range stabbing building the LCP array of G_{is} in O(nlog σ) time and O(nlogσ) bits of working space. Combined with our reduction, we obtain the first efficient algorithm to build the LCP array of an arbitrary labeled graph. An implementation of our algorithm is publicly available at https://github.com/regindex/Labeled-Graph-LCP.

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. Giammaresi 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 𝒲(𝒜) associated with a generalized automaton 𝒜. The set 𝒲(𝒜) is always trivially equal to the set of all prefixes of the language recognized by the automaton, if 𝒜 is a conventional automaton, but this need not be true for generalized automata. By fixing 𝒲(𝒜), we are able to 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 𝒲(𝒜) leads to applications for pattern matching and data compression. Wheeler automata [TCS 2017, SODA 2020] are a popular class of automata that can be compactly stored using e log σ (1 + o(1)) + O(e) bits (e being the number of edges, σ being the size of the alphabet) in such a way that pattern matching queries can be solved in Õ(m) time (m being the length of the pattern). In the paper, we show how to extend these results to generalized automata. More precisely, a Wheeler generalized automata can be stored using 𝔢 log σ (1 + o(1)) + O(e + rn) bits so that pattern matching queries can be solved in Õ(rm) time, where 𝔢 is the total length of all edge labels, r is the maximum length of an edge label and n is the number of states.

Matching statistics were introduced to solve the approximate string matching problem, which is a recurrent subroutine in bioinformatics applications. In 2010, Ohlebusch et al. [SPIRE 2010] proposed a time and space efficient algorithm for computing matching statistics which relies on some components of a compressed suffix tree - notably, the longest common prefix (LCP) array. In this paper, we show how their algorithm can be generalized from strings to Wheeler deterministic finite automata. Most importantly, we introduce a notion of LCP array for Wheeler automata, thus establishing a first clear step towards extending (compressed) suffix tree functionalities to labeled graphs.

In the past thirty years, numerous algorithms for building the suffix array of a string have been proposed. In 2021, the notion of suffix array was extended from strings to DFAs, and it was shown that the resulting data structure can be built in O(m² + n^{5/2}) time, where n is the number of states and m is the number of edges [SODA 2021]. Recently, algorithms running in O(mn) and O(n²log n) time have been described [CPM 2023]. In this paper, we improve the previous bounds by proposing an O(n²) recursive algorithm inspired by Farach’s algorithm for building a suffix tree [FOCS 1997]. To this end, we provide insight into the rich lexicographic and combinatorial structure of a graph, so contributing to the fascinating journey which might lead to solve the long-standing open problem of building the suffix tree of a graph.

The states of a finite-state automaton 𝒩 can be identified with collections of words in the prefix closure of the regular language accepted by 𝒩. But words can be ordered, and among the many possible orders a very natural one is the co-lexicographic order. 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 articles automata admitting a total co-lexicographic ( co-lex for brevity) ordering of states have been proposed and studied. Such class of ordered automata — Wheeler automata — turned out to require just a constant number of bits per transition to be represented and enable regular expression matching queries in constant time per matched character. Unfortunately, not all automata can be totally ordered as previously outlined. In the present work, we lay out a new theory showing that all automata can always be partially ordered, and an intrinsic measure of their complexity can be defined and effectively determined, namely, the minimum width p of one of their admissible co-lex partial orders –dubbed here the automaton’s co-lex width . We first show that this new measure captures at once the complexity of several seemingly-unrelated hard problems on automata. Any NFA of co-lex width p : (i) has an equivalent powerset DFA whose size is exponential in p rather than (as a classic analysis shows) in the NFA’s size; (ii) can be encoded using just Θ(log p ) bits per transition; (iii) admits a linear-space data structure solving regular expression matching queries in time proportional to p 2 per matched character. Some consequences of this new parameterization of automata are that PSPACE-hard problems such as NFA equivalence are FPT in p , and quadratic lower bounds for the regular expression matching problem do not hold for sufficiently small p . Having established that the co-lex width of an automaton is a fundamental complexity measure, we proceed by (i) determining its computational complexity and (ii) extending this notion from automata to regular languages by studying their smallest-width accepting NFAs and DFAs. In this work we focus on the deterministic case and prove that a canonical minimum-width DFA accepting a language ℒ–dubbed the Hasse automaton ℋ of ℒ–can be exhibited. ℋ provides, in a precise sense, the best possible way to (partially) order the states of any DFA accepting ℒ, as long as we want to maintain an operational link with the (co-lexicographic) order of ℒ’s prefixes. Finally, we explore the relationship between two conflicting objectives: minimizing the width and minimizing the number of states of a DFA. In this context, we provide an analogue of the Myhill-Nerode Theorem for co-lexicographically ordered regular languages.

Wheeler DFAs (WDFAs) are a sub-class of finite-state automata which is playing an important role in the emerging field of compressed data structures: as opposed to general automata, WDFAs can be stored in just$\log\sigma+O(1)$bits per edge,$\sigma$being the alphabet's size, and support optimal-time pattern matching queries on the substring closure of the language they recognize. An important step to achieve further compression is minimization. When the input$\mathcal{A}$is a general deterministic finite-state automaton (DFA), the state-of-the-art is represented by the classic Hopcroft's algorithm, which runs in$O(\vert \mathcal{A}\vert \log\vert \mathcal{A}\vert )$time. This algorithm stands at the core of the only existing minimization algorithm for Wheeler DFAs, which inherits its complexity. In this work, we show that the minimum WDFA equivalent to a given input WDFA can be computed in linear$O(\vert \mathcal{A}\vert )$time. When run on de Bruijn WDFAs built from real DNA datasets, an implementation of our algorithm reduces the number of nodes from 14% to 51% at a speed of more than 1 million nodes per second.

For the first time we provide a succinct pattern matching index for arbitrary graphs that can be built in polynomial time, while improving both space and query time bounds from [SODA 2021]. We show that, given an edge-labeled graph$G=(V, E)$, there exists a data structure of$\vert E/_{\leq G}\vert (\lceil\log\vert \Sigma\vert \rceil+\lceil\log q\rceil+2)\cdot(1+o(1))+\vert V/_{\leq G}\vert \cdot(1+o(1))$bits which supports pattern matching on$G$in$O(\vert P\vert \cdot q^{2}\cdot\log(q\cdot\vert \Sigma\vert))$time, where$G/_{\leq G}=(V/_{\leq G}, E/_{\leq G})$is a quotient graph obtained by collapsing some nodes in$G$and$q$is the width of the maximum co-lex relation on$G$. Our results have relevant applications in automata theory: we can use our data structure to decide whether a string belongs to the language recognized by a given automaton, and we can capture the degree of nondeterminism of an NFA.

An index for a finite automaton is a powerful data structure that supports locating paths labeled with a query pattern, thus solving pattern matching on the underlying regular language. The problem is hard in the general case: a recent conditional lower bound suggests that, in the worst case, deciding at query time whether a pattern of length m belongs to the substring closure of the language accepted by requires time. On the other hand, Gagie et al. [TCS 2017] introduced a subclass of automata that allow an optimal Õ(m)-time solution based on prefix-sorting the states in a total order. In this paper, we solve the long-standing problem of indexing arbitrary finite automata, matching the above bounds. Our solution consists in finding a partial co-lexicographic order of the states and proving, as in the total order case, that states reached by a given string form one interval on the partial order, thus enabling indexing. We provide a lower bound stating that such an interval requires O(p) words to be represented, p being the order's width (i.e. the size of its largest antichain). Indeed, we show that p determines the complexity of several fundamental problems on finite automata: Letting σ be the alphabet size, we provide an encoding for NFAs using [log σ] + 2[log p] + 2 bits per transition and a smaller encoding for DFAs using [log σ] + [log p] + 2 bits per transition. This is achieved by generalizing the Burrows-Wheeler transform to arbitrary automata. We show that indexed pattern matching can be solved in Õ(m · p2) query time on NFAs. We provide a polynomial-time algorithm to index DFAs, while matching the optimal value for p. On the other hand, we prove that the problem is NP-hard on NFAs. We show that, in the worst case, the classic power-set construction algorithm for NFA determinization generates an equivalent DFA of size 2p(n–p+1) – 1, where n is the number of NFA's states. Contribution (i) provides a new compression paradigm for labeled graphs. Contributions (ii)-(iii) solve the regular language indexing problem, notably with a polynomial-time solution for DFAs. Contribution (iv) implies a new FPT analysis for the complexity of classic algorithms on automata, including membership and equivalence (the latter being PSPACE-complete when input automata are NFAs).