Markus L Schmid
email: mlschmid@mlschmid.de

Document Spanners -A Brief Overview of Concepts, Results, and Recent Developments

Keywords: Information systems → Information retrieval, • Theory of computation → Database query languages (principles), Data structures Document Spanners, Information Extraction, Overview, Core Spanners, Regular Spanners, Refl-Spanners, SLP-represented documents

The information extraction framework of document spanners was introduced by Fagin, Kimelfeld, Reiss, and Vansummeren (PODS 2013, J. ACM 2015) as a formalisation of the query language AQL, which is used in IBM's information extraction engine SystemT. Since 2013, this framework has been investigated in depth by the principles of database management community and beyond. The present paper gives a brief overview of concepts, results, and recent developments concerning document spanners.

INTRODUCTION

The information extraction framework of document spanners has been introduced by Fagin, Kimelfeld, Reiss, and Vansummeren [START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF] as a formalisation of the query language AQL, which is used in IBM's information extraction engine SystemT. A document spanner performs information extraction by mapping a document D, formalised as a word (or string, sequence) over a finite alphabet Σ, to a relation over so-called spans of D, which are intervals [𝑖, 𝑗⟩ with 1 ⩽ 𝑖 ⩽ 𝑗 ⩽ |D| + 1, where |D| denotes the length of D. Intuitively, a span [𝑖, 𝑗⟩ of a document D = a 1 a 2 • • • a 𝑛 represents the factor a 𝑖 a 𝑖+1 • • • a 𝑗 -1 . More formally, Spans(D) := {[𝑖, 𝑗⟩ : 1 ⩽ 𝑖 ⩽ 𝑗 ⩽ |D| + 1} is the set of spans of document D. For a fixed finite set X of variables, an (X, D)-tuple (or simply, span tuple) is a function X → Spans(D). An (X, D)-relation is a set of (X, D)-tuples. Now, a document spanner (over Σ and X) (or simply, spanner) is a function that maps every document D ∈ Σ * to an (X, D)-relation.

To simplify the notation, one usually assumes the variables in X = {𝑥 1 , . . . , 𝑥 𝑘 } to be ordered, so that a span-tuple 𝑡 : X → Spans(D) is identified with the 𝑘-tuple (𝑡 (𝑥 1 ), . . . , 𝑡 (𝑥 𝑘 )).

