arXiv CSopen access

Ranked MSO-enumeration over compressed words

Ranked MSO-enumeration over compressed words Markus Lohrey # Universität Siegen, Germany

arXiv:2606.03947v1 [cs.DS] 2 Jun 2026

Abstract It is shown that the ranked query enumeration problem for a fixed MSO-query on strings can be solved with linear preprocessing and constant delay in the grammar-compressed setting, where the input string is given by a so-called straight-line program, i.e., a context-free grammar that produces exactly one string. Moreover, ‘ranked’ means that the output tuples of the MSO-query are printed in a specific order that has to be MSO-definable. This is the first result for ranked query enumeration on compressed data. A corollary of this result is that for a fixed polyregular function f and a word w that is given by a straight-line program of size n, one can list after preprocessing time O(n) the symbols in f (w) from left to right with constant delay, which generalizes a result of Bojanczyk for the case where w is uncompressed. The proofs for these results are based on factorization trees, which are made accessible to the grammar-compressed setting (a contribution of independent interest). 2012 ACM Subject Classification Theory of computation → Database query processing and optimization (theory) Keywords and phrases monadic second-order queries, enumeration algorithms, grammar compression, factorization trees

1

Introduction

The evaluation of queries formulated in monadic second order logic (MSO) is a classical problem in database theory and finite model theory. If we allow arbitrary structures, then already the model-checking problem for MSO (and even first-order logic) is PSPACE-complete. Here, the input consists of the structure and the formula. In real applications from data base theory or verification, the structure can be huge whereas the formula is often small. This motivates the study of data complexity, where the formula is fixed and not part of the input. Still, MSO-model-checking is hard for all levels of the polynomial time hierarchy with respect to data complexity. In order to get efficient algorithms, one has to restrict the class of allowed input structures. A famous result in this context is Courcelle’s meta-theorem [13], saying that the data complexity of MSO-model-checking is linear time on the class of all structures of treewidth at most k (for every fixed k). In this paper, we will only consider data complexity. The model-checking problem for MSO is the same as the evaluation problem for boolean MSO-queries. In data base theory, one is usually interested in queries with free variables and the computation of all query answers. Here, we consider MSO-queries Φ(x1 , . . . , xk ) with free first-order variables xi . The goal is then to compute all tuples (a1 , . . . , ak ) in an input structure A (that models the input data) such that A |= Φ(a1 , . . . , ak ) holds. The number of these tuples is clearly bounded by |A|k which can be very large in applications, where the input data are large. In order to have a reasonable notion of efficient algorithms for computing query answers, the concept of enumeration algorithms has been introduced. Such an algorithm starts for a given input structure A with a preprocessing phase building a suitable data structure for the enumeration phase that starts right after the preprocessing phase. In the enumeration phase the algorithm computes all tuples (a1 , . . . , ak ) satisfying the (fixed) MSO-query Φ(x1 , . . . , xk ) without producing a tuple twice. The gold standard for the efficiency of an enumeration algorithm is a linear preprocessing time O(|A|) and constant delay, where the latter means that there is a constant bounding the following computation times: (i) the time for computing the first output tuple, (ii) the time between outputting

2

Ranked MSO-enumeration over compressed words

two tuples, and (iii) the time between outputting the last tuple and final termination. Note that constant delay makes only sense for data complexity since otherwise the length k of the tuples would not be fixed. Moreover constant delay assumes that every element of the input structure A fits into constantly many output registers. Note that in the above setting, the MSO-formula only contains free first-order formulas. One may also allow queries Φ(x1 , . . . , xk , X1 , . . . , Xl ) with free set variable Xi . Although this is not the focus of the paper, we mention it because some of the related papers cited below consider this more general setting. Clearly, the output tuples then no longer fit into constant space and therefore cannot be printed in constant time. The best possible delay bound is then output-linear delay, meaning that the delay for printing an output tuple is linearly bounded in the size of the tuple. For a fixed query Φ(x1 , . . . , xk ) containing only free first-order variables, output-linear delay is equivalent to constant delay. Enumeration algorithms with linear preprocessing and constant delay or output-linear delay are known for several classes of queries and structures, including MSO-queries on strings, trees and structures with bounded treewidth [3, 5, 14, 21, 22, 31, 32] and for regular document spanners (which is a subclass of MSO-queries) on strings [4, 15]. As mentioned above, the input structure for query evaluation can be huge in applications. This has motivated the investigation of query enumeration algorithms for structures that are given in a compressed form. The compression format that has been studied so far in the context of query enumeration is grammar-compression. For strings this means that the input string is given by a context-free grammar that produces exactly one string. Such grammars are also known as straight-line algorithm (SLP for short) and have received a lot of attention in data compression, information theory, stringology and even areas like computational topology and group theory; see the survey [24] for more details. In data base theory, query enumeration algorithms on compressed structures have been first studied in the context of strings and document spanners [34, 35, 36]. This work has been extended to full MSO in [29], where it is shown that for a fixed MSO-query and a given input word that is represented by an SLP G, the set of all query answers can be enumerated with linear processing (meaning time O(|G|) where |G| is the size of the SLP G) and output-linear delay (the authors of [29] consider MSO-formulas with free set variables). In [28] this result has been extended to unranked trees that are given by so-called forest straight-line programs [17] (an extension of SLPs that allows to compress unranked trees), whereas [27] goes one step further to grammar-compressed graphs of bounded degree but restricts to queries expressed in first-order logic. A drawback in all the above mentioned results on query answer enumeration is the fact that the output tuples are printed in some opaque order that cannot be controlled by the user. To overcome this drawback, researchers have developed the concept of ranked enumeration, where the output tuples are printed in a specific order that can be specified in a suitable formalism. Ranked enumeration for MSO-queries has been considered in [12, 19] for strings and [2] for trees. In [12, 19], query answers are enumerated in the order of decreasing weights, where the weight of an input word is an element of an ordered abelian group that is computed by a so-called cost transducer. In contrast, [2] uses ranking functions satisfying a subset-monotonicity property. In the worst case, the delay of the enumeration algorithms from [2, 12, 19] is logarithmic in the size of the input structure (with some improvements in [19] over [12]). Moreover, the input structure is not compressed in [2, 12, 19]. Ranked enumeration on compressed data has not been studied so far. In this paper, we make the first step in this direction. We consider a fixed MSO-formula with k free first-order variables, an SLP-compressed input string and a

M. Lohrey

linear order on k-tuples of string positions that is MSO-definable (a good example for such an order is the lexicographic order on k-tuples of positions; see Example 2.3). Our main result (Theorem 5.1) states that in this setting, the set of all query answers can be enumerated in the specified order with linear preprocessing and constant delay. Before we say something about the proof ingredients, let us mention an easy corollary concerning polyregular functions. These string-to-string functions can be characterized in many different ways (e.g. by MSO-interpretations, pebble-two-way transducers, certain imperative as well as functional programming languages, and as the class obtained from certain primitive functions by closing under composition) and have received a lot of attention in recent years; see [8, 9] for more details. In [8], it is shown that for a fixed polyregular function f and a given input word w, one can enumerate the symbols in f (w) from left to right after linear time preprocessing in constant delay. Note that |f (w)| is bounded polynomially in |w|, where the polynomial depends on f . Recently, it has been shown that polyregular functions do not preserve compression, meaning that there exists a specific polyregular function f , a family of strings wn such that every wn has an SLP of size O(n), whereas the size of a smallest SLP for f (n) is lower bounded by 2n ; see [10, Lemma 13] and its proof. Our corollary of Theorem 5.1 extends the above mentioned enumeration result from [8] to the compressed setting: For every fixed polyregular function f and a given input SLP G producing the string w, one can enumerate the symbols in f (w) from left to right after a linear time preprocessing in constant delay. We conclude the introduction with a few words on the proof ingredients for our main result. A main tool are factorization trees for words, which have been applied in database theory before [11]. A factorization tree for a word w ∈ Σ+ with respect to a morphism h : Σ∗ → M into a finite monoid is a constant-height parse tree of w such that for every node with more than two children, all children evaluate in M to the same idempotent element of M . The existence of such factorization trees for every word has been shown by Simon [37]. In our setting, the word w is given by an SLP G. We introduce the notion of a Simon SLP, which, roughly speaking, is an SLP that is compatible with the structure of a factorization tree for the string produced by the SLP. We show in Section 3 that every SLP can be transformed in linear time into an equivalent Simon SLP. We then combine these Simon SLPs with a technique for constant-time two-way traversal of SLP-compressed strings from [26] (this technique has to be suitably extended for our purpose; see Section 4) in order to extend the above mentioned algorithm from [8] for enumerating the symbols in the image f (w) of a fixed polyregular function f to the setting, where w is given by an SLP. Related work. We mentioned already the existing work on ranked MSO-enumeration. Related to our work is also the following recent result of Muñoz [30] on direct ranked access: For a fixed MSO-query (containing only free first-order variables) and a given SLP of size n producing a string of length N , one can compute in time O(n) a data structure that allows to compute for a given number m in time O(log N ) the lexicographically m-th query answer.

2

Preliminaries

For a mapping f : M → N and a subset P ⊆ M we write f ↾P : P → N for the restriction of f to P . For integers i ≤ j we use the notation [i, j] = {k ∈ Z : i ≤ k ≤ j}. Given an alphabet of symbols Σ, Σ∗ denotes the set of all finite words over the alphabet Σ, including the empty word ε. The set of non-empty words is denoted by Σ+ = Σ∗ \ {ε}. The length of a word s is denoted with |s|. If s = a1 a2 · · · an (ai ∈ Σ) then we define

3

4

Ranked MSO-enumeration over compressed words

s[i] = ai for i ∈ [1, n] and s[i, j] = ai ai+1 · · · aj for 1 ≤ i ≤ j ≤ n. The alphabet of s is alph(s) = {a1 , a2 , . . . , an }. Finite automata and transducers. We assume some knowledge from automata theory; see e.g. [33] for further details. Consider a nondeterministic finite automaton A over the alphabet Σ with n states. We say that A is a trim NFA if every state of A lies on a path from the initial state to a final state. Clearly, every NFA can be transformed into an equivalent trim NFA without increasing the number of states. One can represent the dynamics of an NFA A by a monoid of boolean (n × n)-matrices. For this, assume w.l.o.g. that the set of states of A is {1, . . . , n}. For every letter a ∈ Σ define the boolean matrix Ma by setting the entry of Ma in row i and column j to 1 if there is a transition from state i to state j reading the letter a, otherwise the entry is 0. Then Bool(A) is the monoid generated by all matrices Ma (a ∈ Σ) under multiplication of boolean matrices (where scalar addition and multiplication are the boolean operators ∨ and ∧, respectively). For a subset Γ ⊆ Σ we write Bool(A, Γ) for the submonoid of Bool(A) generated by all matrices Ma with a ∈ Γ. If h : Γ∗ → Bool(A, Γ) is the morphism defined by a 7→ Ma for a ∈ Γ and w ∈ Γ∗ , then the entry in row i and column j of the matrix h(w) is 1 if and only if there is a path in A from state i to state j that is labelled with the word w. A nondeterministic transducer T is a nondeterministic automaton with output that reads in each transition exactly one input symbol a, outputs a word u over the output alphabet and changes the state from p to q. This transition is also written as (p, a/u, q). Since T is nondeterministic, a word s is translated into a finite set of words T (s). Trees. In the following we consider finite rooted ordered trees. Here, ordered means that the children of a node u are linearly ordered (when drawing a tree this is the usual left-to-right order). We denote this linear order by <u . These linear orders <u induce the depth-first left-to-right order <T on the nodes of T : For nodes v1 ̸= v2 of T we have v1 <T v2 if either v2 is a descendant of v1 or there is a node u with two children u1 <u u2 such that vi is a descendant of ui for i ∈ {1, 2}. If v2 is a descendant of v1 in the tree T then we write [v1 , v2 ] for the unique path from v1 down to v2 . Often, we identify [v1 , v2 ] with the set of nodes on this path.

2.1

Factorization trees

Throughout this section, we fix a finite alphabet Σ, a finite monoid M , and a monoid homomorphism h : Σ∗ → M . By E(M ) = {e ∈ M : e2 = e} we denote the set of idempotents of M . A factorization tree for a word s = a1 a2 · · · an (ai ∈ Σ) with respect to h is a finite rooted ordered tree T such that the following holds: T has n leaves v1 <T v2 <T · · · <T vn , where vi is labelled with ai . This allows to assign to every node u of T a word w(u) ∈ Σ∗ : w(vi ) = ai and if u is an internal node with children u1 <u u2 <u · · · <u uk then w(u) = w(u1 )w(u2 ) · · · w(uk ) (hence, w(r) = s if r is the root of T ). The monoid element h(u) ∈ M associated to node u is h(u) = h(w(u)). Every node u is either a leaf or has at least two children. If u has k ≥ 3 children u1 , u2 , . . . , uk then there is an e ∈ E(M ) such that h(ui ) = e for all 1 ≤ i ≤ k (and hence also h(u) = e). In this case we call u an idempotent node. Nodes with exactly two children are called binary nodes. Figure 1 shows a factorization for the word abccabdabcabe, where the i-th leaf is labelled with the i-th letter. We assume that h(ab) = h(c) = h(e) is idempotent.

M. Lohrey

5

c

d c a

b

c

a a

b a

e b

b

Figure 1 A factorization tree.

Simon [37] showed that every word s ∈ Σ+ has a factorization tree of height at most 9|M |. The bound in the following theorem is due to Kufleitner [23] and is sharp. ▶ Theorem 2.1. Every word s ∈ Σ+ has a factorization tree of height at most 3|M |. A factorization tree T can (as any rooted ordered tree) be written as an expression γ(T ) with brackets ( and ). Formally, if T consists of a single leaf that is labelled with a ∈ Σ then γ(T ) = (a). Otherwise, if the root of T has k ≥ 2 children, let Ti (1 ≤ i ≤ k) be the subtree of T rooted in the i-th child of the root. Then we have γ(T ) = (γ(T1 )γ(T2 ) · · · γ(Tn )). Every subtree T ′ of T can identified with an occurrence of γ(T ′ ) in γ(T ) in the natural way. Since the nesting depth of brackets is bounded by the constant 3|M |, the set {γ(T ) : T is a factorization tree w.r.t. h of height at most 3|M | for some word s ∈ Σ+ } is a regular language over the alphabet Σ ∪ {(, )}. This implies the following result that is stated in [7, Lemma 3]. ▶ Theorem 2.2. There is a nondeterministic transducer Th (that only depends on the monoid M and the morphism h : Σ∗ → M ) such that for every word s ∈ Σ∗ we have Th (s) = {γ(T ) : T is a factorization tree for s w.r.t. h of height at most 3|M |}.

2.2

Monadic second-order logic over words

We assume that the reader is familiar with monadic second-order (MSO) logic over words; see [38] for more details. Here, a non-empty word w = a1 a2 · · · an ∈ Σ+ of length n is identified with a finite structure (a so-called word structure) consisting of the universe [1, n] (all positions in the word w), the binary relation < (the standard order on integers) and the unary relations Pa = {i : ai = a} for a ∈ Σ. We will consider MSO-formulas over words with free first-order variables that range over positions in words. For an MSO-formula Φ and first-order variables x1 , . . . , xk we write Φ(x1 , . . . , xk ) to express that x1 , . . . , xk are the free variables of Φ. For a word w ∈ Σ+ of length n, an MSO-formula Φ(x1 , . . . , xk ) and positions p1 , . . . pk ∈ [1, n] we write w |= Φ(p1 , . . . , pk ) to express that Φ is true in the word w when every variable xi takes the value pi . Moreover, we define JΦKw := {(p1 , . . . pk ) ∈ [1, n]k : w |= Φ(p1 , . . . , pk )}.

2.3

Polyregular functions and MSO-interpretations

As already mentioned in the introduction, the class of polyregular string-to-string functions has several alternative definitions. For us, the important one is the one based on MSOstring-to-string interpretations [9]. For this, consider two finite alphabets Σ and Γ. An

6

Ranked MSO-enumeration over compressed words