Example 1.1. Let Σ = {a, b} and let X = {x, y, z} with x < y < z. Then the function 𝑆 that maps documents D ∈ Σ * to the (X, D)relation of all span tuples ([1, 𝑖⟩, [𝑖, 𝑖+1⟩, [𝑖+1, |D|+1⟩) such that the 𝑖 th position of D is an occurrence of b, is a spanner. For example, 𝑆 maps the document ababbab to the following span-relation (represented as a table):

x y z [1, 2⟩ [2, 3⟩ [3, 8⟩ [1, 4⟩ [4, 5⟩ [5, 8⟩ [1, 5⟩ [5, 6⟩ [6, 8⟩ [1, 7⟩ [7, 8⟩ [8, 8⟩
The initial work on document spanners was dominated by their original motivation, i. e., a formalisation of the query language AQL of IBM's information extraction engine SystemT. In this regard, the class of document spanners presented in [START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF] follow a two-stage approach: Primitive spanners extract span relations directly from the input document (see Example 1.1), which are then further manipulated by using particular algebraic operations.

The primitive spanners of [START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF] are based on particular finite automata and regular expressions called variable-set automata (vsetautomata, for short) and regex-formulas, respectively. In this paper, we use a slightly different formalism to represent primitive spanners illustrated in the following example and further explained in Section 2.1. It is straightforward to see that the spanner of Example 1.1 can be formalised by the regular expression

𝛼 := ⊲ x (a ∨ b) * ⊳ x • ⊲ y b ⊳ y • ⊲ z (a ∨ b) * ⊳ z .
Here, the symbols ⊲ x , ⊳ x are meta-symbols called markers, that define the span extracted by variable x. As usual, we write 𝐿(𝛼) for the language described by 𝛼, i.e., the set of all words (over Σ∪ { ⊲ x , ⊳ x : x ∈ X}) that match the regular expression 𝛼. Referring to Example 1.1, the fact that ⊲ x a ⊳ x ⊲ y b ⊳ y ⊲ z abbab⊳ z ∈ 𝐿(𝛼) means that ([1, 2⟩, [2, 3⟩, [3, 8⟩) is in the span relation 𝑆 (ababbab). In this sense, for a given document D, the span tuples of 𝑆 (D) are described by all ways of how 𝛼 can generate a string that equals D with the marker symbols shuffled in between the actual symbols. Likewise, one can define a finite automaton that, in addition to the symbols from Σ, may also read markers on its arcs. Nowadays, it is common to denote spanners that can be described in such a way as regular spanners (we shall discuss in Section 2.2 some particularities about different representations of regular spanner that, for simplicity, are neglected in the introduction).

The algebraic operations considered in [START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF] to further manipulate the primitive span relations extracted by regular spanner are the classical relational algebra operations of union ∪, natural join ⊲⊳, and projection 𝜋 (with their obvious meanings), and additionaly, as a special operation that is particularly useful for information extraction from textual data, also the string-equality selection 𝜍 = . String-equality selection is a unary operator parameterised by a set Z ⊆ X of variables, and the operation 𝜍 = Z selects exactly those rows of the table, for which all spans of columns in Z refer to (potentially different occurrences of) the same subwords of D. To clarify this operation, consider the regular spanner 𝑆 𝛼 described by

𝛼 := ⊲ x (a ∨ b) * ⊳ x • (a ∨ b) * • ⊲ y (a * b * ) ⊳ y
and the string-equality selection 𝜍 = {x,y} . In 𝑆 𝛼 (abaaab) we have, among others, the span tuples ([1, 3⟩, [5, 7⟩) and ([1, 3⟩, [4, 7⟩). However, the string-equality selection 𝜍 = {x,y} discards the latter and only selects the former.

In [START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF], the class of core spanners (capturing the core of SystemT's query language AQL) is defined as the closure of the class of primitive spanners that can be defined by a special class of regular expressions called regex-formulas (and denoted by RGX) under the relational algebra operations ∪, ⊲⊳, 𝜋 and the string-equality selection 𝜍 = (comprising of the operator 𝜍 = Z for all Z ⊆ X). By using classical closure properties of finite automata, it is shown in [START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF] that the class of core spanners can also be characterised by regular spanners represented by a particular kind of finite automata called vset-automata and applications of string-equality selections, followed by a projection operation -this is known as the coresimplification lemma, which we further discuss in Section 2.3.

Since their introduction in [START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF], spanners have received a lot of attention (cf., e.g., [2, 8-13, 15, 16, 27, 30-33, 38-40]). A substantial part of the literature on document spanners has focused on regular spanners. In particular, it has been shown that results of regular spanners can be enumerated with linear preprocessing and constant delay [START_REF] Amarilli | Constant-Delay Enumeration for Nondeterministic Document Spanners[END_REF][START_REF] Florenzano | Efficient Enumeration Algorithms for Regular Document Spanners[END_REF], the paper [START_REF] Maturana | Document Spanners for Extracting Incomplete Information: Expressiveness and Complexity[END_REF] is concerned with different semantics of regular spanners and their expressive power, and the articles [START_REF] Schmid | Spanner Evaluation over SLP-Compressed Documents[END_REF][START_REF] Schmid | Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing[END_REF] study the evaluation of regular spanners on compressed representations of documents. The paper [START_REF] Peterfreund | Complexity Bounds for Relational Algebra over Document Spanners[END_REF] investigates the evaluation of algebraic expressions over regular spanners. Articles that are concerned with string-equality selection are [START_REF] Freydenberger | Document Spanners: From Expressive Power to Decision Problems[END_REF] in which many hardness results for core spanner evaluation are shown, [START_REF] Freydenberger | A Logic for Document Spanners[END_REF] which, by presenting a logic that exactly covers core spanners, answers questions on the expressive power of core spanners, [START_REF] Peterfreund | Recursive Programs for Document Spanners[END_REF] which shows that datalog over regular spanners covers the whole class of core spanners, [START_REF] Dominik | Joining Extractions of Regular Expressions[END_REF] which investigates conjunctive queries on top of regular spanners, and [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF], which incorporates string-equality selections directly into the regular language that represents the underlying regular spanner. The paper [START_REF] Dominik | Dynamic Complexity of Document Spanners[END_REF] investigates the dynamic descriptive complexity of regular spanners and core spanners. The article [START_REF] Peterfreund | Grammars for Document Spanners[END_REF] studies non-regular document spanners of a different kind, where non-regularity is not caused by string-equality selections, but rather by representing spanners by context-free language descriptors (in particular, grammars) instead of regular ones.

The remainder of this paper is structured as follows. Section 2 presents more details on aspects briefly discussed in the introduction, including a more detailed discussion of representations of spanners, different semantics, and the core-simplification lemma (Sections 2.1-2.3), and static analysis and query evaluation tasks associated with spanners (Sections 2.4 and 2.5). Section 3 gives an overview of the framework of refl-spanners of [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF]. Section 4 focuses on the scenario of [START_REF] Schmid | Spanner Evaluation over SLP-Compressed Documents[END_REF][START_REF] Schmid | Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing[END_REF] of spanner evaluation on compressed representations of documents.

DOCUMENT SPANNERS

This section presents more details on aspects briefly discussed in the introduction.

A General Declarative Approach to Formalise Document Spanners

The approach of [START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF] to formalise regular document spanners by vset-automata is of a somewhat imperative nature: An algorithm -in form of a finite automaton -is defined that reads an input document and nondeterministically produces a span tuple. The extracted span relation is then simply defined as all span tuples that can be extracted from the document by a run of this algorithm.

A more declarative approach that is not restricted to regular document spanners but allows to formalise all document spanners was presented in [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF] and is based on the simple observation that any pair of document D ∈ Σ * and (X, D)-tuple 𝑡 can be represented as a string over the alphabet Σ∪{ ⊲

⊲ z a ⊲ x bc ⊲ y ac ⊳ x ac ⊳ y ⊳ z bbaa . (1)
In the literature on spanners, such string representations of documents and span tuples are called subword-marked words or ref-words (over Σ and X). Both these terms are derived from the work [START_REF] Schmid | Characterising REGEX languages by regular languages equipped with factor-referencing[END_REF],

where similar concepts are used to formalise capture groups and backreferences in regular expressions. A sound formalisation of subword-marked words over Σ and X can be obtained by simply restricting words over Σ ∪ { ⊲ x , ⊳ x : x ∈ X} in such a way that, for every x ∈ X, there is exactly one occurrence of each ⊲ x and ⊳ x , and they occur in this order. Equivalently, we can just say that subword-marked words over Σ and X are exactly those strings that can be obtained by inserting the markers { ⊲ x , ⊳ x : x ∈ X} into some document D as described by some (X, D)-tuple 𝑡.

Any given subword-marked word 𝑤 represents a document 𝔢(𝑤) (so 𝔢(•) just erases all markers) and a span tuple st(𝑤) (the function st(•) just transforms the information where the markers occur into spans in the obvious way). This means that for any spanner 𝑆 and document D, the span relation 𝑆 (D) with 𝑚 rows can be represented as a set 𝐿 D of 𝑚 subword-marked words (we just insert the markers into D as described by the span tuples). Referring to Example 1.1, 𝑆 (ababbab) can therefore be represented as

𝐿 ababbab = ⊲ x a ⊳ x ⊲ y b ⊳ y ⊲ z abbab⊳ z , ⊲ x aba ⊳ x ⊲ y b ⊳ y ⊲ z bab⊳ z , ⊲ x abab ⊳ x ⊲ y b ⊳ y ⊲ z ab⊳ z , ⊲ x ababba ⊳ x ⊲ y b ⊳ y ⊲ z ⊳ z .
Consequently, any spanner 𝑆 can be represented as a set of subword-marked words over Σ and X, namely D∈Σ * 𝐿 D . Conversely, every set 𝐿 of subword-marked words over Σ and X necessarily describes a spanner 𝐿 with 𝐿 (D) = {st(𝑤) : 𝑤 ∈ 𝐿, 𝔢(𝑤) = D}. In the following, for any set 𝐿 of subword-marked words or descriptor 𝑀 of a set of subword-marked words, we use

• to denote the represented spanner.

We can now define classes of spanners independently of specialised machine models by defining classes of sets of subwordmarked words. For example, the basic class of regular spanners is characterised by the class of those sets of subword-marked words that are regular languages (and any model for defining regular languages can then be employed as a model for describing regular spanners). Clearly, one now can replace "regular" by any established language class with their own toolkit of algorithmic models (the case where "regular" is replaced with "context-free" is studied in [START_REF] Peterfreund | Grammars for Document Spanners[END_REF]). With respect to this approach it is also worth noting that for any language over the alphabet Σ ∪ { ⊲

x , ⊳ x : x ∈ X} that is not necessarily a subword-marked language, we can obtain its subset of subword-marked words by an intersection with a regular language. Hence, any class of languages closed under intersection with regular languages can directly be interpreted as a class of spanners (in this regard, note that closure under intersection with regular languages is one of the most natural language operations, and many relevant classes of formal languages are closed under this operation, e. g., (deterministic) context-free languages, and all language classes closed under finite state transductions, see [START_REF] Hopcroft | Introduction to automata theory, languages, and computation[END_REF][START_REF] Mateescu | Aspects of Classical Language Theory[END_REF] for further details).

Particularities of Document Spanners

An important aspect of the semantics of spanners is whether span tuples are total functions X → Spans (as initially defined in [START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF]) or whether they can be partial mappings, i. e., for a (X, D)-tuple 𝑡 and x ∈ X it is possible that 𝑡 (x) is undefined (denoted as 𝑡 (x) = ⊥). This latter case is called the schemaless semantics and has been introduced and studied in [START_REF] Maturana | Document Spanners for Extracting Incomplete Information: Expressiveness and Complexity[END_REF]. In terms of the general approach described in Section 2.1, the difference between the classical semantics where span tuples are total functions and the schemaless semantics can directly be reflected in the definition of subword-marked words, i. e., we either require all markers to appear, or we allow that some markers may be missing. A subword-marked word 𝑤 over Σ and X and its associated span tuple 𝑡 = st(𝑤) are called functional if 𝑡 is a total function on X, a span relation is called functional if all its elements are functional, and a spanner 𝑆 is called functional if 𝑆 (D) is functional for every document D ∈ Σ * .

The regex-formulas used in [START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF] are obtained from regular expressions over Σ in which proper sub-expressions can be enclosed by ⊲

x • • • ⊳ x . Such expressions, if interpreted as expressions over Σ ∪ { ⊲ x , ⊳ x : x ∈ X}, can define subword-marked languages and therefore document spanners. Note that such spanners are necessarily hierarchical in the sense that the pairs of brackets ⊲

x • • • ⊳ x
for different 𝑥 ∈ X are either strictly nested or disjoint; i. e., overlappings like in (1) cannot be described. In particular, this imlies that the class of spanners solely described by regex-formulas is strictly contained in those described by vset-automata. However -as a main observation of [START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF] -if one considers the {∪, ⊲⊳, 𝜋 }-closures of the class of spanners described by regex-formulas and the class of spanners described by vset-automata, one obtains the same class of spanners, namely, the class of spanners that can directly be described by vset-automata.

Subword-marked words (or runs of vset-automata) do not necessarily represent a document D and an (X, D)-tuple 𝑡 in a unique way. More precisely, the represented span tuple is invariant with respect to the order of consecutive occurrences of markers in the subword-marked word (or the order in which a vset-automata performs consecutive marker-transitions). We discuss in Section 2.4 how this issue can matter for decision problems for spanners. There are two obvious ways of how to deal with this non-uniqueness, which have both been considered in the literature. Option 1 is to normalise by restricting the model of subword-marked languages (and therefore automata accepting such languages), by fixing an order on { ⊲

x , ⊳ x : x ∈ X} and requiring factors of consecutive markers of subword-marked words to respect this order (this has been done e.g. in [START_REF] Doleschal | Split-Correctness in Information Extraction[END_REF][START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF][START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF]). Option 2 is to represent factors of consecutive markers as sets of markers; the according variant of vset-automata is called extended vset-automata [START_REF] Florenzano | Efficient Enumeration Algorithms for Regular Document Spanners[END_REF]. In terms of the general approach described in Section 2.1, this means that subword-marked words now are built from letters in Σ and elements of the power set of { ⊲ x , ⊳ x : x ∈ X}. For example, the subword-marked word from (1) is represented by { ⊲ z }a{ ⊲ x }bc{ ⊲ y }ac{⊳ x }ac{⊳ y , ⊳ z }bbaa.

Core-Simplification Lemma

As already mentioned in Section 1, the core spanners are defined as those spanners that can be described by applying the operations union, natural join, projection, and string-equality selection to spanners described by regex-formulas; in symbols, this class is denoted as RGX {∪,⊲⊳,𝜋,𝜍 = } . The core-simplification lemma states that any core spanner can be represented as

𝜋 Y (𝜍 = Z 1 𝜍 = Z 2 . . . 𝜍 = Z 𝑘 ( 𝑀 )) ,
where Y, Z 1 , . . . , Z 𝑘 ⊆ X, and 𝑀 describes a regular language of subset-marked words (e.g., 𝑀 is a vset-automaton). For functional spanners, this has been proved in [START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF], and it also holds verbatim for the schemaless case (proved in [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF] by combining the approach of [START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF] with results from [START_REF] Maturana | Document Spanners for Extracting Incomplete Information: Expressiveness and Complexity[END_REF]). The core-simplification lemma tells us that, in terms of expressive power, the string-equality selection (followed by a projection) is the only feature of core spanners that properly exceeds the expressive power of regular languages. As recent research has proven, this seemingly "little" increase of expressivity has severe implications for the complexity (and even (un)decidability) of static analysis and evaluation problems; we discuss this in Section 2.4.

Decision Problems for Spanners

The following typical decision problems for spanners have been studied in the literature; the first two of these are evaluation problems whereas the other are static analysis problems.

ModelChecking: Given a spanner 𝑆 over Σ and X, a document D ∈ Σ * , and an (X, D)-tuple 𝑡, decide whether 𝑡 ∈ 𝑆 (D).

NonEmptiness: Given a spanner 𝑆 over Σ and X and a document D ∈ Σ * , decide whether 𝑆 (D) ≠ ∅. Satisfiability: Given a spanner 𝑆 over Σ and X, decide whether there exists a document D ∈ Σ * with 𝑆 (D) ≠ ∅. Hierarchicality: For a given spanner 𝑆 over Σ and X, decide whether 𝑆 is hierarchical. Containment: Given two spanners 𝑆 1 , 𝑆 2 over Σ and X, decide whether 𝑆 1 (D) ⊆ 𝑆 2 (D) holds for all documents D ∈ Σ * . Equivalence: Given two spanners 𝑆 1 , 𝑆 2 over Σ and X, decide whether 𝑆 1 (D) = 𝑆 2 (D) holds for all documents D ∈ Σ * .

Obviously, the complexity and decidability of these problems depend on the class of spanners at hand.

For regular spanners, due to the positive algorithmic properties of regular languages, all these problems are decidable and have acceptable upper complexity bounds. Let us illustrate this for the problems ModelChecking and Equivalence and the setting where regular spanners are represented by non-deterministic finite automata (NFA) that accept subword-marked languages.

We can decide ModelChecking as follows. The input consists of an NFA 𝑀, a document D and a span tuple 𝑡. We can check whether 𝑡 ∈ 𝑀 (D) by transforming D and 𝑡 into a subword-marked word 𝑤 and check whether 𝑀 accepts 𝑤. The obvious problem with this approach is what we already have discussed in the last paragraph of Section 2.2: we do not know a priori in which order we have to insert consecutive marker symbols into D in order to construct 𝑤. There are several ways of handling this issue, e. g., we could require 𝑀 to be normalised or to be an extended vset-automaton, or we could modify 𝑀 such that it satisfies one of these requirements (potentially resulting in an exponential size blow-up), or we could try to utilise that we know that 𝑀 will only accept proper subwordmarked words to handle the question of the right order of the markers on-the-fly while processing 𝑤 with 𝑀.

The situation is similar for the problem Equivalence: The input now consists of two NFAs 𝑀 1 and 𝑀 2 that accept subwordmarked languages. One can reduce the question whether 𝑀 1 and 𝑀 2 describe the same spanner to the the question whether suitably modified NFAs 𝑀 ′ 1 and 𝑀 ′ 2 accept the same regular language. The picture is quite different (i. e., worse) for core spanners. Let us first give an intuition before discussing known results. The power to define repetitions of strings is a feature that exceeds the expressive power of regular and even context-free languages (the copy language {𝑤𝑤 : 𝑤 ∈ Σ * } is the classical textbook example), and, in terms of the Chomsky-hierarchy, is covered by context-sensitive languages, which are not famous for having good algorithmic properties. Leaving classical questions of formal language theory aside, it is also well-known that the complexity of string processing and pattern matching problems substantially increases if extended by string repetition operators (but note that regular expressions as used in practical contexts are usually extended by such string repetition operators). Finally, string repetitions are also known to pose very hard combinatorial problems as usually investigated in combinatorics on words (e. g., word equations). We shall illustrate with three particular examples how these observations are crucial for core spanners.

First, consider the regular expression

𝛼 := ⊲ x 1 Σ * ⊳ x 1 ⊲ x 2 Σ * ⊳ x 2 • • • ⊲ x 𝑛 Σ * ⊳ x 𝑛
that obviously describes a subword-marked language over Σ and

X = {x 1 , x 2 , . . . , x 𝑛 } (in fact, 𝛼 is a regex-formula). Now check- ing, for some Z 1 , Z 2 , . . . , Z 𝑘 ⊆ {x 1 , x 2 , . . . , x 𝑛 } and a document D, whether the empty tuple is in 𝜋 ∅ (𝜍 = Z 1 𝜍 = Z 2 . . . 𝜍 = Z 𝑘 ( 𝛼 )) (D), is
identical to checking whether D can be factorised into 𝑛 factors such that for each Z 𝑖 all factors that correspond to the variables in Z 𝑖 are the same. This is the pattern matching problem with variables (also known as the membership problem for pattern languages, or the matching problem for regular expressions with backreferences), a well-known NP-complete problem (see, e. g., [START_REF] Manea | Matching Patterns with Variables[END_REF]).

As another example, let 𝑟 1 , 𝑟 2 , . . . , 𝑟 𝑛 be some regular expressions over Σ, and let

𝛼 = ⊲ x 1 𝑟 1 ⊳ x 1 ⊲ x 2 𝑟 2 ⊳ x 2 . . . ⊲ x 𝑛 𝑟 𝑛 ⊳ x 𝑛 (again,
note that this is a regex-formula). Then there is a word 𝑤 with

(𝜍 = {x 1 ,x 2 ,...,x 𝑛 } ( 𝛼 ))(𝑤) ≠ ∅ if and only if 𝑛 𝑖=1 𝐿(𝑟 𝑖 ) ≠ ∅.
Consequently, core spanners (with only one string-equality selection) can express intersection non-emptiness of regular languages, a wellknown PSpace-complete problem.

Finally, let us discuss an example of how core spanners can describe relations typically described by word equations (see [12, Proposition 3.7, Example 3.8, Theorem 3.13] for details). For given strings 𝑢, 𝑣 ∈ Σ * , we write 𝑢 ∼ com 𝑣 if there exists a 𝑝 ∈ Σ * such that 𝑢, 𝑣 ∈ {𝑝} * , and we write 𝑢 ∼ cyc 𝑣 if 𝑢 is a cyclic shift of 𝑣, i.e., there exist strings 𝑤 1 , 𝑤 2 such that 𝑢 = 𝑤 1 𝑤 2 and 𝑣 = 𝑤 2 𝑤 1 . It is a well-known fact that ∼ com can be expressed by the word equation xy = yx (i. e., 𝑢 ∼ com 𝑣 if and only if the substitution x ↦ → 𝑢 and y ↦ → 𝑣 satisfies the equation), and ∼ cyc can be expressed by the word equation xz = zy (i. e., 𝑢 ∼ cyc 𝑣 if and only if there is some string 𝑤 such that the substitution x ↦ → 𝑢, y ↦ → 𝑣 and z ↦ → 𝑤 satisfies the equation). It is shown in [START_REF] Freydenberger | Document Spanners: From Expressive Power to Decision Problems[END_REF]Proposition 3.7] that one can define a core spanner 𝑆 com over Σ and {x, y} such that 𝑆 com (D) represents exactly those pairs (𝑢, 𝑣) of factors of D with 𝑢 ∼ com 𝑣; analogously, a core spanner 𝑆 cyc (D) can be constructed. In general, it is shown in [START_REF] Freydenberger | Document Spanners: From Expressive Power to Decision Problems[END_REF] that, in a specific sense (see [12, Theorems 3.12 and 3.13] for details), core spanners are as expressive as word equations with regular constraints. This provides valuable insight in the complexity of core spanners, because word equations pose notoriously hard questions [START_REF] Volker | More Than 1700 Years of Word Equations[END_REF]. For example, whether solving word equations (without regular constraints) is in NP is still unknown -even for quadratic equations [START_REF] Day | On the Structure of Solution Sets to Regular Word Equations[END_REF][START_REF] Michael | On Quadratic Word Equations[END_REF] where every variable has at most two occurrences (which is the case for the two particular word equations mentioned above).

These explanations show how powerful the string-equality selection is, and, consequently, that extending regular spanners by this operation (i. e., extending regular spanners to core spanners) has severe consequences in terms of decidability and expressive power. In particular, from [START_REF] Freydenberger | Document Spanners: From Expressive Power to Decision Problems[END_REF] we know that ModelChecking and NonEmptiness are NP-hard, Satisfiability and Hierarchicality are PSpace-complete, and Containment and Equivalence are even undecidable.

The Enumeration Problem for Regular Spanners

A special focus of the recent research on spanners has been dedicated to the enumeration problem: Given a spanner 𝑆 over Σ and X, and a document D, we want to enumerate, without repetition, all tuples in 𝑆 (D). In this setting, one is interested in algorithms that proceed in two phases: a preprocessing phase in which suitable data structures are built, and an enumeration phase in which these data structures are used to output the result tuples. One aims at run-time guarantees on the time spent for the preprocessing phase and the delay during the enumeration phase (i. e., the time needed between producing two elements of the result). Usually, these run-time guarantees are stated in terms of data complexity, i.e., the input size is measured in the length of the document D while the dependency on the (size of the representation of the) spanner 𝑆 is hidden in the O-notation. The best one can hope for is linear preprocessing and constant delay. And for regular spanners, the enumeration problem can indeed be solved with linear preprocessing and constant delay: In [START_REF] Florenzano | Efficient Enumeration Algorithms for Regular Document Spanners[END_REF] it is shown how to achieve this for regular spanners that are represented by extended deterministic vset-automata. An immediate consequence of this result is that we can also achieve linear preprocessing and constant delay enumeration for other representations of regular spanners (including nondeterministic automata, regular expressions, etc.) since the time needed for translating them into extended deterministic vset-automata vanishes in the data complexity perspective. An important improvement of this was achieved in [START_REF] Amarilli | Constant-Delay Enumeration for Nondeterministic Document Spanners[END_REF] (see also [START_REF] Amarilli | Constant-Delay Enumeration for Nondeterministic Document Spanners[END_REF]), who devised an enumeration algorithm directly for regular spanners represented by vset-automata; this algorithm has linear preprocessing and constant delay and, moreover, its preprocessing time and delay are also polynomial in the size of the vset-automaton's representation.

REFL-SPANNERS

As discussed in Section 2.4, static analysis and evaluation for core spanners is much more difficult (and in some cases even undecidable) compared to regular spanners. We have already seen, on an intuitive level, how the functionality of string-equality selections is responsible for this increase in complexity. In order to gain a better understanding of this phenomenon, let us take a more thorough look at the interplay of the core spanners' features.

As discussed in Section 2.4, checking for

𝛼 := ⊲ x 1 Σ * ⊳ x 1 ⊲ x 2 Σ * ⊳ x 2 • • • ⊲ x 𝑛 Σ * ⊳ x 𝑛 ,
a document D ∈ Σ * , and sets Z 1 , . . . , Z 𝑘 ⊆ {x 1 , . . . , x 𝑛 } whether the empty tuple is in

𝜋 ∅ (𝜍 = Z 1 . . . 𝜍 = Z 𝑘 ( 𝛼 )) (D)
encodes an intractable pattern matching problem. More precisely, in order to check this, we have to check whether there is at least one subword-marked word 𝑤 ∈ 𝐿(𝛼) with 𝔢(𝑤) = D, such that the markers ⊲ x • • • ⊳ x enclose factors that satisfy the string-equality selections. Our intuition that in the worst-case we have to exhaustively check all such subword-marked words is confirmed by the known NP-completeness of this task.

At this point, however, one might ask whether a spanner of the form 𝜋 ∅ (𝜍 = Z 1 . . . 𝜍 = Z 𝑘 ( 𝛼 )) really describes a reasonable information extraction task, or whether it can be considered as a rather special case. After all, this spanner considers all ways of extracting certain span tuples from a document (described by the regular spanner 𝛼), checks whether at least one of them satisfies a complex property described by the string-equality selections, and finally "returns" (by means of the projection 𝜋 ∅ ) either yes or no. This spanner implements a (rather complex) task of string analysis (or pattern matching or parsing): it answers the question "Does this string satisfy a certain property?" (or: "Does it have the right form?"), while it extracts either the empty set or the singleton set consisting of the empty tuple. This does not seem to fit well to the original intention of extracting information from a document, i. e., the assumption that documents contain information in a sequential way that we wish to extract and compile into a relational form. In fact, it is not far-fetched to assume that if we define a spanner for some information extraction task and this spanner contains a variable x, then we also want -at least as an intermediate result -the actual content extracted by variable x to appear in our constructed table (whether the x-column is projected away by some further processing of the data is another story).

It is easy to see that dropping 𝜋 ∅ from a core spanner can make a huge difference. For example, checking for a given span tuple 𝑡 whether

𝑡 ∈ 𝜍 = Z 1 𝜍 = Z 2 . . . 𝜍 = Z 𝑘 ( 𝛼 ) (D)
can be done quite efficiently (regardless of the actual string-equality selections), since 𝑡 already tells us the contents of the extracted spans.

Since regular spanners may be non-hierarchical (i. e., variables may address overlapping spans, cf. Section 2.2), core spanners can use string-equality selections over overlapping spans. It is already somewhat difficult to come up with a practical example of a regular spanner that extracts overlapping spans. A possible scenario is that we do not have enough a-priori knowledge about the structure of the documents in order to define a spanner in a clean way, e. g., we know that regions of interest that we want to extract are separated by semicolons, but semicolons can also occur inside these regions with some other meaning. In this case, it can make sense to allow extracted spans to overlap each other in order to cover all possibilities. But a reasonable real-world example of an information extraction task for which it is necessary to extract overlapping spans with a regular spanner and then use string-equality selections on these overlapping spans is arguably rather hard to find. The fact that string-equality selections on overlapping spans can be used for describing complicated word combinatorial properties (see Section 2.4) raises the question whether we can avoid some complexity issues of core spanners by prohibiting overlapping spans to be subjected to string-equality selections. Note that such a restriction is much weaker than restricting to hierarchical spanners, since we can still extract overlapping spans, we just are not allowed to use the string-equality operator on overlapping spans (in particular, the full class of regular spanners -which are not necessarily hierarchical -is still covered).

The considerations from above are the motivation for the class of refl-spanners introduced in [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF]. Refl-spanners are designed to properly lie in between regular spanners and core spanners, with the overall goal of having an expressive power that covers the relevant features of core spanners, while at the same time having complexity and decidability properties that are better than that of the full class of core spanners. In the remainder of this section, we discuss the main idea of this class of spanners and give a brief overview of its properties.

String-Equalities as Meta Symbols

The only non-regular feature of core spanners is the string-equality selection. This is immediately clear on an intuitive level, and it is also demonstrated by the core-simplification lemma (cf. Section 2.3): a regular spanner plus string-equality selections plus a projection can describe every core spanner. The main idea of refl-spanners is to express -to at least some extent -the string-equality selections also as a regular feature, i. e., by meta symbols in the regular subword-marked language that describes the regular spanner. This yields a class of spanners that, just like regular spanners, are fully described by regular languages (with meta symbols) and therefore by automata, regular expressions etc. As a (intended) side effect of this different conceptual approach, refl-spanners are not capable to describe some of those features discussed above, i. e., features that are obviously problematic with respect to complexity and decidability while at the same time seem not to have substantial practical relevance.

The overall idea is very simple and directly extends a knownapproach from regular expressions with backreferences (see [START_REF] Dominik | Deterministic regular expressions with back-references[END_REF][START_REF] Schmid | Characterising REGEX languages by regular languages equipped with factor-referencing[END_REF]): In addition to markers ⊲

x and ⊳ x (that describe the span extracted by variable x) in subword-marked words, we also allow x as a meta symbol in subword-marked words, which describes a copy or reference of whatever factor is extracted in the span of variable x. In order to make this meaningful, we only have to forbid that x occurs between ⊲ x and ⊳ x . This extension of the concept of subword-marked words (and languages) is called ref-words (and ref-languages). 1 Obviously, the idea is that references x in a ref-word describe string-equality selections. Let us illustrate this with an example. Consider the regular spanner represented by

𝛼 := a b * ⊲ x (a ∨ b) * ⊳ x (b ∨ c) * ⊲ y (a ∨ b) * ⊳ y b * , (2)
and assume we are interested in the core spanner 𝑆 := 𝜍 = {x,y} ( 𝛼 ). The subword-marked language 𝐿(𝛼) contains words like a ⊲

x aba ⊳ x ⊲ y ab ⊳ y and a ⊲

x aa ⊳ x ⊲ y ab⊳ y 1 In the literature on spanners, subword-marked words (as defined here; see Section 2.1) are usually called ref-words (see, e. g., [START_REF] Doleschal | Split-Correctness in Information Extraction[END_REF][START_REF] Freydenberger | A Logic for Document Spanners[END_REF][START_REF] Dominik | Joining Extractions of Regular Expressions[END_REF][START_REF] Dominik | Dynamic Complexity of Document Spanners[END_REF]). This "misnomer" has historical reasons: Ref-words have originally been used in [START_REF] Schmid | Characterising REGEX languages by regular languages equipped with factor-referencing[END_REF] (in the context of regular expressions with backreferences) as words that contain references x to some of their subwords, which are explicitly marked by brackets ⊲ x • • • ⊳ x . Consequently, the ref-words of [START_REF] Schmid | Characterising REGEX languages by regular languages equipped with factor-referencing[END_REF] are syntactically the same as what is called ref-words in the context of refl-spanners.

Inspired by the approach of [START_REF] Schmid | Characterising REGEX languages by regular languages equipped with factor-referencing[END_REF], papers have adopted ref-words without any references x, but with the "subword marking property" by meta symbols ⊲ x • • • ⊳ x , in order to describe regular spanners. Especially for refl-spanners, we need ref-words in the sense of [START_REF] Schmid | Characterising REGEX languages by regular languages equipped with factor-referencing[END_REF], i. e., with actual references, but also the variants without references (which are called ref-words in some papers), so [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF] introduced the term subword-marked word for the latter. In the context of this development, it is also interesting to note that both the papers [START_REF] Fagin | Document Spanners: A Formal Approach to Information Extraction[END_REF] (the origin of document spanners) and [START_REF] Schmid | Characterising REGEX languages by regular languages equipped with factor-referencing[END_REF] (a work on regular expressions with backreferences) use -apparently without any knowledge of each other when published -similar automata and regular expression based concepts for describing spans. In fact, the memory automata from [START_REF] Schmid | Characterising REGEX languages by regular languages equipped with factor-referencing[END_REF] can be seen as vset-automata that also evaluate string-equality selections on-the-fly.

which, due to the string-equality selection 𝜍 = {x,y} will not represent a row in any table extracted by the spanner 𝑆. In fact, the only part of 𝐿(𝛼) that matters for 𝑆 is its subset

𝑢 ∈ {a,b} * 𝐿(a b * ⊲ x 𝑢 ⊳ x (b ∨ c) * ⊲ y 𝑢 ⊳ y b * ) .
Consequently, instead of using the subword-marked language given by 𝛼, we use the ref-language given by

𝛼 ′ := a b * ⊲ x (a ∨ b) * ⊳ x (b ∨ c) * ⊲ y x ⊳ y b * . (3)
A given ref-word 𝑤 describes a document and a span tuple as follows. First, by 𝔡(𝑤), we denote the "de-referenced version of 𝑤", i.e., the subword-marked word that is obtained from 𝑤 by replacing each x by whatever appears in between ⊲

x and ⊳ x (in general, this has to be done with some care due to possible nesting), e. g., 𝔡(a ⊲

x aba ⊳ x ⊲ y x⊳ y ) = a ⊲ x aba ⊳ x ⊲ y aba⊳ y . Since 𝔡(𝑤) is a subwordmarked word, it describes a document D and (X, D)-tuple as usual.

For our particular example of (3), the ref-words of the regular ref-language 𝐿(𝛼 ′ ) describe exactly the non-regular core spanner 𝑆 := 𝜍 = {x,y} ( 𝛼 ). In general, the formal definition of Section 2.1 extends as follows: Any regular ref-language 𝐿 describes the reflspanner 𝐿 where, for every document D ∈ Σ * we have

𝐿 (D) := st(𝔡(𝑤)) : 𝑤 ∈ 𝐿, 𝔢(𝔡(𝑤)) = D .
In symbols, this can also be written as 𝐿 = 𝔡(𝐿) where 𝔡(𝐿) := {𝔡(𝑤) : 𝑤 ∈ 𝐿} is just a subword-marked language. Obviously, this framework can be used for all kinds of ref-languages (not only regular ones), but the class of refl-spanners from [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF] is based on regular ref-languages.

Just like regular spanners, refl-spanners are solely defined by finite automata (or other regular language description mechanisms), namely automata that accept regular ref-languages.

Let us consider a further, more involved example, where

𝛼 := ⊲ x a * ⊲ y b * ⊳ x a * c * x ⊳ y abc y .
An example of a ref-word in 𝐿(𝛼) is 𝑤 := ⊲ x aa ⊲ y bbb ⊳ x ccx ⊳ y abcy.

For obtaining the described document D, the 𝔡(•) function needs to first substitute the reference x and then the reference y (since the latter depends on x):

⊲ x aa ⊲ y bbb ⊳ x cc x ⊳ y abc y ⊲ x aa ⊲ y bbb ⊳ x ccaabbb ⊳ y abc y ⊲ x aa ⊲ y bbb ⊳ x ccaabbb ⊳ y abcbbbccaabbb aabbbccaabbbabcbbbccaabbb .
In the original core spanner formulation, we can define the spanner described by 𝛼 as 𝜋 {x,y} 𝜍 = {x,z 1 } 𝜍 = {y,z 2 } ( 𝛼 ′ ), where

𝛼 ′ := ⊲ x a * ⊲ y b * ⊳ x a * c * ⊲ z 1 Σ * ⊳ z 1 ⊳ y abc ⊲ z 2 Σ * ⊳ z 2 .
Obviously, a reference x in a ref-language implements a stringequality selection without extracting a span, while a core spanner must extract spans in order to apply the string-equality selection. This is not a restriction for refl-spanners, since we can always also extract spans of references by using ⊲ z x x⊳ z x for a new variable z x .

The crucial restriction of refl-spanners compared to core spanners is the following: If we want to implement a string-equality selection 𝜍 = {x,y} , but the brackets

⊲ x • • • ⊳ x and ⊲ y • • • ⊳ y enclose
other marker symbols, then we cannot simply replace one of them by a reference without substantially changing the meaning of the spanner. This obviously limits the expressive power of refl-spanners in comparison to the full class of core spanners. On the other hand, it also makes it impossible to define string-equality selections on overlapping spans, which, in terms of complexity and decidability, is an asset (see Section 3.3).

Expressive Power of Refl-Spanners

We first note that in order for refl-spanners to describe a subclass of core spanners, we have to restrict them in such a way that the underlying ref-language cannot have an unbounded number of references for some variable x, as, e. g., in the ref-language described by ⊲

x a * b ⊳ x (x) * . We call a refl-spanner reference-bounded if it is described by a ref-language 𝐿 for which there exists a number 𝑘 such that for all 𝑤 ∈ 𝐿 and x ∈ X we have |𝑤 | x ⩽ 𝑘 (here, |𝑤 | x denotes the number of occurrences of the letter x in the word 𝑤). Without this restriction, regular ref-languages can describe spanners that provably are not core spanners, as demonstrated by the example

𝐿(a + ⊲ x b + ⊳ x (a + x) * a + ) (see [9, Theorem 6.1])).
Any reference-bounded refl-spanner translates into a core spanner as follows. Intuitively, for every variable x, we use 𝑘 new variables y x,1 , y x,2 , . . . , y x,𝑘 (where 𝑘 is the bound on the number of references), and we replace each reference x by ⊲ y x,𝑖 Σ * ⊳ y x,𝑖 for some 𝑖, and finally use a string-equality selection 𝜍 = {y x,1 ,...,y x,𝑘 } . The question which core spanners can be represented as reflspanners is much more difficult. We already have seen a simple example above, namely, the core spanner 𝑆 := 𝜍 = {x,y} ( 𝛼 ) from ( 2) can be represented by 𝛼 ′ from (3). However, the situation slightly changes when replacing 𝛼 with

𝛽 := a b * ⊲ x a (a ∨ b) * ⊳ x (b ∨ c) * ⊲ y (a ∨ b) * b ⊳ y b * , since now neither a b * ⊲ x a (a ∨ b) * ⊳ x (b ∨ c) * ⊲ y x ⊳ y b * , nor a b * ⊲ x (a ∨ b) * b ⊳ x (b ∨ c) * ⊲ y x ⊳ y b *
is a correct representation. Luckily, in this case we can use

𝛽 ′ := a b * ⊲ x 𝛾 ⊳ x (b ∨ c) * ⊲ y x ⊳ y b * ,
where 𝛾 is a regular expression describing the language

𝐿(a (a ∨ b) * ) ∩ 𝐿((a ∨ b) * b).
The situation gets much more difficult when considering core spanners with string-equality selections on nested spans, or even overlapping spans. For example, it seems difficult to transform

𝜍 = {x,y} 𝐿( ⊲ x a * ⊳ x ⊲ y ⊲ z a * ⊳ z a * ⊳ y ) , or 𝜍 = {x,y} ( 𝐿( ⊲ x . . . ⊲ y . . . ⊳ x . . . ⊳ y ) )
into a refl-spanner. These examples suggest that the refl-spanner formalism is much less powerful than core spanners, which is to be expected, since we have to pay a price for the fact that we can solve many problems for refl-spanners much more efficiently than for core spanners (see Section 3.3).

As a main result of [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF], it is shown that if a core spanner 𝑆 only uses non-overlapping string-equality selections, then we can define a refl-spanner that extracts the same span relations as 𝑆, with the only difference that some columns are split into several columns. Let us explain this in some more detail.

A sequence of string-equality selections

𝜍 = Z 1 , . . . , 𝜍 = Z 𝑘
is called non-overlapping with respect to a regular spanner 𝑆 if there are no x, y ∈ Z 1 ∪ • • • ∪ Z 𝑘 with x ≠ y such that 𝑆 extracts overlapping spans for x and y from any document.

Let 𝑡 be a span tuple, let 𝜆 ⊆ X and let x ∉ X be a new variable. We write 𝜆→x (𝑡) to describe the span tuple 𝑡 ′ in which the columns of variables in 𝜆 have been fusioned into a new column x as follows: 𝑡 ′ (x) = [𝑖 ′ , 𝑗 ′ ⟩, where 𝑖 ′ is the minimum of all 𝑖 that occur as "left bounds" of the spans 𝑡 (z) = [𝑖, 𝑗⟩ of the variables z ∈ 𝜆, and 𝑗 ′ is the maximum of all 𝑗 that occur as "right bounds" of the spans

𝑡 (z) = [𝑖, 𝑗⟩ of the variables z ∈ 𝜆. For ex- ample, let 𝑡 = ([1, 3⟩, [2, 6⟩, [3, 7⟩) be a ({x 1 , x 2 , x 3 }, D)-tuple, then {x 1 ,x 3 }→y (𝑡) = ([1, 7⟩, [2, 6⟩
) is a ({y, x 2 }, D)-tuple. We lift this operation to an operation on spanners in the obvious way.

The mentioned result of [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF] can now be stated as follows. For any core spanner 𝜍 =

𝜍 = Z 1 . . . 𝜍 = Z 𝑘 (𝑆) = 𝜆 1 →y 1 . . . 𝜆 𝑝 →y 𝑝 (𝑆 ′ ) .
Intuitively speaking, as long as the string-equality selections are non-overlapping, we can transform a core spanner into a reflspanner, that describes the core spanner up to the difference that the actual columns are split into several columns.

Evaluation and Static Analysis of Refl-Spanners

With respect to the complexity and decidability of evaluation and static analysis problems, refl-spanners lie strictly between the classes of regular spanners and core spanners. Recall from Section 2.4 that the problem ModelChecking can be solved for regular spanners by checking if a finite automaton accepts a given word, while for the full class of core spanners the task is intractable. For refl-spanners, we can mimic the same approach that works for regular spannersthis is mainly due to the fact that refl-spanners can also be described by single NFAs. More precisely, if 𝑀 is an NFA that represents a reflspanner (i. e., it accepts a ref-language), then we can again combine 𝑡 and D into a subword-marked word 𝑤. However, this 𝑤 is not the ref-word for which we have to check acceptance with respect to 𝑀, but its image under 𝔡(•), i. e., the subword-marked word after replacing the references. Instead of checking 𝑤 ∈ 𝐿(𝑀), we have to check whether 𝑀 accepts some ref-word 𝑣 with 𝔡(𝑣) = 𝑤 (note that such a 𝑣 is not uniquely determined by D and 𝑡). To this end, we interpret the x-arcs of 𝑀 as paths reading the factor 𝑤 x of D that corresponds to reference x (note that 𝑤 x is uniquely described by D and the span 𝑡 (x)), and then check whether 𝑤 is accepted. If 𝑤 is accepted, then the accepting run actually describes a ref-word 𝑣 (via the replaced x-transitions), such that 𝔡(𝑣) is a subword-marked word with 𝔢(𝔡(𝑣)) = D and st(𝔡(𝑣)) = 𝑡; thus, 𝑡 ∈ 𝑀 (D). If 𝑤 is rejected, then no such 𝑣 can exist and therefore 𝑡 ∉ 𝑀 (D). Due to the replacement of x-arcs by paths of length O(|D|), this algorithm runs in time quadratic in |D|, but, by using standard string data-structures, it can be improved to linear in |D| (i. e., with the same running time as for regular spanners); cf. [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF].

In contrast, the problem NonEmptiness (i. e., checking 𝑆 (D) ≠ ∅ when given a spanner 𝑆 and a document D), can be solved efficiently for regular spanners by just interpreting marker-transitions of the NFA as 𝜀-transitions (where 𝜀 is the empty word) and checking if the word D is accepted by this modified NFA. For refl-spanners, however, this idea does not work and NonEmptiness is NP-hard [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF] (just like for core spanners [START_REF] Freydenberger | Document Spanners: From Expressive Power to Decision Problems[END_REF]).

The problem Satisfiability (i. e., checking for given spanner 𝑆 whether there exists a document D with 𝑆 (D) ≠ ∅), reduces to checking non-emptiness for an NFA in the case of regular spanners, and the same is true for refl-spanner. Thus, the problem can be solved efficiently for refl-spanners [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF], while it is intractable for core-spanners [START_REF] Freydenberger | Document Spanners: From Expressive Power to Decision Problems[END_REF].

The problem Containment is PSpace-complete for regular spanners, since the problem is closely related to the containment problem for regular languages. For core spanners, on the other hand, the problem is undecidable (in fact, not even semi-decidable) [START_REF] Freydenberger | Document Spanners: From Expressive Power to Decision Problems[END_REF]. For refl-spanners, we can at least show that the problem is decidable if we restrict the refl-spanners in such a way that every reference is necessarily extracted by its own private extraction variable [START_REF] Schmid | A Purely Regular Approach to Non-Regular Core Spanners[END_REF]. This seems like a strong restriction for refl-spanners, but note that for core spanners we necessarily have a rather similar situation: if we want to use string-equality selections on some spans, we have to explicitly extract them by variables first.

SPANNERS ON COMPRESSED DOCUMENTS

The underlying data model for document spanners are documents D ∈ Σ * , i.e., finite strings over a finite alphabet. Unlike relational data, strings usually contain many redundancies, and there are simple and straightforward techniques to use these redundancies for compression. This is especially true for natural language, but also for more abstract sequences like bio-sequences or sequential log-files of large systems.

A classical and widely used compression scheme for strings with substantial practical relevance are so-called straight-line programs (SLPs). Let us briefly describe this concept in a way that is tailored to the following exposition. An SLP S is a directed acyclic graph (DAG) whose nodes all have a left and a right child, except for the sinks 𝑇 𝑥 of the graph, which uniquely represent the symbols 𝑥 of the alphabet Σ. For an illustration see Figure 1. Any node 𝐴 with left and right children 𝐵 and 𝐶 represents the document 𝔇(𝐴) = 𝔇(𝐵)𝔇(𝐶), where 𝔇(𝑇 𝑥 ) = 𝑥 for the sinks 𝑇 𝑥 . For example, for node 𝐵 in Figure 1, we have

𝔇(𝐵) = 𝔇(𝐸)𝔇(𝐶) = 𝔇(𝑇 a )𝔇(𝑇 b )𝔇(𝐹 )𝔇(𝑇 a ) (4) = 𝔇(𝑇 a )𝔇(𝑇 b )𝔇(𝑇 b )𝔇(𝑇 c )𝔇(𝑇 a ) = abbca . (5)
By designating some of the nodes of an SLP to represent documents, an SLP represents a set of documents, which we will call a document database. In the example of Figure 1, these designated nodes are 𝐴 1 , 𝐴 2 and 𝐴 3 ; thus, the SLP represents the document database

DDB S = {𝔇(𝐴 1 ), 𝔇(𝐴 2 ), 𝔇(𝐴 3 )} = {ababbcabca, bcabcaabbca, ababbca} .
The classical use of SLPs is as compressed representations of single strings. Their prominence in various areas of computer science is due to the fact that they are mathematically easy, and that they cover many practically applied dictionary-based compression schemes (e. g., run-length encoding and the Lempel-Ziv-family LZ77, LZ78, LZW, etc.). A comprehensive introduction to SLPs is beyond the scope of this overview (we refer to the survey [START_REF] Lohrey | Algorithmics on SLP-compressed strings: A survey[END_REF] and the papers [START_REF] Kieffer | Grammar-based codes: A new class of universal lossless source codes[END_REF][START_REF] Lohrey | The Compressed Word Problem for Groups[END_REF][START_REF] Nevill-Manning | Identifying Hierarchical Structure in Sequences: A linear-time algorithm[END_REF][START_REF] Nevill-Manning | Inferring Sequential Structure[END_REF][START_REF] Rytter | Application of Lempel-Ziv factorization to the approximation of grammar-based compression[END_REF][START_REF] Schmid | Spanner Evaluation over SLP-Compressed Documents[END_REF][START_REF] Storer | Data compression via textual substitution[END_REF]). In the best case, SLPs can be exponentially smaller than the strings they represent, and since redundancies in texts are likely in practical scenarios, good compressibility is to be expected in most cases. Moreover, many fast (i. e., linear or near linear time) practical algorithms for computing SLPs exist.

The papers [START_REF] Schmid | Spanner Evaluation over SLP-Compressed Documents[END_REF][START_REF] Schmid | Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing[END_REF] are devoted to the question of how regular document spanners can be evaluated directly over SLP-represented document databases. Let us explain the setting in a bit more detail. Our documents are stored in a document database DDB = {D 1 , D 2 , . . . , D 𝑚 } that is represented by an SLP S, i. e., for every 𝑖 with 1 ⩽ 𝑖 ⩽ 𝑚 there is a node 𝐴 𝑖 in S with 𝔇(𝐴 𝑖 ) = D 𝑖 (again, see Figure 1 for an example of an SLP-represented document database that stores three documents). For a given regular spanner represented by an automaton 𝑀 and some given 𝑖 with 1 ⩽ 𝑖 ⩽ 𝑚, we wish to evaluate 𝑀 on the document D 𝑖 . The crucial point is that we want to evaluate 𝑀 on D 𝑖 without explicitly constructing (i. e., decompressing) D 𝑖 , which, after all, is stored in our document database (only) in a compressed form. 2 Since the SLP-compressed representation of the document might be exponentially smaller than the actual document, any algorithm that runs polynomially in the compressed size is, in the best case, only polylogarithmic in the actual document's size. This means that even an algorithm that is linear in the size of the document may be outperformed by an algorithm that is polynomial in the compressed size. For document spanners, this is witnessed by the main result of [START_REF] Schmid | Spanner Evaluation over SLP-Compressed Documents[END_REF]: Given a document database DDB = {D 1 , . . . , D 𝑚 } represented by an SLP S, an 𝑖 ∈ [𝑚] and a regular spanner 𝑀, after a linear preprocessing in O(|S|) (in data complexity), 3 we can enumerate 𝑀 (D 𝑖 ) with delay O(log |D 𝑖 |) (in data complexity). Let us discuss this result in a bit more detail (we discuss some technical aspects in Section 4.2).

First, observe that the preprocessing time O(|S|) depends on the compressibility of D 𝑖 , i. e., in the best case, we have |S| = O(log |D 𝑖 |), and in the worst case, we have |S| = Ω(|D 𝑖 |). In contrast to this, the delay is logarithmic in |D 𝑖 | independently of the compressibility achieved by S. This is obviously incomparable to the uncompressed setting, where one can achieve constant delay after 𝑂 (|D 𝑖 |) preprocessing (cf. the results discussed in Section 2.5). There are nevertheless practical scenarios, where the compressed setting seems particularly useful. The compressed setting assumes that we get our documents already in an SLP-compressed form. This assumption is actually not a strong restriction, since there are many practical algorithms that compute SLPs for strings, and that both in terms of running time and achieved compressibility are -although not optimal4 -rather efficient. 5 In the best case where the SLP is logarithmic in |D 𝑖 |, spanner evaluation can be done logarithmically in the data size (i. e., sublinear in data complexity).

The paper [START_REF] Schmid | Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing[END_REF] is devoted to the dynamic setting of spanner evaluation for SLP-represented document databases. The dynamic setting deals with the situation where the database is subject to update operations, and we wish to evaluate queries over the updated database without re-running the preprocessing from scratch. I. e., instead of treating the evaluation of the same query over a slightly changed database as a completely new evaluation problem, we want to profit from the fact that we have already done the preprocessing with respect to the query and the original database. For classical relational database systems, this scenario is completely natural: the system builds data structures that allow to efficiently compute the query result and maintains these data structures when the database is updated. The particular setting introduced in [START_REF] Schmid | Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing[END_REF] is as follows.

We have available an SLP S that stores a document database DDB = {D 1 , D 2 , . . . , D 𝑚 }. Based on the results of [START_REF] Schmid | Spanner Evaluation over SLP-Compressed Documents[END_REF], we have several data structures at hand that allow the enumeration of the results of each of the spanners 𝑀 1 , 𝑀 2 , . . . , 𝑀 𝑘 on any document D 𝑖 in DDB with delay O(log |D 𝑖 |). We then want to manipulate the existing documents of DDB by a sequence of text-editing operations and evaluate the spanners 𝑀 1 , . . . , 𝑀 𝑘 on the resulting document. For example, we may cut the subword from position 5 to 21 from document D 7 , insert it at position 12 into document D 3 , append this document to D 1 , and insert the resulting document into our document database -and we want to do this in such a way that each of the spanners 𝑀 1 , . . . , 𝑀 𝑘 can be evaluated efficiently also on this new document. The way we build the new document is called complex document editing and can be described by an expression 𝜑 of a suitable algebra. In [START_REF] Schmid | Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing[END_REF] it is shown that if S is strongly balanced (to be explained in more detail in Section 4.1), then we can construct the document D 𝜑 described by 𝜑 and add it to the SLP representing DDB, update all data structures needed for enumerating the spanners 𝑀 1 , . . . , 𝑀 𝑘 , and maintain the balancedness property of the SLP -and all this can be done in time O(𝑘•|𝜑 |•(|𝜑 | + log L)), where L := max{|D 𝑖 | : 1 ⩽ 𝑖 ⩽ 𝑚}. In other words, we can perform rather complex updates with only logarithmic dependency on the lengh of the actual documents, and -a rather important aspect -this is generally the case, independently from the SLP-compressibility of the documents.

The remainder of this section is devoted to some technical aspects of spanner evaluation on SLP-represented document databases. Section 4.1 discusses balancedness properties of SLPs, while Sections 4.2 and 4.3 focus on spanner evaluation in the static setting and the dynamic setting, respectively.

Balanced Straight-Line Programs

The results of [START_REF] Schmid | Spanner Evaluation over SLP-Compressed Documents[END_REF][START_REF] Schmid | Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing[END_REF] hinge on balancing properties of SLPs, which we shall now briefly describe. The order of a node 𝐴 (denoted by ord(𝐴)) of an SLP is 𝑘 +1, where 𝑘 is the longest path from 𝐴 to a leaf (i. e., leafs have order 1). In particular, ord(𝐴) denotes the number of iterative applications of the derivation function 𝔇(•) that are necessary in order to obtain the string over Σ represented by 𝐴 (see ( 4) and ( 5)). We say that node 𝐴 is 𝑐-shallow for some positive integer 𝑐 if ord(𝐴) ⩽ 𝑐• log |𝔇(𝐴)|. If 𝐴 has left child 𝐵 and right child 𝐶, then we define bal(𝐴) = ord(𝐵) -ord(𝐶), and we say that 𝐴 is balanced if bal(𝐴) ∈ {-1, 0, 1}; and 𝐴 is strongly balanced if 𝐴 and all its descendants are balanced. We call an SLP S strongly balanced, (𝑐-shallow, resp.) if all its inner nodes are strongly balanced (𝑐-shallow, resp.). Obviously, 𝑐-shallowness as well as strongly balancedness can be viewed as natural properties of balancedness. Moreover, strongly balancedness corresponds to the balancing property that is also used for balanced search trees, e. g., AVL-trees. See [START_REF] Ganardi | Compression by Contracting Straight-Line Programs[END_REF][START_REF] Ganardi | Balancing Straight-line Programs[END_REF][START_REF] Rytter | Application of Lempel-Ziv factorization to the approximation of grammar-based compression[END_REF] for more details on SLP-balancing.

Let us again consider the example of Figure 1. The orders of S's nodes are as follows: ord(𝐹 ) = ord(𝐸) = 2, ord(𝐶) = 3, ord(𝐵) = 4, ord(𝐷) = ord(𝐴 3 ) = 5, ord(𝐴 1 ) = ord(𝐴 2 ) = 6. In particular, all nodes are balanced except for 𝐴 1 , 𝐴 2 , 𝐴 3 , since bal(𝐴 1 ) = 2 and bal(𝐴 2 ) = bal(𝐴 3 ) = -2.

We can observe the following important fact about strongly balanced nodes: Every directed path from a strongly balanced node 𝐴 to some leaf has length at least 1 2 log |𝔇(𝐴)| and at most 2 log |𝔇(𝐴)|. Furthermore, log |𝔇(𝐴)| ⩽ ord(𝐴)-1 ⩽ 2• log |𝔇(𝐴)|. In particular, this means that any strongly balanced SLP is also 2-shallow.

The main result of [START_REF] Schmid | Spanner Evaluation over SLP-Compressed Documents[END_REF] crucially builds upon the balancing theorem of [START_REF] Ganardi | Balancing Straight-line Programs[END_REF] stating that there is a constant 𝑐 such that any given SLP S with a root 𝐴 can be transformed in time 𝑂 (|S|)into a 𝑐-shallow SLP S ′ with a root 𝐴 ′ such that |S ′ | = 𝑂 (|S|) and 𝔇(𝐴 ′ ) = 𝔇(𝐴). This means that when dealing with SLPs, we may assume that the given SLPs are 𝑐-shallow (since we can always ensure this property in linear time in a preprocessing step). Moreover, while we cannot assume that all documents are highly compressible by SLPs, we can always ensure 𝑐-shallowness, independently of compressibility issues.

For the more restrictive property of being strongly balanced, the situation is slightly different: From [START_REF] Rytter | Application of Lempel-Ziv factorization to the approximation of grammar-based compression[END_REF] we know that any given SLP S with a root 𝐴 can be transformed into a strongly balanced SLP S ′ with a root 𝐴 ′ such that 𝔇(𝐴 ′ ) = 𝔇(𝐴), but this construction takes time O(|S|•ord(𝐴)). Since we may assume that S is c-shallow, we can assume that this run-time, as well as |S ′ |, are in O(|S|• log |𝔇(𝐴)|); and from [START_REF] Ganardi | Compression by Contracting Straight-Line Programs[END_REF] it is known that the factor log |𝔇(𝐴)| cannot be avoided.

Enumeration in the Compressed Setting

Intuitively speaking, the compression of an SLP is done by representing several occurrences of the same factor of a document by just a single node. Referring to Figure 1, 𝔇(𝐴 1 ) = 𝔇(𝐸)𝔇(𝐸)𝔇(𝐶)𝔇(𝐶) = ababbcabca .

Thus, the two occurrences of factor ab are represented by the same node 𝐸, and the two occurrences of factor bca are represented by the same node 𝐶. However, the span-tuples to be extracted may treat different occurrences of the same factor compressed by the same node in different ways. For example, a spanner may extract the span-tuple that corresponds to ababb ⊲

x cabc ⊳ x a. This messes up the compression, since the two occurrences of 𝔇(𝐶) = bca have now become two different factors: b ⊲ x ca and bc⊳ x a. So it seems that extracting a span-tuple enforces at least a partial decompression of S, because different occurrences of the same factor need to be treated differently.

The technical challenge that we face also becomes clear by a comparison to the approach of [START_REF] Amarilli | Constant-Delay Enumeration for Nondeterministic Document Spanners[END_REF] for spanner evaluation in the uncompressed case. This approach first computes in the preprocessing one data structure that represents the whole solution set (i. e., the product graph of spanner and document), and then the enumeration is done by systematically searching this data structure (with the help of additional, pre-computed information). Since each position of the document might be the start or end position of some extracted span, it is difficult to imagine such a data structure that is not at least as large as the whole document. In any case, such a datastructure cannot explicitly contain each position of the represented document, and therefore must still respect the compression.

Let us take a look at the (classical and well-investigated) task of checking whether an SLP-compressed string is accepted by a given NFA (note that algorithms for evaluating regular spanners over SLP-compressed documents will necessarily also implicitly solve this task in some way). Let 𝑆 be some node of an SLP S (over Σ), let 𝑀 be an NFA over Σ with states {𝑠 1 , 𝑠 2 , . . . , 𝑠 𝑛 }. We want to check whether 𝔇(𝑆) ∈ 𝐿(𝑀). The general idea is to compute, for each node 𝐴 that is reachable from 𝑆, a Boolean (𝑛 × 𝑛) matrix 𝑀 𝐴 whose entries indicate from which state we can reach which state by reading the string 𝔇(𝐴). This can be done recursively bottom-up along the DAG rooted by 𝑆: the matrices 𝑀 𝑇 𝑥 for the leaf non-terminals are directly given by 𝑀's transition function, and for every node 𝐴 with left and right children 𝐵 and 𝐶, we have 𝑀 𝐴 = 𝑀 𝐵 • 𝑀 𝐶 , where • denotes the Boolean matrix multiplication. This means that we can in fact check 𝔇(𝑆) ∈ 𝐿(𝑀) in time O(|S|𝑛 3 ) (this observation is well-known; see, e. g., [START_REF] Lohrey | Algorithmics on SLP-compressed strings: A survey[END_REF][START_REF] Markey | A PTIME-complete matching problem for SLP-compressed words[END_REF][START_REF] Plandowski | Complexity of Language Recognition Problems for Compressed Words[END_REF])).

In principle, the enumeration algorithm of [START_REF] Schmid | Spanner Evaluation over SLP-Compressed Documents[END_REF] extends the idea sketched above, but in a non-trivial way. It uses suitable variants and extensions of the matrices 𝑀 𝐴 . In the enumeration phase it considers trees that represent partially decompressed versions of the SLP. The logarithmic delay bound is ensured by transforming (in the preprocessing phase) the SLP into a 𝑐-shallow SLP (cf. Section 4.1).

Complex Document Editing

We can update an SLP-represented document database DDB by directly adding new nodes (with left and right arcs) to the SLP. As an example, consider the grey part of Figure 1: by adding the new nodes 𝐴 4 , 𝐴 5 and 𝐺 in the way described in Figure 1, we add to DDB a document D 4 = D 2 • D 1 represented by 𝐴 4 , and a document D 5 = 𝔇(𝐵)𝔇(𝐺) = 𝔇(𝐵)𝔇(𝐷)𝔇(𝐵) = abbcabcaabbcaabbca , represented by 𝐴 5 . Similarly, we can add any document that is defined as concatenation of documents that are already represented by individual nodes of the SLP. Furthermore, the information computed in the preprocessing of the enumeration algorithm (see Section 4.2) can be easily updated.

The situation becomes more difficult if we want to do more complicated updates, such as "construct the document obtained by inserting the subword from position 5 to 21 of document D 7 at position 12 into document D 3 and appending this document to D 1 ", and if we want to maintain some kind of balancing property. The latter will be important not only for ensuring a logarithmic delay in the enumeration of spanners, but also for performing updates in logarithmic time.

The types of updates considered in [START_REF] Schmid | Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing[END_REF] are expressions over the following basic operations (note that the latter three can be described by suitable combinations of the former two): A CDE-expression 𝜑 over a document database DDB = {D 1 , . . . , D 𝑚 } is obtained by nested application of the basic CDE-algebra operations described above. By eval(𝜑) we denote the document described by 𝜑. The update task can now be formalised as follows. We have a document database DDB represented by an SLP S, we receive a CDE-expression 𝜑, and we want to modify S in such a way that it describes DDB ∪{eval(𝜑)}. As illustrated by Figure 1, this can be done easily in the special case that 𝜑 only contains operation concat. The approach for arbitrary CDE-expressions is as follows.

We assume that the SLP that represents DDB is strongly balanced (see Section 4.1).

Let us consider the operation concat(𝔇(𝐵), 𝔇(𝐶)), where 𝐵 and 𝐶 are some nodes of the SLP. If we just naively add a new node 𝐴 with left and right children 𝐵 and 𝐶, then it represents concat(𝔇(𝐵), 𝔇(𝐶)). However, if ord(𝐵) ⩾ ord(𝐶) + 2, then 𝐴 is unbalanced. This case has been handled in [START_REF] Rytter | Application of Lempel-Ziv factorization to the approximation of grammar-based compression[END_REF] by first identifying in the part of the SLP that is rooted by 𝐵 a suitable position where 𝐶 can be inserted in such a way that we only obtain nodes that are unbalanced by at most 2 or -2; such mildly unbalanced nodes can then be re-balanced by performing suitable rotations (these are rotations that are similar to the classical rotations that are used for rebalancing AVL-trees). An analogous (but substantially more involved) construction (desribed in [START_REF] Schmid | Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing[END_REF]) also works for the operation extract(𝔇(𝐴), 𝑖, 𝑗). The crucial point is that for these constructions, we only have to move (and manipulate) nodes

  x , ⊳ x : x ∈ X}: We explicitly represent each span 𝑡 (x) in D with the markers ⊲ x and ⊳ x . As an example, for X = {x, y, z}, consider the document D = abcacacbbaa and the (X, D)-tuple 𝑡 with 𝑡 (x) = [2, 6⟩, 𝑡 (y) = [4, 8⟩, 𝑡 (z) = [1, 8⟩, which can be represented by the string

Z 1 .

 1 . . 𝜍 = Z 𝑘 (𝑆), such that 𝑆 is a regular spanner and 𝜍 = Z 1 , . . . , 𝜍 = Z 𝑘 are non-overlapping with respect to 𝑆, we can construct a refl-spanner 𝑆 ′ such that

Figure 1 :

 1 Figure 1: Graphical representation of an SLP (solid arcs). Left and right children are indicated by labels 𝑙 and 𝑟 , respectively. The grey parts illustrate the extensions discussed in Section 4.3. This figure is taken from [40].

  concat(D, D ′ ): Concatenate D and D ′ . extract(D, 𝑖, 𝑗): Extract the factor from position 𝑖 to 𝑗 from D. delete(D, 𝑖, 𝑗): Delete the factor from position 𝑖 to 𝑗 from D. insert(D, D ′ , 𝑘): Insert D ′ at position 𝑘 of D. copy(D, 𝑖, 𝑗, 𝑘): Considering D, copy the factor from position 𝑖 to 𝑗 and paste it at position 𝑘.

Such a task is also called algorithmics on compressed strings in the literature.

We shall only discuss data complexity here; for upper bounds in combined complexity, we refer to the original papers.

Note that the problem of computing a smallest SLP for a string is NP-complete (see[START_REF] Casel | On the Complexity of the Smallest Grammar Problem over Fixed Alphabets[END_REF][START_REF] Charikar | The smallest grammar problem[END_REF]).

In fact, the literature on algorithmics on compressed strings suggest that most basic string analysis tasks can be performed directly on SLPs. Thus, whenever we are dealing with textual data, it is even a likely scenario that strings are generally represented by SLPs, simply because we have the algorithmic machinery for working directly on SLPs.

ACKNOWLEDGMENTS

The first author is supported by the German Research Foundation -project number 416776735 (gefördert durch die Deutsche Forschungsgemeinschaft (DFG) -Projektnummer 416776735). The second author is partially supported by the ANR project EQUUS ANR-19-CE48-0019; funded by the German Research Foundation -project number 431183758 (gefördert durch die Deutsche Forschungsgemeinschaft (DFG) -Projektnummer 431183758).

for a constant number of times along a path starting in 𝐴. Since the original SLP is strongly balanced, this implies that the overall running time is bounded by O(ord(𝐴)) = O(log |𝔇(𝐴)|).

Given a CDE-expression 𝜑, we can add eval(𝜑) to the SLP representing the document database by applying these constructions inductively, i. e., bottom-up to the syntax tree of 𝜑. This yields the following main result from [START_REF] Schmid | Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing[END_REF]: Let DDB be a document database that is represented by a strongly balanced SLP S. When given a CDEexpression 𝜑 over DDB, we can turn S into a strongly balanced SLP that represents DDB ∪{eval(𝜑)}. Moreover, this construction is carried out in time O(|𝜑 |• log d), where d is the maximum length of any document of DDB that occurs at a leaf of 𝜑's syntax tree, any intermediate document that is represented by a subexpression of 𝜑, and the finally resulting document eval(𝜑).

Within the running time of performing a CDE-update, we can also update the data structures that are necessary to perform the enumeration phase of the algorithm sketched in Section 4.2. . This implies that if we have computed these data structures for spanners 𝑀 1 , 𝑀 2 , . . . , 𝑀 𝑘 (represented by NFA 𝑀 𝑖 ), then, for every 𝑖 ∈ [𝑘] and CDE-expression 𝜑, we can always enumerate 𝑀 𝑖 (eval(𝜑)) by first updating DDB according to 𝜑 and then running the enumeration algorithm. Both the required update as well as the delay is only logarithmic in the data size.

If, for some CDE-expression 𝜑, the actual document eval(𝜑) is to be queried just once without the necessity of permanently storing it in the document database, then we can just remove all the new nodes after having queried it, i. e., this can be done within the time required for constructing the node that represents eval(𝜑).

In comparison to the enumeration algorithm sketched in Section 4.2, the mentioned results on CDE-updates require the SLP to be strongly balanced instead of only 𝑐-shallow. As discussed in Section 4.1, the strongly balancedness property is stronger than 𝑐-shallowness, and it cannot be ensured in linear time.

Let us conclude with a discussion on how to build, from scratch and with acceptable running time, an SLP-representation for a document database. Let DDB = {D 1 , D 2 , . . . , D 𝑚 }. If the documents D 𝑖 are given as SLPs S 𝑖 , then we can make each of those strongly balanced in time O(|S 𝑖 | log |D 𝑖 |) (see Section 4.1), and then we can just combine all these SLPs in order to get an SLP for DDB. In this regard, it is also worth noting that many practical compression schemes can be transformed directly into SLPs with moderate size blow-ups (see [START_REF] Goto | Restructuring Compressed Texts without Explicit Decompression[END_REF]). If, on the other hand, the documents are given in an uncompressed form, then we first have to compress them by running one of the many SLP-compression algorithms. In this setting, in order to achieve a better overall compression rate, it can also make sense to construct an SLP for the single document D 1 D 2 • • • D 𝑚 , which can then be made strongly balanced, and then transformed into an SLP that contains a node for each D 𝑖 (this latter step can be done by CDE-operations).