MSO-string-to-string interpretation is a function f : Σ+ → Γ+ for which there exist a k ≥ 1 and MSO-formulas (all over words from Σ+ ) Φ(x1 , . . . , xk ), Φ< (x1 , . . . , xk , y1 , . . . , yk ), and Φb (x1 , . . . , xk ) for all b ∈ Γ such that the following hold for every word w ∈ Σ+ of length n (we write x̄ for (x1 , . . . , xk ) and similarly for ȳ): w |= ∀x̄, ȳ : Φ< (x̄, ȳ) → (Φ(x̄) ∧ Φ(ȳ)) and w |= ∀x̄ : Φb (x̄) → Φ(x̄) for every b ∈ Γ. The structure with universe JΦKw ⊆ [1, n]k , the binary relation JΦ< Kw ⊆ JΦKw × JΦKw and the unary relations JΦb Kw ⊆ JΦKw for b ∈ Γ is a word structure over the alphabet Γ in the sense of Section 2.2 and the corresponding word is f (w). The polyregular functions are exactly the MSO-string-to-string interpretations [9]. ▶ Example 2.3. A good example for an MSO-definable linear on tuples from [1, n]k (k ≥ 1, n ≥ 1) is the lexicographic order <lex k,n . For every k ≥ 1 there is an MSO-formula Φk such that for every word w of length n, JΦk Kw is <lex k,n . It can be inductively defined by Φ1 (x1 , y1 ) = (x1 < y1 ) and Φk (x1 , . . . , xk , y1 , . . . , yk ) = (x1 < y1 ∨ (x1 = y1 ∧ Φk−1 (x2 , . . . , xk , y2 , . . . , yk )) for k ≥ 2.

2.4

Straight-line programs

Let Σ be a finite alphabet of terminal symbols. A straight-line program (SLP for short) over the terminal alphabet Σ is a context-free grammar that produces exactly one word. This can be syntactically enforced by two properties: The context-free grammar is acyclic. For every variable A there is a unique production of the form A → w. Formally, we define an SLP over the terminal alphabet Σ as a pair G = (V, ρ), where V is a finite set of variables with V ∩ Σ = ∅ and ρ : V → (Σ ∪ V )∗ (the right-hand side mapping) has the property that the binary relation {(A, B) ∈ V × V : B ∈ alph(ρ(A))} is acyclic. This allows to define a homomorphism ρ∗ : (V ∪ Σ)∗ → Σ∗ uniquely by setting ρ∗ (a) = a for a ∈ Σ and ρ∗ (A) = ρ∗ (ρ(A)). For A ∈ V we also write JAKG for ρ∗ (A). Often, an SLP has a distinguished root (or start) variable S. The resulting triple G = (V, ρ, S) is then also called a rooted SLP (rSLP for short) and we define JGK = JSKG . An rSLP G can be seen as a context-free grammar that produces the single string JGK. Our convention is that capital roman letters (typically A, B, C, S, X, Y ) denote variables from V , lowercase roman letters a, b, c denote terminal symbols from Σ, and greek letters α, β, γ denote symbols from V ∪ Σ. P We define the size |G| of the SLP G = (V, ρ) as A∈V |ρ(A)|. For our purpose it is convenient to require that |ρ(A)| = 2 for all variables A. This property only excludes terminal words of length at most one (which is not a big loss since our considerations are only interesting for long words) and can be enforced in linear time: ▶ Lemma 2.4. A given rSLP G in the general sense (where right-hand sides may have arbitrary length) such that JGK has length at least two can be transformed in time O(|G|) into an rSLP H such that all right-hand sides of H have length two and JHK = JGK. Proof. The proof is straightforward (see [25, Proposition 3.8] for a similar statement): One first eliminates all variables B with ρ(B) = ε by deleting every occurrence of B in a right-hand side ρ(A). Only |G| many such deletions can be done in total. Next one eliminates variables A with ρ(A) ∈ V ∪ Σ. For this one computes in linear time the mapping chain : V → V ∪ Σ that is defined by chain(A) = A if |ρ(A)| ≥ 2, chain(A) = chain(B) if ρ(A) = B ∈ V and chain(A) = a if ρ(A) = a ∈ Σ. Note that for every variable A, chain(A) is either a terminal symbol or a variable B with |ρ(B)| ≥ 2. One then keeps only those variables A ∈ V with |ρ(A)| ≥ 2. If the right-hand side of such a variable contains a variable B with ρ(B) ∈ V ∪ Σ

M. Lohrey

7

then we replace this B by chain(B). Finally, one eliminates right-hand sides of length at least three in the same way as it is done in the construction of the Chomsky normal form. ◀ In the following we assume that all right-hand sides of SLPs have length two without mentioning this assumption explicitly. Let G = (V, ρ) be such an SLP over the terminal alphabet Σ. It will be convenient to view G as a dag (directed acyclic graph) D(G) = (V ∪ Σ, E(G)) where the set of edges is E(G) = {(A, ℓ, α), (A, r, β) ∈ V × (V ∪ Σ) : A ∈ V, ρ(A) = αβ}. Here, ℓ and r stand for ‘left’ and ‘right’, respectively. Note that |G| is the number of edges of the dag D(G). Paths in D(G) are edge sequences π = (A1 , d1 , A2 )(A2 , d2 , A3 ) · · · (Ak−1 , dk−1 , Ak )(Ak , dk , α) ∈ E(G)+ . This path is uniquely specified by A1 and the sequence of directions d1 d2 · · · dk . Later, we generalize paths by contracting subpaths that always move left, respectively, right. Then, it will be important to keep also the variables Ai in the path description. The length of the above path π is k (it is at least one since π ∈ E(G)+ ) and π starts in A1 ∈ V and ends in α ∈ V ∪ Σ. If α ∈ Σ then π is a terminal path and we denote with Pt (G) the set of all terminal paths in D(G) and with Pt (G, A) ⊆ Pt (G) the set of all terminal paths in D(G) that start in A ∈ V . If G is clear from the context, we write Pt (A) instead of Pt (G, A). The depth of G, depth(G) for short, is the maximal length of a path in D(G). Consider an SLP G = (V, ρ) and a variable A ∈ V producing the word w = JAKG of length N . The directions di in paths induce a lexicographic order on the set of paths Pt (A), where ℓ < r. Then, the function pA : Pt (A) → [1, N ] that maps the lexicographically i-th path in Pt (A) to position i is bijective. For a subset V ′ ⊆ V of variables we define the subSLP G↾V ′ as the SLP (V ′ , ρ↾V ′ ). The terminal alphabet of G↾V ′ is {α ∈ V ∪ Σ : α ∈ alph(ρ(A)) for some A ∈ V ′ } \ V ′ . ▶ Example 2.5. Consider the SLP G = ({S, A, B, C, D}, ρ) over the terminal alphabet {a, b}, where ρ is given by ρ(S) = AB, ρ(A) = BC, ρ(B) = CC, ρ(C) = aD, ρ(D) = ab. We have JSKG = (aab)5 , the size of the SLP is 10 and its depth is 5. The dag D(G) is shown in Figure 2. For the path π = (S, ℓ, A)(A, ℓ, B)(B, r, C)(C, ℓ, a) ∈ Pt (S) we have pS (π) = 4. Its lexicographic predecessor in Pt (S) is π ′ = (S, ℓ, A)(A, ℓ, B)(B, ℓ, C)(C, r, D)(D, r, b), whereas its lexicographic successor in Pt (S) is π ′′ = (S, ℓ, A)(A, ℓ, B)(B, r, C)(C, r, D)(D, ℓ, a). In particular, we have pS (π ′ ) = 3 and pS (π ′′ ) = 5. The terminal alphabet of the SLP G↾{S,A,B} contains only C and it produces C 5 .

8

Ranked MSO-enumeration over compressed words

S ℓ r

A ℓ

B

r r

ℓ

C r ℓ

D ℓ

r

a

b

Figure 2 The dag D(G) for the SLP from Example 2.5.

2.5

Enumeration algorithms

We use the standard RAM model for algorithms. We consider enumeration algorithms where the output values are enumerated in a specific order. This can be formalized as follows. A ranked enumeration problem is a function E that maps an input I to a finite word E(I) ∈ Ω∗ over an alphabet Ω of output values. In general, the alphabet Ω may depend on the input I. An important restriction for us is that every element a ∈ Ω fits into a constant number of RAM registers, where the bit length of RAM registers depends on the input length |I| in a certain way (more about this later). An enumeration algorithm A for E is an algorithm that computes on input I the word E(I) from left to right. More precisely, if E(I) = a1 a2 · · · am then the algorithm only starts with the computation of ai+1 , once it finishes outputting ai . After the computation of am the algorithm outputs the special end symbol am+1 = end. The preprocessing time of A on input I is the time when the algorithm starts with outputting a1 . The preprocessing time of A is the function that maps an n ∈ N to the maximum preprocessing time of A over all possible inputs I of length at most n. The delay of A on input I is the maximal time between the computation of two consecutive output values ai and ai+1 , where E(I) = a1 a2 · · · am , am+1 = end and i ∈ [1, m]. The algorithm A works in constant delay if there is a constant d such that for every input I the delay is bounded by d. The gold standard in the area of enumeration algorithms is linear preprocessing (i.e., the preprocessing time is O(|I|)) and constant delay. We consider enumeration algorithms, where the input I is an rSLP G. Assume that N is the length of JGK. We assume that positions from the interval [1, N ] fit into single RAM registers. This is a standard assumption in the area of algorithmics on grammar-compressed objects; see e.g. [6, 16, 29].

3

SLP-compressed factorization trees

Let M be a finite monoid, h : Σ∗ → M a homomorphism and G = (V, ρ) an SLP over the terminal alphabet Σ. Constants that are hidden in the O-notation below depend only on the monoid M and the morphism h in the following. We extend h to h : (Σ ∪ V )∗ → M by defining h(A) = h(ρ∗ (A)) for A ∈ V . For an idempotent e ∈ M we define the e-part Ge := G↾Ve , where Ve = {A ∈ V : h(A) = e, ρ(A) = αβ with h(α) = h(β) = e}.

M. Lohrey

9

A1

ℓ

A2

ℓ

Ve A3

r

Ve A4

ℓ

Σe A5

r

A6

r

Vi A7

r

Vi A8

ℓ

Σi A9

ℓ

a

Figure 3 The idempotent-contracted length of a path.

Let Σe be the set of terminal symbols of Ge ; it may contain variables and terminals of G. Note that h(α) = e for every α ∈ Ve ∪ Σe . Hence, the sets Ve ∪ Σe and Ve′ ∪ Σe′ are disjoint for idempotents e ̸= e′ . We define the idempotent-contracted depth of G as follows: Consider the dag D(G) and a path π = (A1 , d1 , A2 ) · · · (Ak−1 , dk−1 , Ak )(Ak , dk , a) ∈ Pt (A1 ) in D(G) with Ai ∈ V (i ∈ [1, k]) and a ∈ Σ. To simplify notation we write Ak+1 for a. The idempotent-contracted length of π is the length of the path obtained from π by contracting all maximal subpaths of π that are paths in some D(Ge ) into single edges. It can be also defined S as the number of i ∈ [1, k] such that either Ai ∈ / e∈E(M ) Ve or Ai ∈ Ve and Ai+1 ∈ Σe for some e ∈ E(M ). Figure 3 shows a path of length 9 with idempotent-contracted length 7. The idempotent-contracted depth of G is the maximal idempotent-contracted length of a path in D(G). A Simon SLP (SSLP for short) with respect to the homomorphism h is an SLP such that every path in D(G) has idempotent-contracted length at most 3|M |. If h is clear from the context we simply speak of an SSLP. A rooted SSLP is called an rSSLP. ▶ Theorem 3.1. Fix a finite monoid M and h : Σ∗ → M as above. From a given rSLP G one can construct in time O(|G|) an rSSLP G ′ of size O(|G|) such that JG ′ K = JGK. Proof. Recall the nondeterministic transducer Th from Theorem 2.2. Let G = (V, ρ, S). In a first step, we compute an acyclic context-free grammar H that generates the finite set Th (JGK). This is done by the standard product construction applied to the transducer Th and the rSLP G (viewed as a context-free grammar). The variables of H are triples (p, α, q), where α ∈ V ∪ Σ and p and q are states of Th . If ρ(A) = αβ then for all states p, q, r of Th we have the production (p, A, r) → (p, α, q)(q, β, r) in H. Moreover, we add all productions (p, a, q) → w, where (p, a/w, q) is a transition of Th . If m is the number of states of Th and t is the sum of the lengths of the output words in the transitions of Th (both are constants in our setting) then the size of H is bounded by m3 |G| + t. In a second step, we reduce H by removing variables that do not derive a terminal word. The well know algorithm from [20, Section 7.1.1] achieves this in linear time. After this step, we can fix for every variable A an arbitrary production A → s and define an SLP by setting ρ(A) = s. The resulting rSLP H′ produces a word γ(T ), where T is a factorization tree for JGK of height at most 3|M |. By Lemma 2.4 we can assume that all right-hand sides of H′ have length two. Finally, we restructure the SLP H′ into an rSSLP G ′ for JGK. Every factor u of the word ′ JH K = γ(T ) can be uniquely written as u1 ) u2 ) · · · uk ) v ( wℓ ( wℓ−1 · · · ( w1

(1)

with k, ℓ ≤ 3|M |. Every word ui , v, wi is either empty, γ(T ′ ) for a subtree T ′ of T or a sequence γ(T1 )γ(T2 ) · · · γ(Tj ) for subtrees T1 , T2 , . . . , Tj whose roots form a consecutive sequence of children of an idempotent node of T . We call (1) the Dyck factorization of u. Assume now that a variable A of H′ derives the word (1). We then introduce in the final rSSLP G ′ variables that derive the projections of the words u1 , u2 , . . . , uk , v, wℓ , wℓ−1 , . . . , w1 to the alphabet Σ (i.e., the words that are obtained by removing the brackets from

10

Ranked MSO-enumeration over compressed words

u1 , u2 , . . . , uk , v, wℓ , wℓ−1 , . . . , w1 ). Of courses, it suffices to introduce variables only for those words that are non-empty. We compute the right-hand side mapping ρ′ of G ′ by a bottom-up process. Let us consider an example, where ρH′ (A) = BC with B and C variables of H′ (the case where one of them or both are terminal symbols is easier). Assume that the Dyck factorizations of the factors JBKH′ and JCKH′ of γ(T ) are JBKH′ JCKH′

=

r1 ) r2 ) s ( t4 ( t3 ( t2 ( t1 ,

(2)

=

x1 ) x2 ) x3 ) y ( z2 ( z1 .

(3)

Assume that all factors ri , s, ti , xi , y, zi are nonempty. Then we have already introduced variables R1 , R2 , S, T4 , T3 , T2 , T1 for the variable B and X1 , X2 , X3 , Y, Z2 , Z1 for C. Here the variable Ri derives the Σ-projection of ri , S derives the Σ-projection of s, etc. The Dyck factorization of JAKH′ = JBKH′ JCKH′ can be derived from the concatenation of the Dyck factorizations in (2) and (3) by pairing matching brackets: r1 ) r2 ) s ( t4 ( t3 ( t2 ( t1 x1 ) x2 ) x3 ) y ( z2 ( z1 =

r1 ) r2 ) s ( t4 ( t3 ( t2 p1 x2 ) x3 ) y ( z2 ( z1

with p1 = ( t1 x1 )

=

r1 ) r2 ) s ( t4 ( t3 p2 x3 ) y ( z2 ( z1

with p2 = ( t2 p1 x2 )

=

r1 ) r2 ) s ( t4 p3 y ( z2 ( z1

with p3 = ( t3 p2 x3 )

=

r1 ) r2 ) s ( z3 ( z2 ( z1

with z3 = t4 p3 y

We then introduce for A the new variables P1 , P2 , P3 , Z3 with the right-hand sides ρ′ (P1 ) = T1 X1 , ρ′ (P2 ) = T2 P1 X2 , ρ′ (P3 ) = T3 P2 X3 , ρ′ (P4 ) = T4 P3 Y. The variables R1 , R2 , S, Z2 , Z1 can be reused for A. Note that the number of new variables introduced for each variable of H′ is linearly bounded in the height of the factorization tree T ; hence it is O(|M |). At the end we have to apply Lemma 2.4 to reduce the length of right-hand sides to two. It is easy to see that this construction yields an rSSLP. For every variable A of G ′ with ρ′ (A) = α1 α2 exactly one of the following two cases holds: There is a binary node v of T with left child v1 and right child v2 such that α1 produces the word w(v1 ) and α2 produces the word w(v2 ) (and hence A produces w(v)). There is an idempotent node v of T and consecutive children v1 <v v2 <v · · · <v vk of v (these are not necessarily all children of v) such that A produces w(v1 ) · · · w(vk ), α1 produces w(v1 ) · · · w(vi ) and α2 produces w(vi+1 ) · · · w(vk ) for some k ∈ [1, k − 1]. This ensures that G ′ is indeed an rSSLP. ◀

4

Constant time traversal in SLP-compressed words

In order to exploit Simon SLPs algorithmically we need a technique from [26] for two-way constant time traversal in SLP-compressed words. Later, we introduce a generalization of this technique. Throughout this section we fix an SLP G = (V, ρ) over the terminal alphabet Σ. For a variable A ∈ V we write |A|G for the length of the word JAKG . Recall from Section 2.4 the bijection pA : Pt (A) → [1, |A|G ] between paths in D(G) that start in A and end in a terminal symbol and the positions in [1, |A|G ]. We succinctly represent a path π ∈ Pt (A) by merging successive edges where π moves in the same direction (left or right) towards the leaf. To

M. Lohrey

11

a C

b

a

b

D

D

B A S

C A

B S

Figure 4 The left shows the tries TL (a), TL (b) and the right shows TR (a), TR (b), for the SLP from Example 2.5.

formalize this idea, we define for every α ∈ V ∪ Σ the strings L(α), R(α) ∈ V ∗ Σ inductively as follows. For a ∈ Σ let L(a) = R(a) = a. For A ∈ V with ρ(A) = αβ (α, β ∈ V ∪ Σ) let L(A) = A L(α) and R(A) = A R(β).

(4)

If L(α) (with α ∈ V ∪ Σ) ends with the terminal symbol a ∈ Σ then we define ωL (α) = a (in particular, ωL (a) = a). The terminal ωR (α) ∈ Σ is defined analogously by referring to the string R(α). ▶ Example 4.1. Consider the SLP from Example 2.5. We have L(a) = R(a) = a, L(b) = R(b) = b, and L(S) = SABCa

R(S) = SBCDb

L(A) = ABCa

R(A) = ACDb

L(B) = BCa

R(B) = BCDb

L(C) = Ca

R(C) = CDb

L(D) = Da

R(D) = Db.

Moreover, ωL (X) = a and ωR (X) = b for all X ∈ {S, A, B, C, D}. We store all strings L(α) (for α ∈ V ∪ Σ) in |Σ| many tries: Fix a ∈ Σ and let w1 , . . . , wn be all strings L(α) such that ωL (α) = a (in particular, a is one of the wi ). Let vi be the string wi reversed. Then, P = {v1 , . . . , vn } is a prefix-closed set of strings (except that the empty string is missing) that can be stored in a trie TL (a). Formally, P is the set of nodes of TL (a), each node s ∈ P is labeled by its last symbol (so the root is labeled with a), and there is an edge from aw to awA for all w ∈ V ∗ , A ∈ V with awA ∈ P . The tries TR (a) are defined in the same way by referring to the strings R(A). Note that the total number of nodes in all tries TL (a) (a ∈ Σ) is exactly |V | + |Σ|. In fact, every α ∈ V ∪ Σ occurs exactly once as a node label in the forest {TL (a) : a ∈ Σ}. ▶ Example 4.2. The tries TL (a), TL (b), TR (a), and TR (b) for the SLP from Example 2.5 are shown in Figure 4.

12

Ranked MSO-enumeration over compressed words

Next, we define two alphabets L and R by L = {(A, ℓ, α) : α ∈ alph(L(A)) \ {A}},

(5)

R = {(A, r, β) : β ∈ alph(R(A)) \ {A}}.

(6)

Note that the sizes |L| and |R| are quadratic in the size of G. In order to avoid some case distinctions in the rest of the section, we also allow triples (α, d, α) with α ∈ V ∪ Σ and d ∈ {ℓ, r} but they are placeholders for the empty word ε (in particular (α, ℓ, α) does not belong to L and similarly for R). On the alphabets L and R we define the functions ℓ-reduce : L → L ∪ {ε} and r-reduce : R → R ∪ {ε} as follows: let (A, ℓ, α) ∈ L and let B be the unique variable that appears directly to the left of α in the string L(A). Then we define ℓ-reduce(A, ℓ, α) = (A, ℓ, B). Note that by our conventions, this is ε in case A = B (i.e., α is the left symbol in ρ(A)). The definition of r-reduce is analogous: If (A, r, α) ∈ R, then r-reduce(A, r, α) = (A, r, B) where B is the unique variable that appears directly to the left of α in the string R(A). ▶ Example 4.3. For the SLP from Example 2.5 the sets L and R are L = {(S, ℓ, A), (S, ℓ, B), (S, ℓ, C), (S, ℓ, a), (A, ℓ, B), (A, ℓ, C), (A, ℓ, a), (B, ℓ, C), (B, ℓ, a), (C, ℓ, a), (D, ℓ, a)}, R = {(S, r, B), (S, r, C), (S, r, D), (S, r, b), (A, r, C), (A, r, D), (A, r, b), (B, r, C), (B, r, D), (B, r, b), (C, r, D), (C, r, b), (D, r, b)}. We have ℓ-reduce(S, ℓ, a) = (S, ℓ, C), r-reduce(B, r, D) = (B, r, C), and ℓ-reduce(S, ℓ, A) = ε. An element (A, ℓ, α) can be represented by a pair (v1 , v2 ) of different nodes in the forest {TL (a) : a ∈ Σ}, where v1 (resp. v2 ) is the unique node labeled with α (resp., A). Note that v1 and v2 belong to the same trie and v2 is strictly below v1 . This observation allows us to reduce the computation of the mapping ℓ-reduce to a so-called next link query: From the pair (v1 , v2 ) we have to compute the unique child v of v1 such that v is on the path from v1 down to v2 . If v is labeled with B, then ℓ-reduce(A, ℓ, α) = (A, ℓ, B) (which is ε if B = A). We represent (A, ℓ, B) by the pair (v, v2 ). Clearly, the same remark applies to the map r-reduce. The following result is mentioned in [18]. ▶ Proposition 4.4. A trie T can be represented in space O(|T |) such that any next link query can be answered in time O(1). Moreover, this representation can be computed in time O(|T |) from T . We use a compressed representation of paths in the dag D(G) that allows to contract consecutive left (resp., right) edges into triples from L (resp., R). Formally, we use sequences of triples π = (A1 , d1 , A2 )(A2 , d2 , A3 ) · · · (An−1 , dn−1 , An )(An , dn , α) ∈ (L ∪ R)+

(7)

such that n ≥ 1, Ai ∈ V for 1 ≤ i ≤ n and α ∈ V ∪ Σ. We say that this π starts in A1 and ends in α. The set of all triple sequences of the form (7) is denoted with S(G) ⊆ (L ∪ R)+ . A sequence π ∈ S(G) represents a path in D(G) that we denote by path(π). It is obtained by replacing every triple (Ai , ℓ, Ai+1 ) ∈ L by a path of consecutive left edges from Ai to Ai+1 and similarly for triples from R. By definition, every path in D(G) is also a sequence in S(G) consisting of triples from the edge set of D(G). We will use the term ’path’ only in this meaning. If π ∈ S(G) is not a path then we will always use the term ’sequence’.

M. Lohrey

If π ∈ S(G) ends in a terminal symbol then π is a terminal sequence. The set of all terminal sequences is denoted with St (G). We say that π ∈ S(G) is alternating if for every factor (A, d, B)(B, d′ , α) in π we have d = ℓ if and only if d′ = r. The set of all alternating sequences is denotes with Sa (G). An alternating sequence π is the maximal compressed sequence of triples for path(π). We write Sat (G) for Sa (G) ∩ St (G). Finally, for A ∈ V we write Sat (G, A), St (G, A), Sa (G, A), S(G, A) if we take only sequences starting with the variable A. Note that Pt (G, A) ⊆ St (G, A). For a sequence π ∈ St (G, A) we define the corresponding position in [1, |A|G ] by pA (π) = pA (path(π)). In the following, the underlying SLP G will be clear from the context. We will therefore simply write Sat (A), St (A), Sa (A), S(A), Sat , St , Sa , S. ▶ Example 4.5. For the SLP from Example 2.5, we have π = (S, ℓ, B)(B, r, b) ∈ Sat (S) and path(π) = (S, ℓ, A)(A, ℓ, B)(B, r, C)(C, r, D)(D, r, b). There is a simple process of making π ∈ S alternating. Thereby we replace in π factors of the form (A, d, B)(B, d, α) with d ∈ {ℓ, r} by (A, d, α). This can be done in any order and the resulting alternating sequence is denoted with reduce(π). In [26] an algorithm is presented that, after a preprocessing phase working in time O(|G|), takes as input a sequence π ∈ Sat (A) and computes in constant time the unique π ′ ∈ Sat (A) with pA (π ′ ) = pA (π)+1 in case pA (π) < |A|G and otherwise returns ⊥ (standing for undefined). A symmetric algorithm that returns the unique π ′ ∈ Sat (A) with pA (π ′ ) = pA (π) − 1 in case pA (π) > 1 and otherwise returns ⊥ is described as well. Fix a variable A ∈ V with |A|G ≥ 2 for the further consideration. We need a generalization of the algorithms from [26], where we store a subset Π ⊆ Pt (A) of paths with |Π| a constant. It will be convenient to assume that the unique paths π, π ′ ∈ Pt (A) with pA (π) = 1 and pA (π ′ ) = |A|G belong to Π; so in particular |Π| ≥ 2. We store Π by a rooted binary tree B (every vertex is either a leaf or has a left and a right child) with the following properties: B has |Π| leaves and every edge e of B is labelled by some πe ∈ Sa . If e = ̸ e′ are the two outgoing edges of a node of B then πe ∈ L(L ∪ R)∗ if and only if πe′ ∈ R(L ∪ R)∗ . For every π ∈ Π there is a leaf v such that the following holds: If e1 , e2 , . . . , em are the edges along the path from the root of B to the leaf v, then πe1 πe2 · · · πem ∈ St (A) and path(πe1 πe2 · · · πem ) = π. In the situation of the third point, we will also say that the pair (A, v) represents (in the tree B) the path π and write pA (v) for pA (π). Since |Π| ≥ 2, the tree B has at least two leaves. Since |Π| is a constant, B has a constant number of nodes. Only the edge labels πe occupy non-constant space. Note that for given leaves u, v of B it is straightforward to decide in time O(1) which of the cases pA (u) < pA (v), pA (u) > pA (v), or pA (u) = pA (v) holds. The latter holds if and only if u = v. If u = ̸ v then one has to follow the paths from the root of B to the leaves u and v up to the point where the two paths diverge to check whether pA (u) < pA (v) or pA (u) > pA (v) holds. Figure 5 shows an example for a tree B as above. It is not derived from the SLP from Example 2.5, for which the number of left-right and right-left turns in the dag D(G) is too small to get an interesting B. The leaves are called 1, 2, 3, 4, 5 in Figure 5. The reader can easily come up with an SLP that could realize the tree B from Figure 5. Consider a tree B that stores the set of paths Π ⊆ Pt (A). In the following, B is considered as a global data structure that is modified as a side effect by the procedures that we outline. The procedure right from Algorithm 2 in the appendix takes a leaf u of B as input. If pA (u) = |A|G then the algorithm returns ⊥ and the tree B is not modified. If pA (u) < |A|G

13

14

Ranked MSO-enumeration over compressed words

2 b) , r,

(A

(A , ℓ,

B)

(B

D , r,

(B

, ℓ,

(C ℓ, D,

E)

r, E,

, ℓ,

a)

4

b)

5

C)

(C

(

)(

, (C

, r,

(F F)

) r, c

, ℓ,

G)

(G

, r,

3

C)

(C

, ℓ,

a)

1

Figure 5 An example for a tree B.

and there is a leaf u′ in B with pA (u′ ) = pA (u) + 1 then this leaf u′ is returned and B is not modified. Otherwise a new leaf u′ is added to B such that for the new tree we have pA (u′ ) = pA (u) + 1, whereas for all leaves v from the original tree B, pA (v) does not change. Moreover, u′ is returned. The procedure right uses a procedure split that can be also found in the appendix. There is a symmetric procedure left that has the same specification as right except that the node u′ satisfies pA (u′ ) = pA (u) − 1 if pA (u) > 1; otherwise ⊥ is returned. It can be obtained analogously to the procedure right. The idea for the procedure right is derived from [26]. Figure 6 shows a tree that could arise from the call right(3) for the tree from Figure 5. For this, ℓ-reduce(B, ℓ, C) ̸= ε (or equivalently, C is not the left symbol in ρ(A)) must hold. This causes the (B, ℓ, C)-labelled edge from Figure 5 to be split into two edges with labels (B, ℓ, B ′ ) and (B ′ , ℓ, C), where (B, ℓ, B ′ ) = ℓ-reduce(B, ℓ, C) and ρ(B ′ ) = CF . The new node that arises from this edge splitting gets a right child (the new leaf 6 in Figure 6) with label (B ′ , r, F )(F, ℓ, a). Here we have a = ωL (F ). Note that if ℓ-reduce(B, ℓ, C) = ε (meaning that the triple (B, ℓ, C) represents a single edge in D(G)), then the call right(3) would split the edge labelled with (B, r, D)(D, ℓ, E)(E, r, C) in Figure 5. Dealing with all the possible cases in the procedure right is not difficult but a bit tedious. Each case needs a constant number of modifications in the tree B, which has constant size by our assumption. In addition a constant number of edge labels (i.e., sequences from Sa ) are modified, where every modification replaces a constant number of triples at the beginning or the end of the sequence; see also Figures 12–17 in the appendix. We will also need a procedure for removing a leaf v from the tree B (where 1 < pA (v) < |A|G ) in constant time. This is straightforward. We first remove the leaf v together with its incoming edge. This leaves two edges e = (x, y), e′ = (y, z) where (y, z) is the unique outgoing edge of y. We merge these edges into a single edge with label reduce(πe πe′ ) ∈ Sa . If for instance πe ends with a triple (U, ℓ, V ) and πe′ starts with a triple (V, ℓ, W ) then these triples are combined into the triple (U, ℓ, W ). Figure 7 shows the tree after removing the leaf 5 from the tree in Figure 5. Note that the above tree B only stores paths from Pt (A). For our application in Section 5 we need trees BA for several variables A ∈ V . We then write right(A, u) and left(A, u) to

M. Lohrey

15

2

, (A

(A ,

ℓ, B

(B

) r, b

D , r,

)(

(C ℓ, D,

(

E)

) (B ,

r, E,

′ , r,

ℓ, B ′ )

, r,

(F F)

, ℓ,

a)

4

b)

5

C)

F)

(C

(F,

, ℓ,

G)

(G

) ℓ, a 6

, r,

(B

(B ′ , ℓ,

, (C

) r, c

3

C)

(C

, ℓ,

a)

1

Figure 6 The tree B from Figure 5 after the update right(3). We have ρ(B ′ ) = CF .

indicate the tree BA on which these operations are executed.

5

Ranked MSO-enumeration

In this section we prove the main technical result, that covers ranked MSO-enumeration (as explained in the introduction) as well as the enumeration of the image f (w) for a polyregular function, both for compressed input words. Fix two finite alphabets Σ and Γ and an MSO-interpretation f : Σ+ → Γ+ as defined in Section 2.3. Let Φ(x1 , . . . , xk ), Φ< (x1 , . . . , xk , y1 , . . . , yk ), and Φb (x1 , . . . , xk ) for all b ∈ Γ be the corresponding MSO-formulas over words from Σ+ defining f . We fix these formulas for this section and define the following additional MSO-formulas (we write x̄ for (x1 , . . . , xk ) and similarly for ȳ and z̄): Φmin (x̄)

=

Φ(x̄) ∧ ¬∃z̄ : Φ< (z̄, x̄),

Φmax (x̄)

=

Φ(x̄) ∧ ¬∃z̄ : Φ< (x̄, z̄),

Φsucc (x̄, ȳ)

=

Φ< (x̄, ȳ) ∧ ¬∃z̄ : Φ< (x̄, z̄) ∧ Φ< (z̄, ȳ),

Φsucc,i (x̄, yi )

=

∃y1 , . . . , yi−1 , yi+1 , . . . , yk : Φsucc (x̄, ȳ).

So, for every word w ∈ Σ+ of length n, there are unique tuples minw , maxw ∈ [1, n]k such that w |= Φmin (minw ) and w |= Φmax (maxw ) hold. Clearly, minw (resp., maxw ) is the first (resp., last) position in the word structure for f (w). Moreover, Φsucc (x̄, ȳ) defines the successor relation on positions of f (w). Hence, the binary relation JΦsucc Kw defines a function succw : JΦKw \ {maxw } → JΦKw \ {minw }. Similarly, Φsucc,i (x̄, yi ) defines for every word w of length n a function succw,i : JΦKw \ {maxw } → [1, n] that maps a tuple p̄ from its domain to the i-th component of succw (p̄). Finally, the formulas Φb (b ∈ Γ) define a function γ : JΦKw → Γ, where γ(p̄) is the unique symbol b ∈ Γ such that w |= Φb (p̄) holds for p̄ ∈ JΦKw . We then define a function F that maps an input word w ∈ Σ+ to the sequence (b1 , p̄1 )(b2 , p̄2 ) · · · (bm , p̄m ) with bi ∈ Γ and p̄i ∈ [1, n]k that is defined as follows: p̄1 = minw , p̄m = maxw ,

16

Ranked MSO-enumeration over compressed words

2 , r, (A

(A , ℓ,

(B

, r,

b)

(D D)

, ℓ,

(E E)

B) (B

, ℓ,

, (C

, r,

F

, )(F

) r, c

)

ℓ, a

4

3

C)

(C

, ℓ,

a)

1

Figure 7 The tree B from Figure 5 after removing the leaf 5.

for every i ∈ [2, m], p̄i = succw (p̄i−1 ), for every i ∈ [1, m], bi = γ(p̄i ). So F is the same as the MSO-interpretation f , where in addition we add the domain tuples from f (w) to the output. The main result of this section is the following: ▶ Theorem 5.1. The enumeration problem that maps an rSLP G to the sequence F (JGK) can be solved after linear preprocessing in constant delay. Proof. Let w = JGK. In order to prove the theorem, we will compute in linear time from the rSLP G a data structure that allows to solve in constant time the following tasks: (i) compute the tuple minw , (ii) compute from a given tuple p̄ ∈ JΦKw the symbol γ(p̄), (iii) compute from a given tuple p̄ ∈ JΦKw \ {maxw } and i ∈ [1, k] the position succw,i (p̄), (iv) check whether a given tuple p̄ ∈ JΦKw is maxw . Point (iii) then allows to compute in constant time also the tuple succw (p̄) (since k is a constant in our setting). To compute F (w) one then iterates the computation of succw starting with the k-tuple minw . Moreover, it suffices to show (iii) for i = 1 (the same method works for all i ∈ [1, k]). In the following, we focus on step (iii) (the most difficult one) and thereby we will also address step (iv). Later we explain how steps (i) and (ii) can be solved using similar techniques. We will use a factorization tree T for w with respect to a morphism h : Σ∗ → M , where h and M only depend on the fixed MSO-interpretation. We start with the definition of M and h. Let Z = {x1 , . . . , xk , y1 } be the set of free variables of the formulas Φsucc,1 . We transform Φsucc,1 into a trim NFA A using the standard procedure for transforming MSO-formulas over words into NFAs. The alphabet of A is the set Σ × 2Z and A has the following properties: For every word (a1 , Z1 )(a2 , Z2 ) · · · (an , Zn ) ∈ L(A) (with ai ∈ Σ and Zi ⊆ Z) and every variable z ∈ Z there is exactly one position i ∈ [1, |w|] with z ∈ Zi . (a1 , Z1 )(a2 , Z2 ) · · · (an , Zn ) ∈ L(A) if and only if succu,1 (p1 , . . . , pk ) = p′ , where u = a1 a2 · · · an , pi is the unique position in [1, n] with xi ∈ Zpi and p′ is the unique position in [1, n] with y1 ∈ Zp′ .

M. Lohrey

17

This, together with the fact that A is trim, ensures that we can partition the state set Q of A into two sets Q0 and Q1 such that the following holds, where a path in A is called y1 -free if it does not use a transition with a label (a, Z) such that y1 ∈ Z: states in Q0 can be reached from the initial state q0 of A along a y1 -free path, and from states in Q1 one can reach a final state along a y1 -free path. Note that this means that on every path from q0 to a state in Q1 the variable y1 must be seen exactly once and, similarly, on every path from Q0 to a final state the variable y1 must be seen exactly once. For a transition (q, (a, Z), q ′ ) in A with y1 ∈ Z we must have q ∈ Q0 and q ′ ∈ Q1 . From A we then derive the NFA A′ by replacing every transition label (a, Z) with y1 ∈ Z by (a, Z \ {y1 }). It is an NFA for the MSO-formula ∃y1 : Φsucc,1 = ∃ȳ : Φsucc (x̄, ȳ). Its alphabet is Σ × 2{x1 ,...,xk } . Note that J∃ȳ : Φsucc (x̄, ȳ)Kw = JΦKw \ {maxw }. We define the monoid M = Bool(A′ , Σ × {∅}). Let h : Σ∗ → M be the homomorphism with h(a) = Ba , where Ba is the boolean matrix corresponding to the state transformation induced by the letter (a, ∅) in the NFA A′ . Note that transitions in A′ having a label (a, Z) with Z = ̸ ∅ are irrelevant for the monoid M (one could remove all these transitions and would obtain the same monoid). The uncompressed setting. Before we proceed with the SLP-compressed setting, let us first consider the case where w is an uncompressed string of length n. This case is sketched in [8]. We follow this approach with some adaptions and later show how to extend it to the compressed setting using the machinery from Sections 3 and 4. Let w = a1 a2 · · · an with ai ∈ Σ. In the precomputing phase we compute in time O(n) a factorization tree T of height at most 3|M | for the word w with respect to the above homomorphism h : Σ∗ → M . We assume that T is stored by having pointers from every node to its parent node, it left sibling (if it exists) and its right sibling (if it exists). Moreover, there are pointers from every non-leaf node to its left-most child and to its right-most child. Let v0 be the root of T . For every node v of T let |v|T be the number of leaves of T below v (the so-called leaf size of v). We precompute in time O(|w|) all numbers |v|T and all monoid elements h(v) for v a node of T . For a subset U of nodes of T we write h(U ) for the product Q u∈U h(u), where we run over the elements from U in the order <T . Let p̄ = (p1 , p2 , . . . , pk ) ∈ [1, n]k be the argument for succw,1 and assume that p1 < p2 < · · · < pk . The case where the order between the pi is different or some of the pi are equal does not lead to additional complications. In addition, it will be convenient to assume that p1 = 1 and pk = n. This can be assumed by adding dummy variables in the MSO-formulas that are fixed to the first and last position of the word w. We assume that p̄ ∈ JΦKw ; this property will be always preserved during the computation of F (w). We denote with w ⊗ p̄ the word (a1 , Z1 )(a2 , Z2 ) · · · (an , Zn ), where Zi = {xj : j ∈ [1, k], pj = i}. Our goal is to check whether p̄ ̸= maxw (see step (iv)) and, if the latter holds, compute p′ = succw,1 (p̄) ∈ [1, n]. Let vi be the pi -th leaf of T with respect to the order <T . We make the additional assumption that for every i ∈ [1, k] we have computed the path πi = [v0 , vi ] from the root of T to the leaf vi ; this property will be also preserved during the computation of F (w). Moreover, for every node v on one of these paths πi we assume that we have computed the number |v|< T := |{u : u is a leaf of T and u <T v}|.

(8)

′ For the root node v0 we have |v0 |< T = 0. We will compute in addition to p = succw,1 (p̄) (if it exists) also the path π ′ = [v0 , v ′ ], where v ′ is the p′ -th leaf of T with respect to the order

18

Ranked MSO-enumeration over compressed words

<T . The computation starts in v0 and ends in the leaf v ′ . Moreover, for every node v along ′ this path π ′ we compute the number |v|< T . When this process finally arrives at the leaf v , ′ ′ ′ < we can determine the position p by p = |v |T + 1. The constant height bound 3|M | of the tree T ensures that one can compute all monoid elements h(w[pi−1 + 1, pi − 1]) ∈ M (2 ≤ i ≤ k) in constant time. To see this, let vi−1,i be the lowest common ancestor of the nodes vi−1 and vi and define the paths τi−1 = [vi−1,i , vi−1 ] and τi = [vi−1,i , vi ]; see also Figure 8. We define the following set of nodes of T : encli−1,i

=

{v : vi−1 <T v <T vi } \ τi

(encl stands for ‘enclosed’). In Figure 8, encli−1,i is the gray shaded part without the red paths τi−1 and τi . For every node u in T we define chi−1,i (u) as the set of those children of u that belong to encli−1,i . We have chi−1,i (u) = ∅ if u does not belong to τi−1 ∪ encli−1,i ∪ τi . Moreover, define [ chi−1,i = chi−1,i (u). u∈τi−1 ∪τi

In Figure 8, chi−1,i is the set of (dark and light) blue nodes in the gray region. Then we can compute h(w[pi−1 + 1, pi − 1]) as h(w[pi−1 + 1, pi − 1]) = h(chi−1,i ).

(9)

This product can be computed in constant time using the already computed paths πi−1 and πi , the pointers in T , and the monoid elements h(v). Powers of the same idempotent element e in h(chi−1,i ) can be reduced to a single e. Then the resulting product has at most one monoid element for each node in τi−1 ∪ τi , which yields a product of length at most 6|M |. For the example, in Figure 8 we obtain h(chi−1,i ) = m n e o m ϵ m ϵ o n e o. Next, observe that the monoid elements h(w[pi−1 + 1, pi − 1]) ∈ M (2 ≤ i ≤ k) together with the symbols w[pi ] (1 ≤ i ≤ k) are enough to check whether succw,1 (p̄) is defined. Using these elements one can check, whether there is an accepting run of the NFA A′ on the word w ⊗ p̄. If there is such an accepting run, then p′ = succw,1 (p̄) ∈ [1, n] is defined, otherwise we must have p̄ = maxw and the computation of F (w) terminates. Assume that p′ = succw,1 (p̄) is defined. We have to compute this position p′ and the corresponding path π ′ . First, we find out to which of the intervals {p1 }, [p1 + 1, p2 − 1], {p2 }, . . . , [pk−1 + 1, pk − 1], {pk } the unknown position p′ belongs to (recall that we assume p1 = 1 and pk = n). For this, the partition Q = Q0 ⊎ Q1 of the state set Q of the NFA A′ is important. If we find for instance an accepting run of the NFA A′ on w ⊗ p̄ that enters the interval [pi−1 + 1, pi − 1] in a state from Q0 and leaves [pi−1 + 1, pi − 1] in a state from Q1 (the existence of such a run can be deduced from h(w[pi−1 + 1, pi − 1])) then p′ ∈ [pi−1 + 1, pi − 1]. If it turns out that p′ = pi for some i ∈ [1, k] then we are done with step (iii). Therefore, assume that pi−1 < p′ < pi . The path π ′ = [v0 , v ′ ] shares with πi−1 and πi the prefix [v0 , vi−1,i ]. Then π ′ follows either τi−1 or τi , but at some point it will enter encli−1,i (the path can already branch off at vi−1,i if vi−1,i has more than two children as in Figure 8). The node u ∈ τi−1 ∪ τi from where π ′ enters encli−1,i can be determined from the monoid elements h(chi−1,i (v)) for v ∈ τi−1 ∪ τi using again the partition Q = Q0 ⊎ Q1 . When this node u is determined we have to find in constant time the right child from chi−1,i (u) that is taken by the path π ′ . If u is an idempotent node, then the set chi−1,i (u) can have unbounded size. The important observation here is the following: Assume that u ∈ τi−1 ∪ τi is an idempotent node. Then only the edge to the first or last (with respect to the child order <u ) node of chi−1,i (u) can be taken by π ′ (unless |chi−1,i (u)| = 3, in which case all three nodes

M. Lohrey

19

v0

ϵ ϵ ϵ

vi−1,i

ϵ ϵ ϵ ϵ ϵ

ϵ ϵ ϵ

m m

ϵ ϵ ϵ ϵ ϵ ϵ ϵ ϵ

u

o

e

o

e e e u′ e e e e e e e

n

n e eeee

vi−1

m

o

ee

vi

Figure 8 A part of a factorization tree T . The paths τi−1 = [vi−1,i , vi−1 ] and τi = [vi−1,i , vi ] are in red. Node names are in green. Some of the nodes u are labelled with their monoid elements h(u) ∈ M (m, n, o and the idempotents e, ϵ). The blue nodes in the gray zone are in general not leaves of T ; the subtrees rooted in those nodes are omitted. When the path π ′ branches off from πi−1 or π into the gray zone, it can only take one of the dark blue edges.

are possible), and the correct alternative can be found in time O(1) using the h-values of the nodes of T and the partition Q = Q0 ⊎ Q1 . Assume for instance the situation shown in Figure 9 on the left occurs, where the unique position of y1 is located at a leaf below the third node from chi−1,i (u). Hence, one can obtain an accepting run of the NFA A (the NFA for Φsucc,1 ) on the word w for the situation on the left. But then the same must also hold for the situation on the right in Figure 9, because the second and third node from chi−1,i (u) have the same context in the monoid M ((ee, eee) = (e, e) on the left and (e, eeee) = (e, e) on the right in Figure 9) is the same. Hence, we could also find for y1 a position below the second (or fourth) node from chi−1,i (u). This contradicts the uniqueness of the position of y1 . Note that this argument assumes that chi−1,i (u) consists of at least four nodes. In Figure 8 the path π ′ can only branch off into the gray zone to one of the dark blue nodes. Once we found the right child of u we can navigate down to the leaf v ′ (where y1 is located) using the same principle.

20

Ranked MSO-enumeration over compressed words

u e chi−1,i (u) e e e e e e y1

e eeeeee y1

Figure 9 The variable y1 cannot be located at a leaf of T as shown on the left, because then y1 could be also located at a leaf of T as shown on the right, contradicting the uniqueness of the position of y1 . Similarly, the situation on the right is excluded, otherwise also the situation on the left would be possible.

′ Updating the numbers |u|< T while we navigate down to v is straightforward (using the precomputed leaf sizes |v|T ) when we move from a binary node u to one of its children. When descending from an idempotent node u to one of its children in chi−1,i (u) = {u1 , u2 , . . . , ul−1 , ul } (with ui <u ui+1 ) we have seen that only u1 , u2 , ul are possible for the descent (this also includes the case where l = 3). Moreover, u1 (resp., ul ) is either the left-most (resp., rightmost) child of u in T or the right (resp., left) sibling of another child u′ of u that belongs to τi−1 (resp., τi ). In all cases, the | · |< T -value of the new node can be easily computed from previously computed numbers. For instance, if the algorithms descends to ul and ul is the ′ < ′ < left sibling of a node u′ ∈ τi then we can determine |ul |< T as |u |T − |ul |T (note that |u |T has been computed before since it belongs to πi ) and if the algorithms descends to u2 and u1 is ′ < ′ the right sibling of a node u′ ∈ τi−1 then we can determine |u2 |< T as |u |T + |u |T + |u1 |T . This concludes the outline of steps (iii) and (iv) (from the beginning of the proof of Theorem 5.1) for the uncompressed case. The other steps are in fact easier. For step (ii) we transform each of the formulas Φb (b ∈ Γ) from our fixed MSO-interpretation into an NFA Ab and take the monoid Mb = Bool(Ab , Σ × {∅}) and the homomorphism hb : Σ∗ → Mb defined by hb (a) = Bb,a , where Bb,a is the boolean matrix corresponding to the state transformation induced by the letter (a, ∅) in the NFA Ab . Then, in order to check whether w |= Φb (p̄) holds, it suffices to compute all the monoid elements hb (w[pi−1 +1, pi −1]) ∈ Mb (2 ≤ i ≤ k) using a factorization tree for w with respect to hb . This task has been solved for step (iii) with h instead of hb . Finally, step (i) can be solved in the same way as step (iii): We compute each component of the tuple minw using the formula Φmin,i (xi ) = ∃x1 , . . . , xi−1 , xi+1 , . . . , xk : Φmin . For this one can use the algorithm from step (iii). The only difference is that there are no positions pi and paths πi to start with. Formally, one can simply take k = 0 in the algorithm for step (iii). Instead of working with a separate factorization tree for each of the MSO-formulas Φmin,i , Φsucc,i (1 ≤ i ≤ k), Φb (b ∈ Γ) it is better to take the direct product of the above monoids M, Mb , etc., and the corresponding homomorphism from Σ∗ into this direct product. Then one can work with a single factorization tree T . This has the advantage that the path to the new position p′ computed in step (iii) does not have to be inserted into the factorization trees for the other MSO-formulas. This will be crucial when w is given by an rSLP.

The dag-compressed setting. Our final goal is to adapt the above approach to the setting where the string w is given by an rSLP G. As an intermediate step, let us consider the case, where the factorization tree T for w is represented succinctly by a rooted dag, where isomorphic subtrees of T are identified. To represent the child orders <u , one can label the outgoing edges of a dag node by 1, 2, . . . , k where k is the number of children (for the binary dag D(G) of an SLP these edge labels are ℓ and r). We write D for this dag and its root is

M. Lohrey

21

1

2

2

1

4

e

d 1 2

3

1

2 4

c

1

a

3

2

b

Figure 10 A dag compression of the factorization tree from Figure 1. Binary nodes are in magenta, idempotent nodes are in green.

denoted with r. Consider for instance the factorization tree T from Figure 1. Then a dag compression of T is shown in Figure 10 (it is in fact the best dag compression in the sense that all nodes of T , where isomorphic subtrees are rooted are merged in the dag). We store D by keeping for every dag node u a doubly linked adjacency list of the children of u with additional pointers from u to the first and last node of this list. We claim that the approach for the uncompressed setting extends to the dag-compressed setting with only a few minor modifications. Nodes of T are in one-to-one correspondence with paths in D that start in the root and end in a leaf (we speak of root-leaf paths in the following). Such a path can be identified with the sequence of edge labels which yields a lexicographic order on paths. The algorithm follows the approach from the uncompressed setting to compute the path π ′ to the unique position of the variable y1 in the word w from the paths π1 , . . . , πk (that lead to the positions of the variables x1 , . . . , xk ). In the dag-compressed setting, these paths are of course paths in the dag D. Recall that in the uncompressed setting the computation of the monoid elements from M and the decision on the branching direction when descending along the path π ′ are solely based on the precomputed monoid elements h(u) for the nodes u of T . Now, the nodes of T are paths π that start at the root of D; so we should write h(π) instead of h(u). In general the number of paths in D is exponential in the size of D; so we cannot afford to compute all values h(π). But this is not necessary, since h(π) only depends on the last node of π. More precisely, for every node v of D we can precompute in time O(|D|) a monoid element h(v) as follows: If v is a leaf labelled with the symbol a ∈ Σ then h(v) = h(a) and if v has m ≥ 1 outgoing edges (v, i, vi ) (1 ≤ i ≤ m) then h(v) = h(v1 )h(v2 ) · · · h(vm ) in M . Then for every path π in D that goes from the root to v we have h(π) = h(v) (where π is viewed here as a node of the tree T ). The same remark also applies to the leaf size |π|T for a node π of T . Recall that this is the number of leaves in the subtree rooted at π. Also these values only depend on the last node of π and we can precompute numbers |v|D (for v a node of D) by |v|D = 1 for a leaf v of D and |v|D = |v1 |D + |v2 |D + · · · + |vm |D if v has m ≥ 1 outgoing edges (v, i, vi ). Using these monoid elements h(v) and the numbers |v|D the computation of

22

Ranked MSO-enumeration over compressed words

the path π ′ from the uncompressed setting can be extended without modifications to the dag-compressed setting. Thereby we also compute for every prefix τ of π ′ the value |τ |< T ; see (8). Note that |τ |< is the number of root-leaf paths in the dag D that are lexicographically T strictly smaller than τ . The SLP-compressed setting. We finally adapt the above approach for the dag-compressed setting to the SLP-compressed setting, where w is given by an rSLP G. Let w = JGK and N = |w| in the following. We only consider step (iii) from the beginning of the proof in detail. In the preprocessing we replace, using Theorem 3.1, the rSLP G by an equivalent rSSLP with respect to the above homomorphism h : Σ∗ → M . We denote this rSSLP again with G. So, in the following, G = (V, ρ, S) is an rSSLP with JGK = w. For an idempotent e ∈ E(M ) let Ge = (Ve , ρ↾Ve ) be the e-part of G (see Section 3). In time O(|G|) we precompute for every variable A ∈ V the monoid element h(A) := h(JAKG ) ∈ M as well as the length |A|G of the string produced by A. The rSSLP G is quite close to a dag D for a factorization tree T (as considered in the paragraph on the dag-compressed setting). The only difference is that in the rSSLP G an idempotent node v of D (i.e., a node with more than two children) becomes a variable of the e-part Ge for the idempotent e = h(v). Hence, a node of D with more than two children is replaced by a binary subdag. Using the data structure from Section 4 we can emulate the algorithm for the dag-compressed setting on the rSSLP G. Let us elaborate this in more detail. As in the dag-compressed setting, the paths πi in the factorization tree T from the uncompressed setting are replaced by terminal paths πi ∈ Pt (S) in the dag D(G). In contrast to the dag-compressed setting (where the dag has depth at most 3|M | – the same as the factorization tree to which it unfolds) the paths πi in the rSLP G have unbounded length. In order to be able to do all manipulations in constant time, we use the data structure from Section 4 for maximal subpaths of πi that belong to an e-part Ge . Consider a tuple π̄ = (π1 , . . . , πk ) of paths πi ∈ Pt (S) in the dag D(G). Let p̄ = (p1 , . . . , pk ) be the corresponding tuple of positions pi = pS (πi ) in the word w. We assume that p̄ is also computed and that it belongs to the domain of succw . Our goal is to compute the position p′ = succw,1 (p̄) and the corresponding path π ′ ∈ Pt (S). For every idempotent e ∈ E(M ) let Pt (π̄, e) be the set of all terminal paths σ ∈ Pt (Ge ) in Ge such that for some i ∈ [1, k] there is a factorization πi = τ1 στ2 (where τ1 or τ2 can be also empty), but if if τ1 is non-empty and ends with the edge (A, d, B) then (A, d, B)τ ∈ / Pt (Ge ).1 In other words, σ is a longest subpath in some πi under the restriction that it is a path in Ge . For every variable A of Ge let Pt (π̄, A) be those paths in Pt (π̄, e) that start in the variable A (we do not have to mention e in Pt (π̄, A), since A determines the idempotent e = h(A)). For every variable A of Ge such that Pt (π̄, A) ̸= ∅ we will store the paths in Pt (π̄, A) by a tree BA as described in Section 4. Note that the union of all sets Pt (π̄, A) is bounded by 3|M |k: Each of the k paths πi contains at most 3|M | maximal subpaths from some e-part Ge , since the idempotent contracted length of πi is bounded by 3|M |. Hence, we will store at most 3|M |k many trees BA . With the help of the BA we store every path πi by replacing in πi every maximal subpath σ ∈ Pt (π̄, A) (such subpaths cannot overlap in πi ) by an edge labelled with the pair (A, v) that represents the path σ in the sense of Section 4 (in particular, v is a leaf of BA ). We

1

The same is also true if we add to σ the first edge of τ2 since σ is required to be a terminal path in D(Ge ).

M. Lohrey

23

S ℓ A v B ℓ

v′

A1 A2 A3 r ℓ

D

B

′

C

C r

′

E

r

ℓ

D′

E

u′ u F F1 F2 F3 F4 r

G4 G3 G2 G1 G ℓ

a

G′

r b

Figure 11 The contracted path π̃i−1 goes from S down to the a-labelled leaf, and the contracted path π̃i goes from S down to the b-labelled leaf on the bottom right.

denote the resulting contracted path by π̃i and call it the contracted representation of πi . Its length (i.e., number of edge triples (A, d, B) and pairs (A, v)) is at most 3|M |, since G is an rSSLP and hence has idempotent-contracted depth at most 3|M |. The paths stored in the trees BA correspond in the dag-compressed setting to edges in a path πi that lead from an idempotent node to one of its children. In Figure 3, the shortcuts from A3 to A5 and from A7 to A9 would be placed by pairs (A3 , v) and (A7 , v ′ ) for suitable leaves v and v ′ in BA3 and BA7 , respectively. ▶ Example 5.2. Figure 11 shows an example for the contracted paths π̃i−1 π̃i

= =

(S, ℓ, A)(A, v)(B, ℓ, D)(D, ℓ, E)(E, u)(F, r, a) and ′

′

(S, ℓ, A)(A, v )(C, r, E)(E, u )(G, r, b)

(10) (11)

′

with v = ̸ v . The straight edges in Figure 11 are edges in the dag D(G) and the curly edges S stand for paths from e∈E(M ) Pt (Ge ). The red u-labelled path from E to F is represented by the path from the root to the leaf u in the tree BE , and similarly for the other red curly edges. The curly paths from E to Fi (1 ≤ i ≤ 4) are the paths from Pt (Ge , E) (assuming that E ∈ Ve ) that are lexicographically larger than the path from E to F and the lexicographic order on these paths corresponds to the left-to-right order in Figure 11.2 Analogous statements hold for the curly paths that descend from A and the E on the right. Using the trees BA , we can now emulate the algorithm for the dag-compressed setting. Note that in the dag-compressed setting we assumed that the children of an idempotent dag node u are stored in a doubly linked adjacency list. This allows to go from a child u′ of u to its left or right sibling, which is needed when we branch off from one the paths πi ; see also Figure 8 (which refers to the uncompressed setting, but the situation for the dag-compressed setting is the same), where the path π ′ can branch off from πi−1 or πi along one of the dark blue edges. 2

Note that the variables F, F1 , . . . , F4 are not necessarily distinct.

24

Ranked MSO-enumeration over compressed words

For instance, in Figure 8 the path π ′ might branch off from πi−1 at the idempotent node u and descend to the right sibling of u′ . Also notice that the nodes u and u′ have been visited before, since they belongs to πi−1 or πi . For the SLP-compressed setting, this means that during the computation of the new path π ′ , the latter may branch off from some πi along a terminal path τ ′ ∈ Pt (Ge , A) such that τ ′ is the lexicographic predecessor or successor (with respect to the lexicographic order on Pt (Ge , A)) of a path that is already represented in BA . In Figure 11 the path π ′ may for instance branch off at A and continue the dark blue path to A1 . Its lexicographical predecessor is the red curly path from A ∈ Ve to B in D(Ge ), which is already represented by the pair (A, v) in the tree BA . Hence, the call right(A, v) returns a potentially new leaf v ′ in the new tree BA such that the pair (A, v1 ) represents in the new tree BA (after the call right(A, v)) the blue path from A to A1 in Figure 11. At this point we have computed the prefix (S, ℓ, A)(A, v1 ) of π̃ ′ (the contracted representation of the path π ′ ). In general, the path π ′ can only branch off from πi−1 ∪ πi along one the dark blue edges in Figure 11 (assuming that pi−1 < p′ < pi ). The case where π ′ branches off along the curly edge from E to F4 for instance is easy, since this edge stands for the rightmost path in Pt (Ge′ , E) (assuming E ∈ Ve′ ). This path is already represented in the tree BE (we assumed in Section 4 that the leftmost and rightmost path in the SLP are always represented in the tree B). We have now shown that after a O(|G|)-time preprocessing we can compute the mapping succw (for w = JGK) in constant time. More precisely, given a tuple p̄ = (p1 , . . . , pk ) of positions in w and the contracted representations of the paths πi (the lexicographically pi -th path in Pt (G, S)), our algorithm computes in constant time the new tuple p̄′ of positions in w. Moreover, the algorithm also computes the contracted representations of the paths πi′ that correspond to the new positions p′i and updates the trees BA accordingly. It is now important to remove those leaves in the trees BA that are not needed for the contracted representations of the paths πi′ , otherwise the trees BA would grow unboundedly. For this we have to do a constant number (at most 3|M |k many) delete operations as explained at the end of Section 4. Finally, recall the last paragraph from the uncompressed setting, where we argued that one should take the direct product of all the monoids for the various MSO-formulas Φmin,i , Φsucc,i (1 ≤ i ≤ k), Φb (b ∈ Γ) and compute a single factorization tree for this direct product. For the SLP-compressed setting this means that we work with a single rSSLP. This is crucial. If one would work with several rSSLPs (one for each of the above MSO-formulas), then after computing the new path π ′ to the new position p′ in the rSSLP for Φsucc,1 , one would have to compute in the rSSLP for Φsucc,2 the lexicographically p′ -th terminal path. It is not clear how to do this in constant time, even if one works with contracted paths. This finally concludes the proof of Theorem 5.1. ◀ By removing the position tuples p̄ from the function F in Theorem 5.1, we obtain the following corollary: ▶ Corollary 5.3. Fix a polyregular function f : Σ∗ → Γ∗ . The enumeration problem that maps an rSLP G over the terminal alphabet Σ to the word f (JGK) can be solved after linear preprocessing in constant delay. By removing the letters b ∈ Γ (or taking a unary alphabet Γ) we obtain the following corollary of Theorem 5.1: ▶ Corollary 5.4. Fix MSO-formulas Φ(x1 , . . . , xk ) and Φ< (x1 , . . . , xk , y1 , . . . , yk ) such that for every word w ∈ Σ∗ the relation JΦ< Kw is a linear order on [1, |w|]k . Then, the enumeration

M. Lohrey

problem that maps an rSLP G to the sequence of all tuples from JΦKJGK ordered with respect to JΦ< KJGK can be solved after linear preprocessing in constant delay. Proof. We apply Theorem 5.1 with a unary alphabet Γ and the MSO-interpretation that is given by the formulas Φ(x̄) for the domain and Φ′< (x̄, ȳ) = Φ< (x̄, ȳ) ∧ Φ(x̄) ∧ Φ(ȳ) for the linear order. ◀ The reader might have observed that our proof of Theorem 5.1 also works, if we directly start with a formula Φsucc (x̄, ȳ) for a successor relation on k-tuples instead of a formula Φ< (x̄, ȳ) for a linear order on k-tuples. This leads to the notion of successor-MSO stringto-string interpretations [9], which are the string-to-string functions computed by MSOinterpretations, assuming that a string a1 a2 · · · an is represented by its successor structure ([1, n], p 7→ p + 1(1 ≤ p < n), (Pa )a∈Σ ). Hence, we obtain: ▶ Corollary 5.5. Fix a successor-MSO string-to-string interpretation f : Σ∗ → Γ∗ . The enumeration problem that maps an rSLP G over the terminal alphabet Σ to the word f (JGK) can be solved after linear preprocessing in constant delay. The class of successor-MSO string-to-string interpretations is strictly larger than the class of polyregular functions. Moreover, in contrast to the polyregular functions, the class of successor-MSO string-to-string interpretations is not closed under composition and membership in inverse images of regular languages is undecidable [9].

6

Future work

We proved that for an MSO-definable order on k-tuples, the ranked enumeration problem for a fixed MSO-query and a given grammar-compressed string w can be solved after linear time preprocessing (where ‘linear’ means ‘linear in the size of the SLP for w’) in constant delay. Here, the MSO-query contains k free first-order variables but no free set variables. This is a restriction that we would like to overcome. Many existing results on MSO-query enumeration allow queries with free set variables [3, 5, 12, 19, 28, 29], in which case ‘constant delay’ has to be replaced by ‘output-linear delay’. At the moment, we do not see, how to extend our approach based on factorization trees to free set variables. Another desirable extension of our work would be to go from strings to forests. Only very recently a version of Simon’s factorization tree theorem for forests has been shown [1] using the framework of forest algebras. It remains to see whether this result can be combined with forest straight-line programs (in the same way as factorization trees for strings were made accessible to ordinary straight-line programs in Section 3). Constant-time traversal algorithms for forest straight-line programs have been developed in [26]. Finally, recall that our ranked enumeration algorithm outputs the tuples according to an MSO-definable linear order, whereas in [12, 19] tuples are enumerated in the order of decreasing weights (elements of an ordered abelian group) and the weight of an input string is computed by a so-called cost transducers. It is not clear, how these two concepts relate to each other. Under the cost transducer model there can be tuples with the same weight, so their order in the enumeration is arbitrary. This cannot occur in our model. References 1

Shaull Almagor, Michaël Cadilhac, and Asaf Shoham. A factorization theorem for forest algebras, 2026. URL: https://arxiv.org/abs/2605.10368, arXiv:2605.10368.

25

26

Ranked MSO-enumeration over compressed words

2

3

4

5

6

7

8 9

10

11

12

13 14 15

16 17

18

Antoine Amarilli, Pierre Bourhis, Florent Capelli, and Mikaël Monet. Ranked enumeration for MSO on trees via knowledge compilation. In Proceedings of the 27th International Conference on Database Theory, ICDT 2024, LIPIcs, pages 25:1–25:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.ICDT.2024.25. Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth. Enumeration on trees with tractable combined complexity and efficient updates. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, pages 89–103. ACM, 2019. doi:10.1145/3294052.3319702. Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth. Constant-delay enumeration for nondeterministic document spanners. ACM Transactions on Database Systems, 46(1):2:1–2:30, 2021. doi:10.1145/3436487. Guillaume Bagan. MSO queries on tree decomposable structures are computable with linear delay. In Proceedings of the 20th International Workshop Computer Science Logic (CSL 2006) and the 15th Annual Conference of the EACSL, volume 4207 of Lecture Notes in Computer Science, pages 167–181. Springer, 2006. doi:10.1007/11874683\_11. Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, and Oren Weimann. Random access to grammar-compressed strings and trees. SIAM Journal on Computing, 44(3):513–539, 2015. doi:10.1137/130936889. Mikolaj Bojanczyk. Factorization forests. In Proceedings of the 13th International Conference on Developments in Language Theory, DLT 2009, Lecture Notes in Computer Science, pages 1–17. Springer, 2009. doi:10.1007/978-3-642-02737-6\_1. Mikolaj Bojanczyk. Polyregular functions. CoRR, abs/1810.08760, 2018. URL: http://arxiv. org/abs/1810.08760, arXiv:1810.08760. Mikolaj Bojanczyk, Sandra Kiefer, and Nathan Lhote. String-to-string interpretations with polynomial-size output. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, LIPIcs, pages 106:1–106:14. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.ICALP.2019.106. Mikolaj Bojanczyk and Markus Lohrey. Transducers on compressed strings, 2026. to appear in Proceedings of the 53rd EATCS International Colloquium on Automata, Languages, and Programming, ICALP 2026. Mikolaj Bojanczyk and Pawel Parys. Xpath evaluation in linear time. In Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2008, pages 241–250. ACM, 2008. doi:10.1145/1376916.1376951. Pierre Bourhis, Alejandro Grez, Louis Jachiet, and Cristian Riveros. Ranked enumeration of MSO logic on words. In Proceedings of the 24th International Conference on Database Theory, ICDT 2021, LIPIcs, pages 20:1–20:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPICS.ICDT.2021.20. Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Information and Computation, 85(1):12–75, 1990. doi:10.1016/0890-5401(90)90043-H. Bruno Courcelle. Linear delay enumeration and monadic second-order logic. Discrete Applied Mathematics, 157(12):2675–2700, 2009. doi:10.1016/J.DAM.2008.08.021. Fernando Florenzano, Cristian Riveros, Martín Ugarte, Stijn Vansummeren, and Domagoj Vrgoc. Efficient enumeration algorithms for regular document spanners. ACM Transactions on Database Systems, 45(1):3:1–3:42, 2020. doi:10.1145/3351451. Moses Ganardi, Artur Jez, and Markus Lohrey. Balancing straight-line programs. Journal of the ACM, 68(4):27:1–27:40, 2021. doi:10.1145/3457389. Adrià Gascón, Markus Lohrey, Sebastian Maneth, Carl Philipp Reh, and Kurt Sieber. Grammarbased compression of unranked trees. Theory of Computing Systems, 64(1):141–176, 2020. doi:10.1007/s00224-019-09942-y. Leszek Gasieniec, Roman M. Kolpakov, Igor Potapov, and Paul Sant. Real-time traversal in grammar-based compressed files. In Proceedings to the 2005 Data Compression Conference, DCC 2005, page 458. IEEE Computer Society, 2005. doi:10.1109/DCC.2005.78.

M. Lohrey

19

20 21 22

23

24 25 26

27

28

29 30 31

32

33 34

35

36

Pawel Gawrychowski, Florin Manea, and Markus L. Schmid. Revisiting weighted information extraction: A simpler and faster algorithm for ranked enumeration. Proceeedings of the ACM on Managment of Data, 2(5):222:1–222:19, 2024. doi:10.1145/3695840. J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison–Wesley, Reading, MA, 1979. Wojciech Kazana and Luc Segoufin. Enumeration of monadic second-order queries on trees. ACM Transactions on Computational Logic, 14(4):25:1–25:12, 2013. doi:10.1145/2528928. Sarah Kleest-Meißner, Jonas Marasus, and Matthias Niewerth. MSO queries on trees: Enumerating answers under updates using forest algebras. Logical Methods in Computer Science, 21(4), 2025. doi:10.46298/LMCS-21(4:2)2025. Manfred Kufleitner. The height of factorization forests. In Proceedings of the 33rd International Symposium Mathematical Foundations of Computer Science 2008, MFCS 2008, Lecture Notes in Computer Science, pages 443–454. Springer, 2008. doi:10.1007/978-3-540-85238-4\_36. Markus Lohrey. Algorithmics on SLP-compressed strings: A survey. Groups Complexity Cryptology, 4(2):241–299, 2012. doi:10.1515/GCC-2012-0016. Markus Lohrey. The Compressed Word Problem for Groups. SpringerBriefs in Mathematics. Springer, 2014. doi:10.1007/978-1-4939-0748-9. Markus Lohrey, Sebastian Maneth, and Carl Philipp Reh. Constant-time tree traversal and subtree equality check for grammar-compressed trees. Algorithmica, 80(7):2082–2105, 2018. doi:10.1007/s00453-017-0331-3. Markus Lohrey, Sebastian Maneth, and Markus L. Schmid. FO-query enumeration over SLPcompressed structures of bounded degree. In Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025, LIPIcs, pages 69:1–69:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPICS.MFCS.2025.69. Markus Lohrey and Markus L. Schmid. MSO-enumeration over SLP-compressed unranked forests. TheoretiCS, 5, 2026. URL: https://doi.org/10.46298/theoretics.26.6, doi: 10.46298/THEORETICS.26.6. Martin Muñoz and Cristian Riveros. Constant-delay enumeration for SLP-compressed documents. Logical Methods in Computer Science, 21(1), 2025. doi:10.46298/LMCS-21(1:17)2025. Martín Muñoz. Dynamic direct (ranked) access of MSO query evaluation over SLP-compressed strings, 2026. URL: https://arxiv.org/abs/2603.13058, arXiv:2603.13058. Matthias Niewerth. MSO queries on trees: Enumerating answers under updates using forest algebras. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, pages 769–778. ACM, 2018. doi:10.1145/3209108.3209144. Matthias Niewerth and Luc Segoufin. Enumeration of MSO queries on strings with constant delay and logarithmic updates. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 179–191. ACM, 2018. doi:10.1145/ 3196959.3196961. Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. doi:10.1017/CBO9781139195218. Markus L. Schmid and Nicole Schweikardt. Spanner evaluation over SLP-compressed documents. In Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2021, pages 153–165. ACM, 2021. doi:10.1145/3452021.3458325. Markus L. Schmid and Nicole Schweikardt. Document spanners - A brief overview of concepts, results, and recent developments. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2022, pages 139–150. ACM, 2022. doi:10.1145/3517804.3526069. Markus L. Schmid and Nicole Schweikardt. Query evaluation over SLP-represented document databases with complex document editing. In Proceedings of the 41st ACM SIGMOD-SIGACTSIGAI Symposium on Principles of Database Systems, PODS 2022, pages 79–89. ACM, 2022. doi:10.1145/3517804.3524158.

27

28

Ranked MSO-enumeration over compressed words

37 38

A

Imre Simon. Factorization forests of finite height. Theoretical Computer Science, 72(1):65–94, 1990. doi:10.1016/0304-3975(90)90047-L. Howard Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, Boston, Basel, Berlin, 1994. doi:10.1007/978-1-4612-0289-9.

Appendix Algorithm 1 split(e, π1 , π2 , π3 )

Input: edge e = (u, v) of B, factorization πe = π1 π2 with π1 ̸= ε ̸= π2 , π3 ∈ Sat introduce new node x and replace the edge e by two edges e1 = (u, x), e2 = (x, v); 2 introduce a new leaf node y and the edge e3 = (x, y); 3 πe1 := π1 ; πe2 := π2 ; πe3 := π3 ; 4 return y; 1

In the algorithm right below, whenever split is called within right, the leaf returned in line 4 of split is also returned by right. In particular, right terminates after every call of split.

M. Lohrey

Algorithm 2 right(u)

Input: a leaf u in B Output: ⊥ if pA (u) = |A|G , else a leaf u′ in the new tree with pA (u′ ) = pA (u) + 1 1 let e = (v, w) be the first edge on the path from the leaf u to the root with πe ∈ / R; 2 if such an edge e does not exist then 3 return ⊥ 4 end ′ ′ ∗ 5 let πe = π (B, ℓ, α)τ with π ∈ (L ∪ R) , τ ∈ R ∪ {ε}; // πe must have this form 6 (B, ℓ, C) := ℓ-reduce(B, ℓ, α) ; // here we set C := B if ℓ-reduce(B, ℓ, α) = ε ′ 7 if C ̸= B or π ̸= ε then 8 let β ∈ V ∪ Σ be the right symbol in ρ(C); 9 split(e, π ′ (B, ℓ, C), (C, ℓ, α)τ, (C, r, β)(β, ℓ, ωL (β))) // (β, ℓ, ωL (β)) = ε if β∈Σ 10 else // α is the left symbol in ρ(B) and π ′ = ε ′ 11 let e = (v, x) ̸= e be the second edge leaving v; // this edge e′ must exist 12 let πe′ = (B, r, β)π ′′ with π ′′ ∈ (L ∪ R)∗ ; // πe′ must have this form 13 let γ be the right symbol in ρ(B); 14 if β ̸= γ then // we must have γ ∈ V 15 split(e′ , (B, r, γ), (γ, r, β)π ′′ , (γ, ℓ, ωL (γ))) 16 else 17 if π ′′ has the form (γ, ℓ, D)π̃ with π̃ ̸= ε then 18 split(e′ , (B, r, γ)(γ, ℓ, D), π̃, (D, ℓ, ωL (D))) 19 else // π ′′ ∈ L ∪ {ε} must hold ′′ 20 if there is an edge e = (y, z) such that there is a path of L-labelled edges from x to y and πe′′ ∈ LR(L ∪ R)∗ then 21 let πe′′ = (E, ℓ, F )π̃ with π̃ ̸= ε; 22 split(e′′ , (E, ℓ, F ), π̃, (F, ℓ, ωL (F ))) 23 else 24 let y be the unique leaf below x such that every edge on the path from x to y is L-labelled; // y = x is possible 25 return y 26 end 27 end 28 end 29 end

29

30

Ranked MSO-enumeration over compressed words

Figures 12–16 show the different cases arising in Algorithm 2. In each figure, the left part shows the situation before the call of right, whereas the right part shows the situation after the call of right. Red node labels (u, v, w, x, y, z) refer to the corresponding node names used in Algorithm 2. Edges labelled by L∗ (resp., R∗ ) stand for paths that only contain L-labelled (resp., R-labelled) edges. v

v

π′

π′ B

B C

wα

wα

R

∗

β

R

u

∗

u ωL (β)

Figure 12 The case B ̸= C; i.e., α is not the left symbol in ρ(B); see lines 7–9. The path π ′ from v to B can be also empty. We assume moreover that the τ from line 5 is empty (and similarly in the other figures). There is a similar picture for τ ∈ R.

v

v

π′

π′ B

wα R

B wα

∗

u

β ∗

R

u ωL (β)

Figure 13 The case B = C (i.e., α is the left symbol in ρ(B)) and π ′ ̸= ε; see lines 7–9.

M. Lohrey

31

vB

vB

wα R

γ

wα ∗

R

u

∗

u ωL (γ)

β

β

π ′′

π ′′ x

x

Figure 14 Here, ρ(B) = αγ and β ̸= γ; see lines 14 and 15.

vB

vB γ

wα R∗ u

γ

wα R∗ u

D

D

ωL (D)

π̃

π̃

x

x

Figure 15 Here, ρ(B) = αγ and π ′′ from line 12 has the form (γ, ℓ, D)π̃ with π̃ ̸= ε; see lines 17 and 18.

vB

vB

γx

wα R∗

L∗

R∗

Ey

u

γx

wα L∗ Ey

u

F

F ωL (F )

π̃

π̃

z

z ′′

Figure 16 Here, ρ(B) = αγ and there is an edge e = (y, z) such that there is a path of L-labelled edges from x to y and πe′′ = (E, ℓ, F )π̃ with π̃ ̸= ε; see lines 20–22. We assume moreover that π ′′ from line 12 is empty. There is a similar picture for π ′′ ∈ L.

32

Ranked MSO-enumeration over compressed words

vB

γx

wα R∗

L∗ u

y

Figure 17 Here, ρ(B) = αγ and y is a leaf; see lines 24 and 25. In this situation, the tree B is not modified.

Related documents

• String Diagrams for Process Mining#978502
• ZigZag Trie: A Novel Index for Contextual Queries#978503
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#978504
• Efficiently Linking Unstructured Data for Multi-step Reasoning#978505