# A framework for extraction and transformation of documents

Cristian Riveros  Pontificia Universidad Católica de Chile,
<EMAIL_ADDRESS>Markus L. Schmid  Humboldt-Universität zu Berlin,
Germany<EMAIL_ADDRESS><EMAIL_ADDRESS>Nicole
Schweikardt  Humboldt-Universität zu Berlin, Germany<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We present a theoretical framework for the extraction and transformation of
text documents. We propose to use a two-phase process where the first phase
extracts span-tuples from a document, and the second phase maps the content of
the span-tuples into new documents. We base the extraction phase on the
framework of document spanners and the transformation phase on the theory of
polyregular functions, the class of regular string-to-string functions with
polynomial growth.

For supporting practical extract-transform scenarios, we propose an extension
of document spanners described by regex formulas from span-tuples to so-called
multispan-tuples, where variables are mapped to sets of spans. We prove that
this extension, called regex multispanners, has the same desirable properties
as standard spanners described by regex formulas. In our framework, an
Extract-Transform (ET) program is given by a regex multispanner followed by a
polyregular function.

In this paper, we study the expressibility and evaluation problem of ET
programs when the transformation function is linear, called linear ET
programs. We show that linear ET programs are equally expressive as non-
deterministic streaming string transducers under bag semantics. Moreover, we
show that linear ET programs are closed under composition. Finally, we present
an enumeration algorithm for evaluating every linear ET program over a
document with linear time preprocessing and constant delay.

##  1 Introduction

Information extraction (IE) of text documents found its theoretical
foundations in the framework of document spanners [22]. Introduced by Fagin,
Kimelfeld, Reiss, and Vansummeren one decade ago [21], this framework sets the
grounds for rule-based IE through the notion of spanners and how to combine
them by using relational operators. Moreover, it inspired a lot of research on
languages [25, 35], expressiveness [24, 31, 37, 15, 39], evaluation [23, 8,
16, 13, 26, 36, 28], provenance [17, 14], and compressed evaluation [40, 42,
33] for IE. Initially conceived to understand SystemT, IBM’s rule-based IE
system, it has found some recent promising implementations in [38]. See [41,
7] for surveys of the area.

Although IE is a crucial task for data management, document extraction is
usually followed by a transformation into new documents. Indeed, data
transformation is essential for communicating middleware systems, where data
does not conform to the required format of a third-party system and needs to
be converted. This forms the main task of the so-called ETL technologies [46]
(for Extract-Transform-Load), which are crucial parts of today’s data
management workflows. Even the search-and-replace operation over text, a
ubiquitous task in all text systems, can be conceived as an extraction (i.e.,
search) followed by a transformation (i.e., replace). Hence, although document
spanners provided the formal ground of ruled-based IE, these grounds are
incomplete without understanding the following transformation process.

In this paper, we study the extraction and transformation of text documents
through the lens of document spanners. We propose to use a two-phase process
where the first phase extracts span-tuples from a document, and the second
phase maps the content of the span-tuples into new documents. The main idea
here is to use the framework of document spanners for the extraction phase,
completing it with an transformation phase using the theory of polyregular
functions.

Let us now explain our proposed framework and respective results with several
examples. We consider the following document $\mathbf{D}$ over alphabet
$\Sigma$ that lists famous English-speaking singers in the format $\\#$
[person] $\\#$ [person] $\\#$ …$\\#$ [person] $\\#$ with [person] $=$ [last
name]; [name]; [birthplace]; [opt]; [opt];…, where [opt] are optional
attributes like, e. g., age, nickname, honorary titles etc, which follow no
fixed scheme. This means that ‘$\\#$’ and ‘;’ are used as separators, and for
convenience, we set $\widehat{\Sigma}=\Sigma\setminus\\{;,\\#\\}$.

$\mathbf{D}=$ # Holiday; Billie; USA # Bush; Kate; England # Young; Neil;
Canada; 78; ‘‘Godfather of Grunge’’ # King; Carole; USA; 81 # McCartney; Paul;
England; Sir; CH; MBE # Mitchell; Joni; Canada; painter # Franklin; Aretha;
USA; ‘‘Queen of Soul’’ # O’Riordan; Dolores; Ireland; †01/15/2018 # Bowie;
David; England # Dylan; Bob; USA; 82 # Young; Neil; USA # Gallagher; Rory;
Ireland #

Our general approach is to first perform information extraction on
$\mathbf{D}$ with (an extension of) _regex formulas_ (see [22]). For example,
$E_{1}\ :=\ \
\Sigma^{*}\\#\,\textsf{x}\\{\widehat{\Sigma}^{*}\\};\textsf{y}\\{\widehat{\Sigma}^{*}\\};\Sigma^{*}$
is a regex formula that uses a variable x to extract just any factor over
$\widehat{\Sigma}$ that occurs between separators ‘$\\#$’ and ‘;’, and a
variable y to extract the following factor over $\widehat{\Sigma}$ between the
next two occurrences of ‘;’. The construct $\textsf{x}\\{r\\}$ creates a
_span_ $[i,j\rangle$ pointing to factor
$\mathbf{D}[i]\mathbf{D}[i+1]\ldots\mathbf{D}[j-1]$, satisfying the
subexpression $r$. The regex formula $E_{1}$ specifies a spanner that, on our
example document $\mathbf{D}$ produces the set
$\\{([2,9\rangle,[10,16\rangle),$ $([21,25\rangle,[26,30\rangle),$
$([39,44\rangle,[45,49\rangle),\ldots\\}$ of _span-tuples_. Every span-tuple
$t$ represents an annotated version of our document: the factor corresponding
to $t(\textsf{x})$ is annotated by (or allocated to) x and the factor
corresponding to $t(\textsf{y})$ is annotated by y. And each such annotation
represents another finding of relevant information in our document.

As the second step of our model, we map each annotated version of our document
to another document, which therefore describes a transformation of our
document. This mapping will explicitly use the information represented by the
annotation from the extraction phase. Formally, we use a string-to-string
function for the transformation phase that gets as argument a single string
that represents the document and the information given by a span-tuple. The
transformation function is applied to each of the annotated documents. Since
the transformation function can be non-injective, we may obtain the same
output string several times. In our model, we keep such duplicates (by using
bag semantics), since they represent the situation that the same output string
can be constructed from completely different annotations. Considering our
example, the annotated documents are as follows (we use $\textbar$ as
separator between strings for better readability):

They are obtained by simply representing the span for each variable
$\textsf{z}\in\\{\textsf{x},\textsf{y}\\}$ by a pair of parentheses
$\prescript{}{\textsf{z}}{\textsf{\vdash}}\ldots\textsf{\dashv}_{\textsf{z}}$.
If we couple the spanner $E_{1}$ with the string-to-string function:

$T_{1}\ :=\ \
u\prescript{}{\textsf{x}}{\textsf{\vdash}}v_{\textsf{x}}\textsf{\dashv}_{\textsf{x}};\prescript{}{\textsf{y}}{\textsf{\vdash}}v_{\textsf{y}}\textsf{\dashv}_{\textsf{y}}u^{\prime}\>\>\mapsto\>\>v_{\textsf{y}}\mbox{\kern
0.59998pt\vrule height=1.29167pt}\vbox{\hrule width=3.00003pt}\hbox{\vrule
height=1.29167pt}\,v_{\textsf{x}}\,$

where $u,u^{\prime}\in\Sigma^{*}$ and
$v_{\textsf{x}},v_{\textsf{y}}\in\widehat{\Sigma}^{*}$, then we obtain what we
call an _extract-transform program_ (_ET program_). This ET program
$(E_{1},T_{1})$ maps our document $\mathbf{D}$ to the following collection of
strings:

Note that these are the names of all singers from the document, but in the
format “[first name] [last name]” (i. e., the order of the names is swapped).
Moreover, “Neil Young” constitutes a duplicate, since it is the image under
_different_ extractions of the regex formula $E_{1}$. This is an intended
feature of our model, since every distinct way of information extraction
should translate into a distinct output document of the transformation phase.

This example already points out that classical _one-way transducers_ [10] are
not suitable transformation functions, since they cannot change the order of
the extracted factors. We propose, instead, to use the class of _polyregular
functions_ [12, 20], which is a robust class of regular string-to-string
functions with (at most) polynomial growth. The function from above is a
polyregular function that even has linear growth; a subclass of special
interest for this work. We will discuss polyregular functions (and
representations for them) later in this paper. In the examples here, we
describe them sufficiently formally but on an intuitive level.

Let us move on to a more complicated example. We want to define an ET program
which maps $\mathbf{D}$ to the following strings:

Specifically, we want to map each singer entry [last name]; [name];
[birthplace]; [opt-1]; …; [opt-k] to the string [name] [last name]:
[birthplace] # [name] [last name]: [opt-1] # …# [name] [last name]: [opt-k] #,
which is something like the cross-product between [name] [last name] and the
list [birthplace], [opt-1], …, [opt-k]. For example, the substring # Young;
Neil; Canada; 78; ‘‘Godfather of Grunge’’ # is mapped to Neil Young: Canada #
Neil Young: 78 # Neil Young: ‘‘Godfather of Crunge’’ #.

Intuitively, we would have to extract each element of the unbounded list
[birthplace], [opt-1], …, [opt-k] in its own variable, which goes beyond the
capability of document spanners. As a remedy, in this paper we propose to
extend the classical spanner framework to _multispanners_ , which can extract
in each variable a _set of spans_ instead of only a single span. Now assume
that we apply to the document the expression:

$E_{2}\ :=\ \
\Sigma^{*}\\#\,\textsf{x}\\{\widehat{\Sigma}^{*}\\};\textsf{y}\\{\widehat{\Sigma}^{*}\\};\textsf{z}\\{\widehat{\Sigma}^{*}\\}(;\textsf{z}\\{\widehat{\Sigma}^{*}\\})^{*}\,\\#\,\Sigma^{*}\,.$

Then for the substring #Young; Neil; Canada; 78; ‘‘Godfather of Grunge’’#, we
will extract _each_ attribute as a single span of variable z, so the
corresponding _multispan_ tuple and the corresponding string representation
would be:

Thus, by defining a suitable transformation function $T_{2}$, we get an ET
program $(E_{2},T_{2})$ for our task. This is again possible by a polyregular
function, but not with linear growth.

These examples show that typical string transduction tasks can often be
naturally divided into the job of locating the relevant parts of our input,
followed by their manipulation (e. g., reordering, deleting, copying, etc.),
and our framework is particularly tailored to this situation. Moreover, we can
easily construct new ET programs by combining specifications for an extract
task (i. e., a multispanner) with specifications for a transform task (a
string-to-string function) of existing ET programs. For example, the same
spanner that finds relevant text blocks, like names, email addresses, URLs,
etc. can be combined with different string-to-string functions that pick and
arrange some of these text blocks in a certain format. Or, for cleaning
textual data, we use a string-to-string function that deletes all the
annotated factors, and we combine this with different spanners for finding the
factors to be deleted.

As also pointed out by our examples, it is a desired feature that the output
of an ET program can contain duplicates. Let us motivate this by a more
practical example. Assume that the extraction phase marks the addresses in a
list of customer orders, while the transformation phase then transforms these
addresses into a format suitable for printing on the parcels to be shipped to
the customers. In the likely situation that there are different orders by the
same person, the extraction phase produces different markings that will all be
transformed into the same address label. Such duplicates, however, are
important, since we actually want to obtain an address label for each distinct
order (i. e., distinct marking), even if these addresses are the same
(although the orders are not). This means that the output sets of our ET
programs should actually be bags.

Our main conceptual contribution is a sound formalisation of our ET framework,
which includes the extension of the classical spanner framework to
multispanners (which we believe are interesting in their own right). Our main
algorithmic result is about _linear ET programs_ , i. e., the subclass where
the multispanner of the extraction can be described by a regular expression
(similar to the ones used above) and the transformation function is a
polyregular function with linear growth (e.g., the program $(E_{1},T_{1})$).
We show that we can enumerate the output documents of linear ET programs with
linear preprocessing and output-linear delay (in data complexity).
Furthermore, we show that ET programs are closed under composition. This
implies that we can enumerate the output of a composition of programs
efficiently. As an important tool for our enumeration algorithm, we show that
linear ET programs have the same expressive power as nondeterministic
streaming string transducers (NSST). This also gives an important insight with
respect to the expressive power of linear ET programs.

Specifically, the contributions are as follows.

  * •

We introduce the formalism of multispanners, for extracting an unbounded
number of spans in a single tuple (Section 2).

  * •

By combining multispanners and polyregular functions, we introduce ET programs
as a framework for extraction and transformation of documents (Section 3).

  * •

We restrict our analysis to the linear case, and show that linear ET programs
are equally expressive as NSSTs under bag-semantics (Section 4).

  * •

We present an enumeration algorithm for evaluating linear ET programs with
linear-time preprocessing and output-linear delay (Section 5).

  * •

We show that linear ET programs are closed under composition and, therefore,
we can evaluate the composition of linear ET programs efficiently (Section 6).

We conclude in Section 7 with some remarks on future work. Further details are
provided in an appendix.

#### Further related work

To the best of our knowledge, this is the first work on extending document
spanners with transformation.

String transductions [10, 34, 12] – a classical model in computer science –
have recently gained renewed attention with the theory of polyregular
functions [2]. Although we can see an ET program as a single transduction
(cf., Section 4 and the equivalence with NSSTs), this work has several novel
contributions compared to classical string transductions. Firstly, our
framework models the process by two declarative phases (which is natural from
a data management perspective), contrary to string transductions that model
the task as a single process. Secondly, our work uses bag semantics, which
requires revisiting some results on transduction (see Section 6). Moreover,
efficient enumeration algorithms for (non-deterministic) linear polyregular
functions have not been studied before.

There are systems for transforming documents into documents (e.g., [29]). For
example, they used a combination of regular expressions with replace operators
[30] or parsing followed by a transduction over the parsing tree [29]. Indeed,
in practice, regular expressions support some special commands for
transforming data (also called substitutions). Our study has a theoretical
emphasis on information extraction and transformation, starting from the
framework of document spanners. To our knowledge, previous systems neither use
the expressive power of document spanners nor polyregular functions.

##  2 Multispanners

Let us first give some standard notations. By $\powerset(A)$ we denote the
power set of a set $A$. Let $\mathbb{N}=\\{1,2,3,\ldots\\}$ and
$[n]=\\{1,2,\ldots,n\\}$ for $n\in\mathbb{N}$. For a finite alphabet $A$, let
$A^{+}$ denote the set of non-empty words over $A$, and
$A^{*}=A^{+}\cup\\{\textsf{\varepsilon}\\}$, where $\textsf{\varepsilon}$ is
the empty word. For a word $w\in A^{*}$, $|w|$ denotes its length (in
particular, $|\textsf{\varepsilon}|=0$). A word $v\in A^{+}$ is a _factor_ (or
_subword_) of $w$ if there are $u_{1},u_{2}\in A^{*}$ with $w=u_{1}vu_{2}$;
$v$ is a _prefix_ or _suffix_ of $w$, if $u_{1}=\textsf{\varepsilon}$ or
$u_{2}=\textsf{\varepsilon}$, respectively. For every $i\in[|w|]$, let $w[i]$
denote the symbol at position $i$ of $w$. We use DFAs and NFAs (deterministic
and nondeterministic finite automata, resp.) as commonly defined.

#### Multispans and multispanners

For a document $\mathbf{D}\in\Sigma^{*}$ and for every
$i,j\in[|\mathbf{D}|{+}1]$ with $i\leq j$, $[i,j\rangle$ is a _span of
$\mathbf{D}$_ and its _value_ , denoted by $\mathbf{D}[i,j\rangle$, is the
substring of $\mathbf{D}$ from symbol $i$ to symbol $j{-}1$. In particular,
$\mathbf{D}[i,i\rangle=\textsf{\varepsilon}$ (called an _empty span_) and
$\mathbf{D}[1,|\mathbf{D}|{+}1\rangle=\mathbf{D}$. By
$\textsf{{Spans}}(\mathbf{D})$, we denote the set of spans of $\mathbf{D}$,
and by $\textsf{{Spans}}$ we denote the set of all spans $\\{[i,j\rangle\mid
i,j\in\mathbb{N},\ i\leq j\\}$. Two spans $[i,j\rangle$ and
$[i^{\prime},j^{\prime}\rangle$ are _disjoint_ if $j\leq i^{\prime}$ or
$j^{\prime}\leq i$. A _multispan_ is a (possibly empty) set of pairwise
disjoint spans.

Let $\mathcal{X}$ be a finite set of variables. A _span-tuple_ (over a
document $\mathbf{D}$ and variables $\mathcal{X}$) [22] is a function
$t\colon\mbox{$\mathcal{X}$}\to\textsf{{Spans}}(\mathbf{D})$. We define a
_multispan-tuple_ as a function
$t\colon\mbox{$\mathcal{X}$}\to\powerset(\textsf{{Spans}}(\mathbf{D}))$ such
that, for every $\textsf{x}\in\mbox{$\mathcal{X}$}$, $t(\textsf{x})$ is a
multispan. Note that every span-tuple $t$ can be considered as a special case
of a multispan-tuple where $t(x)=\\{[i,j\rangle\\}$. For simplicity, we
usually denote multispan-tuples in tuple-notation, for which we assume an
order $<$ on $\mathcal{X}$. For example, if
$\mbox{$\mathcal{X}$}=\\{\textsf{x}_{1},\textsf{x}_{2},\textsf{x}_{3}\\}$ with
$\textsf{x}_{1}<\textsf{x}_{2}<\textsf{x}_{3}$, then multispan
$t=(\,\\{[1,6\rangle\\},\,\emptyset,\,\\{[2,3\rangle,[5,7\rangle\\}\,)$ maps
$\textsf{x}_{1}$ to $\\{[1,6\rangle\\}$, $\textsf{x}_{2}$ to $\emptyset$ and
$\textsf{x}_{3}$ to $\\{[2,3\rangle,[5,7\rangle\\}$. Note that $[2,3\rangle$
and $[5,7\rangle$ are disjoint, while $[1,6\rangle$ and $[5,7\rangle$ are not,
which is allowed, since they are spans of different multispans.

A _multispan-relation_ (over a document $\mathbf{D}$ and variables
$\mathcal{X}$) is a possibly empty set of multispan-tuples over $\mathbf{D}$
and $\mathcal{X}$. Given a finite alphabet $\Sigma$, a _multispanner_ (over
$\Sigma$ and $\mathcal{X}$) is a function that maps every document
$\mathbf{D}\in\Sigma^{*}$ to a multispan-relation over $\mathbf{D}$ and
$\mathcal{X}$. Note that the empty relation $\emptyset$ is also a valid image
of a multispanner.

######  Example 2.1.

Let $S$ be a multispanner over alphabet $\\{\mathtt{a},\mathtt{b}\\}$ and
variables $\\{\textsf{x},\textsf{y}\\}$ that maps every document
$\mathbf{D}\in\\{\mathtt{a},\mathtt{b}\\}^{*}$ to the set of all multispan-
tuples $t$ such that $t(\textsf{x})=\\{[i,j\rangle\\}$ where
$\mathbf{D}[i,j\rangle$ is a factor that starts and ends with $\mathtt{b}$,
and is not directly preceded or followed by another $\mathtt{b}$, and
$t(\textsf{y})$ is the multispan that contains a span for each maximal unary
(i.e., of the form $\mathtt{a}^{+}$ or $\mathtt{b}^{+}$) factor of
$\mathbf{D}[i,j\rangle$. For example, $t\in
S(\mathtt{a}\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{b}\mathtt{b}\mathtt{b}\mathtt{a}\mathtt{a}\mathtt{b})$
with:

$t(\textsf{x})=\\{[3,11\rangle\\}\text{ and
}t(\textsf{y})=\\{[3,4\rangle,[4,5\rangle,[5,8\rangle,[8,10\rangle,[10,11\rangle\\}\,.$

Similarly to the classical framework of document spanners [22], it is
convenient to represent multispanners over $\Sigma$ and $\mathcal{X}$ by
formal languages over the alphabet
$\Sigma\cup\\{\prescript{}{\textsf{x}}{\textsf{\vdash}},\textsf{\dashv}_{\textsf{x}}\mid\textsf{x}\in\mbox{$\mathcal{X}$}\\}$.
This allows us to represent multispanners by formal language descriptors, e.
g., regular expressions or finite automata.

#### Representing multispans by multiref-words

In this section, we adapt the concept of ref-words (commonly used for
classical document spanners; see [27, 25, 15, 41]) to multispanners.

For any set $\mathcal{X}$ of variables, we shall use the set
$\Gamma_{\mbox{$\mathcal{X}$}}=\\{\prescript{}{\textsf{x}}{\textsf{\vdash}},\textsf{\dashv}_{\textsf{x}}\mid\textsf{x}\in\mbox{$\mathcal{X}$}\\}$
as an alphabet of meta-symbols. In particular, for every
$\textsf{x}\in\mbox{$\mathcal{X}$}$, we interpret the pair of symbols
$\prescript{}{\textsf{x}}{\textsf{\vdash}}$ and $\textsf{\dashv}_{\textsf{x}}$
as a pair of opening and closing parentheses. A _multiref-word_ (_over
terminal alphabet $\Sigma$ and variables $\mathcal{X}$_) is a word
$w\in(\Sigma\cup\Gamma_{\mbox{$\mathcal{X}$}})^{*}$ such that, for every
$\textsf{x}\in\mbox{$\mathcal{X}$}$, the subsequence of the occurrences of
$\prescript{}{\textsf{x}}{\textsf{\vdash}}$ and of
$\textsf{\dashv}_{\textsf{x}}$ is well-balanced and unnested, namely, has the
form
$(\prescript{}{\textsf{x}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}})^{k}$
for some $k\geq 0$.

Intuitively, any multiref-word $w$ over $\Sigma$ and $\mathcal{X}$ uniquely
describes a document $\mathbf{D}_{w}\in\Sigma^{*}$ and a multispan-tuple
$\textsf{t}_{w}$ as follows. First, let $\mathbf{D}_{w}$ be obtained from $w$
by erasing all symbols from $\Gamma_{\mbox{$\mathcal{X}$}}$. We note that, for
every $\textsf{x}\in\mbox{$\mathcal{X}$}$, every matching pair
$\prescript{}{\textsf{x}}{\textsf{\vdash}}$ and $\textsf{\dashv}_{\textsf{x}}$
in $w$ (i. e., every occurrence of $\prescript{}{\textsf{x}}{\textsf{\vdash}}$
and the following occurrence of $\textsf{\dashv}_{\textsf{x}}$) uniquely
describes a span of $\mathbf{D}_{w}$: ignoring all other occurrences of
symbols from $\Gamma_{\mbox{$\mathcal{X}$}}$, this pair encloses a factor of
$\mathbf{D}_{w}$. Consequently, we simply define that, for every
$\textsf{x}\in\mbox{$\mathcal{X}$}$, $\textsf{t}_{w}(\textsf{x})$ contains all
spans defined by matching pairs $\prescript{}{\textsf{x}}{\textsf{\vdash}}$
and $\textsf{\dashv}_{\textsf{x}}$ of $w$. The property that the subsequence
of $w$ of the occurrences $\prescript{}{\textsf{x}}{\textsf{\vdash}}$ and
$\textsf{\dashv}_{\textsf{x}}$ has the form
$(\prescript{}{\textsf{x}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}})^{k}$
for some $k\geq 0$ implies that all spans of $\textsf{t}_{w}(\textsf{x})$ are
pairwise disjoint.

######  Example 2.2.

Let us consider the following multiref-word over the finite alphabet $\Sigma$
and variables $\mbox{$\mathcal{X}$}=\\{\textsf{x},\textsf{y}\\}$: $w\ =\ \
\mathtt{a}\mathtt{a}\prescript{}{\textsf{x}}{\textsf{\vdash}}\prescript{}{\textsf{y}}{\textsf{\vdash}}\mathtt{b}\textsf{\dashv}_{\textsf{y}}\prescript{}{\textsf{y}}{\textsf{\vdash}}\mathtt{a}\textsf{\dashv}_{\textsf{y}}\prescript{}{\textsf{y}}{\textsf{\vdash}}\mathtt{b}\mathtt{b}\mathtt{b}\textsf{\dashv}_{\textsf{y}}\prescript{}{\textsf{y}}{\textsf{\vdash}}\mathtt{a}\mathtt{a}\textsf{\dashv}_{\textsf{y}}\prescript{}{\textsf{y}}{\textsf{\vdash}}\mathtt{b}\textsf{\dashv}_{\textsf{y}}\textsf{\dashv}_{\textsf{x}}$.
By definition, $w$ represents the document
$\mathbf{D}_{w}=\mathtt{a}\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{b}\mathtt{b}\mathtt{b}\mathtt{a}\mathtt{a}\mathtt{b}$
and the multispan-tuple (from Example 2.1):

$\textsf{t}_{w}=(\underbrace{\\{[3,11\rangle\\}}_{\textsf{x}},\underbrace{\\{[3,4\rangle,[4,5\rangle,[5,8\rangle,[8,10\rangle,[10,11\rangle\\}}_{\textsf{y}})$

The advantage of the notion of multiref-words is that it allows to easily
describe both, a document and some multispan-tuple over this document.
Therefore, one can use any set of multiref-words to define a multispanner as
follows. A _multiref-language_ (_over terminal alphabet $\Sigma$ and variables
$\mathcal{X}$_) is a set of multiref-words over $\Sigma$ and $\mathcal{X}$.
Any multiref-language $L$ describes the multispanner ${\lsem{}{L}\rsem}$ over
$\Sigma$ and $\mathcal{X}$ defined as follows. For every
$\mathbf{D}\in\Sigma^{*}$: ${\lsem{}{L}\rsem}(\mathbf{D})\ =\ \
\\{\textsf{t}_{w}\mid w\in L\text{ \ and \ }\mathbf{D}_{w}=\mathbf{D}\\}$.

Analogously to classical spanners (cf. [39, 27, 25, 15, 41]), we define the
class of _regular multispanners_ as those multispanners $S$ with
$S={\lsem{}{L}\rsem}$ for some regular multiref-language $L$. Moreover, as
done in [22] for classical spanners, we will use a class of regular
expressions to define a subclass of regular multispanners that shall play a
central role for our extraction and transformation framework.

#### Regex multispanners

Let $\Sigma$ be a finite alphabet and let $\mathcal{X}$ be a finite set of
variables. We now define _multispanner-expressions_ (_over $\Sigma$ and
$\mathcal{X}$_). Roughly speaking, these expresssions are a particular class
of regular expressions for defining sets of multiref-words and therefore
multispanners. More specifically, a multispanner-expression $R$ (over $\Sigma$
and $\mathcal{X}$) satisfies the syntax:

$\begin{array}[]{rcl}R&:=&\textsf{\varepsilon}\ \mid\ a\in\Sigma\mid\ (R\cdot
R)\ \mid\ (R+R)\ \mid\ R^{*}\mid\ \textsf{x}\\{R\\}\end{array}$

for every $\textsf{x}\in\mbox{$\mathcal{X}$}$ such that x does not appear in
$R$. Such a multispanner-expression $R$ naturally defines a set of multiref-
words $\mathcal{L}(R)$ as follows:
$\mathcal{L}(\textsf{\varepsilon})=\\{\textsf{\varepsilon}\\}$,
$\mathcal{L}(a)=\\{a\\}$, $\mathcal{L}(R\cdot
R^{\prime})=\mathcal{L}(R)\cdot\mathcal{L}(R^{\prime})$,
$\mathcal{L}(R+R^{\prime})=\mathcal{L}(R)\cup\mathcal{L}(R^{\prime})$,
$\mathcal{L}(R^{*})=\mathcal{L}(R)^{*}$, and $\mathcal{L}(\textsf{x}\\{R\\})\
=\ \
\\{\prescript{}{\textsf{x}}{\textsf{\vdash}}\\}\cdot\>\mathcal{L}(R)\cdot\\{\textsf{\dashv}_{\textsf{x}}\\}$,
where, for every $L,L^{\prime}\subseteq\Sigma^{*}$, $L\cdot
L^{\prime}=\\{uv\mid u\in L\wedge v\in L^{\prime}\\}$,
$L^{0}=\\{\textsf{\varepsilon}\\}$, $L^{i}=L\cdot L^{i-1}$ for every $i\geq
1$, and $L^{*}=\bigcup_{i=0}^{\infty}L^{i}$. As usual, we use $R^{+}$ as a
shorthand for $(R\cdot R^{*})$.

One can easily prove (e.g., by induction over the size of the expressions)
that any multispanner-expression defines a multiref-language, since we do not
allow expressions of the form $\textsf{x}\\{R\\}$ whenever $R$ mentions x.
Thus, we can define the _multispanner ${\lsem{}{R}\rsem}$ specified by $R$_ as
${\lsem{}{R}\rsem}={\lsem{}{\mathcal{L}(R)}\rsem}$. Furthermore, we say that a
multispanner $S$ is a _regex multispanner_ if $S={\lsem{}{R}\rsem}$ for some
multispanner-expression $R$.

######  Example 2.3.

$R\ :=\ \
(\textsf{\varepsilon}+\Sigma^{*}\mathtt{a}^{+})\cdot\textsf{x}\big{\\{}(\textsf{y}\\{\mathtt{b}^{+}\\}\cdot\textsf{y}\\{\mathtt{a}^{+}\\})^{*}\cdot\textsf{y}\\{\mathtt{b}^{+}\\}\big{\\}}\cdot(\mathtt{a}^{+}\Sigma^{*}+\textsf{\varepsilon})$
is a multispanner-expression with ${\lsem{}{R}\rsem}$ being the multispanner
$S$ from Example 2.1; thus, $S$ is a regex multispanner.

#### Comparison with classical spanners

Multispanners are designed to naturally extend the classical model of spanners
from [22] to the setting where variables are mapped to sets of spans instead
of single spans. Let us discuss a few particularities of our definitions.

We first note that since classical span-tuples, span-relations and spanners
(in the sense of [22]) can be interpreted as special multispan-tuples,
multispan-relations and multispanners, respectively, our framework properly
extends the classical spanner framework.

A multispan-tuple $t$ allows $[i,j\rangle\in t(\textsf{x})$ and
$[k,l\rangle\in t(\textsf{y})$ with $i\leq k<j\leq l$ and
$\textsf{x}\neq\textsf{y}$ (and this is also the case for classical span-
tuples). However, $[i,j\rangle,[k,l\rangle\in t(\textsf{x})$ with $i\leq
k<j\leq l$ is not possible for multispan-tuples, since then representing
$[i,j\rangle$ and $[k,l\rangle$ by parentheses
$\prescript{}{\textsf{x}}{\textsf{\vdash}}\ldots\textsf{\dashv}_{\textsf{x}}$
in the document cannot be distinguished from representing $[i,l\rangle$ and
$[k,j\rangle$. Furthermore, for distinct $s,s^{\prime}\in t(\textsf{x})$ we
require that $s$ and $s^{\prime}$ are disjoint, which is motivated by the fact
that without this restriction, the subsequence of all
$\prescript{}{\textsf{x}}{\textsf{\vdash}}$ and $\textsf{\dashv}_{\textsf{x}}$
occurrences could be an arbitrary well-formed parenthesised expression
(instead of a sequence
$(\prescript{}{\textsf{x}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}})^{k}$);
thus, recognising whether a given string over
$\Sigma\cup\Gamma_{\mbox{$\mathcal{X}$}}$ is a proper multiref-word cannot be
done by an NFA, as is the case for classical spanners.

Our main motivation for multispanners is that they can express information
extraction tasks that are of interest in the context of our extract and
transform framework (and that cannot be represented by classical spanners in a
convenient way). However, there are other interesting properties of
multispanners not related to their application in our extract and transform
framework, which deserve further investigation. For example, if $L$ and
$L^{\prime}$ are multiref-languages (i. e., ${\lsem{}{L}\rsem}$ and
${\lsem{}{L^{\prime}}\rsem}$ are multispanners), then $L\cup L$, $L\cdot
L^{\prime}$ and $L^{*}$ are also multiref-languages (and therefore
${\lsem{}{L\cup L^{\prime}}\rsem}$, ${\lsem{}{L\cdot L}\rsem}$ and
${\lsem{}{L^{*}}\rsem}$ are also multispanners). For classical spanners, this
is only true for the union. Consequently, multispanners show some robustness
not provided by classical spanners.

##  3 Extract transform framework

Let us first present some more notation. As usual, $f:A\to B$ denotes a
function from $A$ to $B$. When $f$ is partial, we write $f:A\rightharpoonup B$
and use $f(a)=\textsf{\bot}$ to indicate that $f$ is undefined for element
$a\in A$. Moreover, $\textsf{dom}(f)=\\{a\in A\mid f(a)\neq\bot\\}$ denotes
the domain of $f$. Every partial function $T:A^{*}\rightharpoonup B^{*}$ is
called a _string-to-string function_ with input alphabet $A$ and output
alphabet $B$.

The main idea of our extraction and transformation framework is to use a
document spanner to extract information and then use a string-to-string
function to convert this information into new documents. For this purpose, it
is necessary to convert the output of a spanner (i.e., span-tuples) into the
input of a string-to-string function (i.e., strings). In the following, we
present a unique way to encode multispan-tuples into multiref-words, which
will serve as our intermediate object between extraction and transformation.

#### A unique multiref-word representation

The representation of documents and multispan-tuples by multiref-words allows
us to define multispanners by multiref-languages. But this representation is
not unique, which is inconvenient if we want to use it for encoding multispan-
tuples as strings. As a remedy, we adopt the following approach: We represent
a document $\mathbf{D}\in\Sigma^{*}$ and multispan-tuple $t$ as a multiref-
word $w$ such that factors of $w$ that belong to
$\Gamma_{\mbox{$\mathcal{X}$}}^{*}$ (i.e., factors between two letters of
$\mathbf{D}$) have the form:

$(\textsf{\dashv}_{\textsf{x}}\textsf{+}\textsf{\varepsilon})(\prescript{}{\textsf{x}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}}\textsf{+}\textsf{\varepsilon})(\prescript{}{\textsf{x}}{\textsf{\vdash}}\textsf{+}\textsf{\varepsilon})(\textsf{\dashv}_{\textsf{y}}\textsf{+}\textsf{\varepsilon})(\prescript{}{\textsf{y}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{y}}\textsf{+}\textsf{\varepsilon})(\prescript{}{\textsf{y}}{\textsf{\vdash}}\textsf{+}\textsf{\varepsilon})\ldots\,.$

Specifically, let $\mathbf{D}\in\Sigma^{*}$ be a document and $t$ a multispan-
tuple over $\mathbf{D}$ and variables $\mathcal{X}$. For a variable
$\textsf{x}\in\mbox{$\mathcal{X}$}$ and $i\in[|\mathbf{D}|+1]$, define
$t[i,x]\ =\ \
(\textsf{\dashv}_{\textsf{x}})^{c}(\prescript{}{\textsf{x}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}})^{e}(\prescript{}{\textsf{x}}{\textsf{\vdash}})^{o}$,
where $c,e,o\in\\{0,1\\}$ with $c=1$ iff $[j,i\rangle\in t(\textsf{x})$ for
some $j\neq i$; $e=1$ iff $[i,i\rangle\in t(\textsf{x})$; and $o=1$ iff
$[i,j\rangle\in t(\textsf{x})$ for some $j\neq i$. E. g., for the tuple $t$ in
Example 2.1, we have that
$t[3,\textsf{x}]=\prescript{}{\textsf{x}}{\textsf{\vdash}}$ and
$t[4,\textsf{y}]=\textsf{\dashv}_{\textsf{y}}\prescript{}{\textsf{y}}{\textsf{\vdash}}$.

Let
$\mbox{$\mathcal{X}$}=\\{\textsf{x}_{1},\textsf{x}_{2},\ldots,\textsf{x}_{m}\\}$
with $\textsf{x}_{1}\preceq\textsf{x}_{2}\preceq\ldots\preceq\textsf{x}_{m}$,
where $\preceq$ is some fixed linear order on $\mathcal{X}$. For every
$i\in[|\mathbf{D}|+1]$, we define $t[i]\ :=\ \ t[i,\textsf{x}_{1}]\cdot
t[i,\textsf{x}_{2}]\cdot\ldots\cdot t[i,\textsf{x}_{m}]$. We can then define
the encoding of $t$ and $\mathbf{D}$ as the multiref-word:

$\mathtt{enc}(t,\mathbf{D})\ =\ \ t[1]\cdot\mathbf{D}[1]\cdot
t[2]\cdot\mathbf{D}[2]\cdot\ldots\cdot\mathbf{D}[|\mathbf{D}|]\cdot
t[|\mathbf{D}|{+}1].$

Note that $\mathtt{enc}(t,\mathbf{D})$ is a multiref-word,
$\mathbf{D}_{\mathtt{enc}(t,\mathbf{D})}=\mathbf{D}$ and
$\textsf{t}_{\mathtt{enc}(t,\mathbf{D})}=t$. Thus,
$\mathtt{enc}(t,\mathbf{D})$ is a correct and unique encoding for $t$ and
$\mathbf{D}$ as a multiref-word. Next, we use this encoding to define
_extract-transform programs_.

#### Extract-transform programs

An _extract-transform program_ (for short: _ET program_) is a pair $(E,T)$
such that $E$ is a multispanner over $\Sigma$ and $\mathcal{X}$, and $T$ is a
string-to-string function with input alphabet
$\Sigma\cup\Gamma_{\mbox{$\mathcal{X}$}}$ and some output alphabet $\Omega$.
The semantics ${\lsem{}{E\cdot T}\rsem}$ of an ET program $(E,T)$ is defined
as follows. For an input document $\mathbf{D}$, we first apply $E$ on
$\mathbf{D}$, which produces a multispan-relation $E(\mathbf{D})$. Then, for
every multispan-tuple $t\in E(\mathbf{D})$, we apply $T$ on the multiref-word
$\mathtt{enc}(t,\mathbf{D})$ producing a new document in the output. Note that
while $\mathtt{enc}(\cdot,\cdot)$ is injective, the function $T$ might not be,
which means that for $t,t^{\prime}\in E(\mathbf{D})$ with $t\neq t^{\prime}$
we might have
$T(\mathtt{enc}(t,\mathbf{D}))=T(\mathtt{enc}(t^{\prime},\mathbf{D}))$. This
leads to duplicates, but, as explained in the introduction, we keep them,
since we want each distinct $t\in E(\mathbf{D})$ of the extraction phase to
correspond to a transformed document in the output. Hence, the output set is a
_bag_ (also known as _multiset_). As common in the literature, we use the
notation $\\{\\!\\!\\{\ldots\\}\\!\\!\\}$ for bags (we give a detailed
definition of bags in Appendix, Section A). Formally, for every
$\mathbf{D}\in\Sigma^{*}$, we define ${\lsem{}{E\cdot T}\rsem}(\mathbf{D})\ =\
\\{\\!\\!\\{T(\mathtt{enc}(t,\mathbf{D}))\mid t\in E(\mathbf{D})\\}\\!\\!\\}$.

#### Polyregular ET programs

In the introduction, we have already discussed several examples of ET programs
on an intuitive level. The multispanners of these examples were explicitly
stated as multispanner expressions. The transformation functions were given as
ad-hoc specifications, but they were all instances of so-called _polyregular
functions_. A polyregular function is a string-to-string function that is
regular and has a growth at most polynomial in the size of the output string.
Formally, $T$ is polyregular if it can be defined by a _pebble transducer_ : a
two-way transducer enhanced with a fixed number of pebbles (i.e., pointers)
that the machine can drop or remove over the input word in a nested fashion
and can read when it passes over them (see [20] for a formal definition).
Polyregular functions form a robust class that has found several
characterizations, among them for-transducers, MSO interpretations, and others
[12]. Furthermore, polyregular functions are closed under composition and have
good theoretical properties (see [12] for an overview). For this reason, we
introduce the following definition.

A _polyregular ET program_ is an ET program $(E,T)$ where $E$ is a regex
multispanner and $T$ is a polyregular function. All the ET programs mentioned
in the introduction were examples of polyregular ET programs. In the example
ET program $(E_{2},T_{2})$ discussed there, we need the following string-to-
string function $T_{2}$ in the transformation phase:

$\displaystyle
u\>\\#\prescript{}{\textsf{x}}{\textsf{\vdash}}u_{\textsf{x}}\textsf{\dashv}_{\textsf{x}};\prescript{}{\textsf{y}}{\textsf{\vdash}}u_{\textsf{y}}\textsf{\dashv}_{\textsf{y}};\prescript{}{\textsf{z}}{\textsf{\vdash}}v_{\textsf{z},1}\textsf{\dashv}_{\textsf{z}};\prescript{}{\textsf{z}}{\textsf{\vdash}}v_{\textsf{z},2}\textsf{\dashv}_{\textsf{z}}\ldots\prescript{}{\textsf{z}}{\textsf{\vdash}}v_{\textsf{z},k}\textsf{\dashv}_{\textsf{z}}\>u^{\prime}\>\mapsto$
$\displaystyle u_{\textsf{y}}\mbox{\kern 0.59998pt\vrule
height=1.29167pt}\vbox{\hrule width=3.00003pt}\hbox{\vrule
height=1.29167pt}u_{\textsf{x}}:v_{\textsf{z},1}\\#u_{\textsf{y}}\mbox{\kern
0.59998pt\vrule height=1.29167pt}\vbox{\hrule width=3.00003pt}\hbox{\vrule
height=1.29167pt}u_{\textsf{x}}:v_{\textsf{z},2}\\#\ldots\\#u_{\textsf{y}}\mbox{\kern
0.59998pt\vrule height=1.29167pt}\vbox{\hrule width=3.00003pt}\hbox{\vrule
height=1.29167pt}u_{\textsf{x}}:v_{\textsf{z},k}\\#\,,$

where $u,u^{\prime}\in\Sigma^{*}$,
$u_{\textsf{x}},u_{\textsf{y}},v_{\textsf{z},1},v_{\textsf{z},2},\ldots,v_{\textsf{z},k}\in\widehat{\Sigma}^{*}$.
It can be verified that this is indeed a polyregular function, by defining a
pebble transducer or a for-transducer for it, which, due to space constraints,
is done in the Appendix (see Section B).

Let us explain why the class of polyregular functions is a good choice for our
setting. As mentioned before, polyregular functions can be seen as the class
of MSO string-to-string functions, i.e., they have the same expressive power
as MSO interpretations. Furthermore, polyregular functions are a robust and
well-established class with several representations and good closure
properties. Polyregular functions also capture most of the transformations
that occur in practice. For example, practical regex use substitutions for
transforming strings [44, 45]. Interestingly, one can define all these
operators by combining regex multispanners and polyregular functions. There
are even substitutions in regex that define non-linear polyregular functions
(e.g., see the operator `$’` in [1,2]). Thus, polyregular functions are a
natural choice. In the following we will focus on a fragment called _linear ET
programs_.

#### Linear ET programs

We restrict attention to string-to-string functions of linear growth.
Specifically, we say that a string-to-string function $T$ has _linear growth_
if there exists a constant $c$, such that $|T(w)|\leq c\cdot|w|$ for every
string $w$. A _linear ET program_ is a polyregular ET program $(E,T)$ where
$T$ has linear growth.

The class of linear polyregular functions forms a proper and well-behaved
subclass of polyregular functions, which allows for several equivalent
representations like two-way transducers, MSO transductions, or deterministic
streaming string transducers [12, 3] (this last formalism will be crucial for
the rest of this paper). The string-to-string function $T_{1}$ (see Page 1)
that we used in the first example discussed in the introduction is an example
of a linear polyregular function, and we shall see a deterministic streaming
string transducer for it later on.

#### Deterministic streaming string transducers

Let $\mathcal{R}$ be a finite set of registers and $\Omega$ a finite alphabet.
An _assignment_ 111We assume that assignments are partial functions, in
contrast to [4] that assume that assignments are functions. Note that this
generalization of the model in [4] comes without modifying the expressive
power of standard streaming string transducers.  is a partial function
$\sigma:\mathcal{R}\rightharpoonup(\mathcal{R}\cup\Omega)^{*}$ that assigns
each register $X\in\mathcal{R}$ to a string $\sigma(X)$ of registers and
letters from $\Omega$. We define the extension
$\hat{\sigma}:(\mathcal{R}\cup\Omega)^{*}\rightharpoonup(\mathcal{R}\cup\Omega)^{*}$
of an assignment such that
$\hat{\sigma}(\alpha_{1}\ldots\alpha_{n})=\sigma(\alpha_{1})\cdot\ldots\cdot\sigma(\alpha_{n})$
for every string $\alpha_{1}\ldots\alpha_{n}\in(\mathcal{R}\cup\Omega)^{*}$
where
$\sigma(\textsf{\ooalign{\scalebox{1.0}[1.0]{$o$}\cr\rotatebox[origin={c}]{-30.0}{\raisebox{1.72218pt}{\scalebox{0.65}{$\
\boldsymbol{\smile}$}}}}})=\textsf{\ooalign{\scalebox{1.0}[1.0]{$o$}\cr\rotatebox[origin={c}]{-30.0}{\raisebox{1.72218pt}{\scalebox{0.65}{$\
\boldsymbol{\smile}$}}}}}$ for every
$\textsf{\ooalign{\scalebox{1.0}[1.0]{$o$}\cr\rotatebox[origin={c}]{-30.0}{\raisebox{1.72218pt}{\scalebox{0.65}{$\
\boldsymbol{\smile}$}}}}}\in\Omega$. Further, we assume that
$\hat{\sigma}(\alpha_{1}\ldots\alpha_{n})$ is undefined iff
$\sigma(\alpha_{i})$ is undefined for some $i\in[n]$. Given two assignments
$\sigma_{1}$ and $\sigma_{2}$, we define its composition
$\sigma_{1}\circ\sigma_{2}$ as a new assignment such that
$[\sigma_{1}\circ\sigma_{2}](X)=\hat{\sigma}_{1}(\sigma_{2}(X))$. We say that
an assignment $\sigma$ is _copyless_ if, for every $X\in\mathcal{R}$, there is
at most one occurrence of $X$ in all the strings $\sigma(Y)$ with
$Y\in\mathcal{R}$.

######  Example 3.1.

Consider $\mathcal{R}=\\{X,Y\\}$ and $\Omega=\\{a,b\\}$, and the following
assignments where we write $X:=\alpha$ to mean $\sigma(X)=\alpha$:

$\begin{array}[]{ccccc}\begin{array}[]{rl}\sigma_{1}\colon\\!\\!&X:=aXa\\\
&Y:=XY\end{array}&&\begin{array}[]{rl}\sigma_{2}\colon\\!\\!&X:=bXb\\\
&Y:=b\end{array}&&\begin{array}[]{rl}\sigma_{3}:\\!\\!&X:=baXab\\\
&Y:=b\end{array}\end{array}$

One can check that $\sigma_{1}\circ\sigma_{2}=\sigma_{3}$. Also, $\sigma_{2}$
and $\sigma_{3}$ are copyless assignments, but $\sigma_{1}$ is not.

Note that copyless assignments are closed under composition, namely, if
$\sigma_{1}$ and $\sigma_{2}$ are copyless assignments, then
$\sigma_{1}\circ\sigma_{2}$ is copyless as well. We denote by
$\textsf{Asg}(\mathcal{R},\Omega)$ the set of all copyless assignments over
registers $\mathcal{R}$ and alphabet $\Omega$.

A _deterministic streaming string transducer_ (DSST) [3] is a tuple
$\mathcal{T}=(Q,\Sigma,\Omega,\mathcal{R},\Delta,q_{0},F)$, where $Q$ is a
finite set of states, $\Sigma$ is the input alphabet, $\Omega$ is the output
alphabet, $\mathcal{R}$ is a finite set of registers, $\Delta\colon
Q\times\Sigma\rightharpoonup\textsf{Asg}(\mathcal{R},\Omega)\times Q$ is the
transition function, $q_{0}$ is the initial state, and
$F:Q\rightharpoonup(\mathcal{R}\cup\Omega)^{*}$ is a final partial function
such that, for every $q\in Q$ and $X\in\mathcal{R}$, $X$ appears at most once
in $F(q)$. Intuitively, if $F(q)$ is defined, then $q$ is a final (i.e.,
accepting) state. A _configuration_ of a DSST $\mathcal{T}$ is a pair
$(q,\nu)$ where $q\in Q$ and $\nu\in\textsf{Val}(\mathcal{R},\Omega)$, and
$\textsf{Val}(\mathcal{R},\Omega)$ is the set of all assignments
$\mathcal{R}\rightharpoonup\Omega^{*}$, which are called _valuations_. A _run_
$\rho$ of $\mathcal{T}$ over a string $a_{1}\ldots a_{n}$ is a sequence of
configurations $(q_{i},\nu_{i})$ of the form:

$\rho\ :=\
(q_{0},\nu_{0})\xrightarrow{a_{1}/\sigma_{1}}(q_{1},\nu_{1})\xrightarrow{a_{2}/\sigma_{2}}\ldots\xrightarrow{a_{n}/\sigma_{n}}(q_{n},\nu_{n})$

such that $\Delta(q_{i},a_{i+1})=(\sigma_{i+1},q_{i+1})$, $\nu_{0}$ is the
empty assignment, i. e. $\nu_{0}(X)=\textsf{\varepsilon}$ for every
$X\in\mathcal{R}$, and $\nu_{i+1}=\nu_{i}\circ\sigma_{i+1}$ for every $i<n$. A
run $\rho$ is called an _accepting run_ if $\nu_{n}(F(q_{n}))$ is defined. The
_output_ of an accepting run $\rho$ is defined as the string
$\textsf{out}(\rho):=\nu_{n}(F(q_{n}))$.

Since $\Delta$ is a partial function, we can see that DSST are deterministic,
i.e., for every input word $w$, there exists at most one run $\rho$. Thus,
every DSST $\mathcal{T}$ defines a string-to-string function
${\lsem{}{\mathcal{T}}\rsem}$ such that
${\lsem{}{\mathcal{T}}\rsem}(w)=\textsf{out}(\rho)$ iff $\rho$ is the run of
$\mathcal{T}$ over $w$ and $\rho$ is accepting.

######  Example 3.2.

Recall the string-to-string function $T_{1}\
=u\prescript{}{\textsf{x}}{\textsf{\vdash}}v_{\textsf{x}}\textsf{\dashv}_{\textsf{x}};\prescript{}{\textsf{y}}{\textsf{\vdash}}v_{\textsf{y}}\textsf{\dashv}_{\textsf{y}}u^{\prime}\>\>\mapsto\>\>v_{\textsf{y}}\mbox{\kern
0.59998pt\vrule height=1.29167pt}\vbox{\hrule width=3.00003pt}\hbox{\vrule
height=1.29167pt}\,v_{\textsf{x}}$, where $u,u^{\prime}\in\Sigma^{*}$ and
$v_{\textsf{x}},v_{\textsf{y}}\in\widehat{\Sigma}^{*}$ (see Page 1). This
function is implemented by the following DSST:

$q_{0}$pt$\begin{array}[]{l}X:=\textsf{\varepsilon}\vspace{-1mm}\\\
Y:=\textsf{\varepsilon}\end{array}\\!\\!\\!$pt$\Sigma$$q_{1}$$q_{2}$$q_{3}$pt$Y\mbox{\kern
0.59998pt\vrule height=1.29167pt}\vbox{\hrule width=3.00003pt}\hbox{\vrule
height=1.29167pt}\,X$pt$\prescript{}{\textsf{x}}{\textsf{\vdash}}$pt$a\in\widehat{\Sigma}\
\ \begin{array}[]{|l}X:=Xa\vspace{-1mm}\\\
Y:=Y\end{array}$pt$a\in\widehat{\Sigma}\ \
\begin{array}[]{|l}X:=X\vspace{-1mm}\\\
Y:=Ya\end{array}$pt$\textsf{\dashv}_{\textsf{x}}\,;\,\prescript{}{\textsf{y}}{\textsf{\vdash}}$pt$\textsf{\dashv}_{\textsf{y}}$pt$\Sigma$

DSSTs form a well-behaved class of linear string-to-string functions,
equivalent to the previously mentioned class of linear polyregular functions
(see [12, 3]). Moreover, DSSTs perform a single pass over the input string,
while other equivalent models (e.g., two-way transducers) may do several
passes. This streaming behavior of DSSTs will turn out to be very useful for
designing algorithms for linear ET programs. For this reason, in the sequel we
use DSSTs as our model of string-to-string functions for linear ET programs.

##  4 Expressiveness of linear extract transform programs

#### Nondeterministic streaming string transducers

We extend DSSTs (cf. Section 3) to the nondeterministic case and bag
semantics. Let us explain the model by pointing out its differences to
DSSTs.222Note that nondeterministic streaming string transducers with _set
semantics_ instead of bag semantic have already been introduced in [4].

A _nondeterministic streaming string transducer_ (NSST) is a tuple
$\mathcal{T}=(Q,\Sigma,\Omega,\mathcal{R},\Delta,I,F)$, where $Q$, $\Sigma$,
$\Omega$, $\mathcal{R}$ and $F$ have the same meaning as for DSSTs. The
partial function $I:Q\rightharpoonup\textsf{Val}(\mathcal{R},\Omega)$ plays
the role of the initial state, i. e., a state $q$ is a possible initial state
if $I(q)$ is defined, and in this case $I(q)$ is an initial valuation of the
registers. Moreover, $\Delta$ is not a (partial) function from $Q\times\Omega$
to $\textsf{Asg}(\mathcal{R},\Omega)\times Q$ anymore, but a _bag_ of
transitions, i.e., $\Delta$ is a bag of elements in
$Q\times\Sigma\times\textsf{Asg}(\mathcal{R},\Omega)\times Q$.

The semantics of the model are as expected. A run over a string $a_{1}\ldots
a_{n}$ is a sequence of configurations $(q_{i},\nu_{i})$ of the form:

$\rho\ :=\
(q_{0},\nu_{0})\xrightarrow{a_{1}/\sigma_{1}}(q_{1},\nu_{1})\xrightarrow{a_{2}/\sigma_{2}}\ldots\xrightarrow{a_{n}/\sigma_{n}}(q_{n},\nu_{n})$

such that $I(q_{0})$ is defined and $\nu_{0}=I(q_{0})$,
$(q_{i},a_{i+1},\sigma_{i+1},q_{i+1})\in\Delta$ and
$\nu_{i+1}=\nu_{i}\circ\sigma_{i+1}$ for every $i<n$. As for DSSTs, $\rho$ is
an _accepting run_ if $\nu_{n}(F(q_{n}))$ is defined, and the output of an
accepting run $\rho$ is the string $\textsf{out}(\rho)=\nu_{n}(F(q_{n}))$. We
define $\textsf{Runs}_{\mathcal{T}}(a_{1}\ldots a_{n})$ as the bag of all
accepting runs of $\mathcal{T}$ over $a_{1}\ldots a_{n}$.

Finally, we define the semantics of an NSST $\mathcal{T}$ over a string
$w\in\Sigma^{*}$ as the bag:

${\lsem{}{\mathcal{T}}\rsem}(w)\ =\
\\{\\!\\!\\{\,\textsf{out}(\rho)\,\mid\,\rho\in\textsf{Runs}_{\mathcal{T}}(w)\,\\}\\!\\!\\}.$

#### Equivalence of linear ET programs and NSSTs

We show that linear ET programs and NSSTs are equivalent. This is a
fundamental insight with respect to the expressive power of ET programs.
Moreover, the fact that the two-stage model of linear ET programs can be
described by a single NSST will be important for our enumeration algorithm
(Section 5) and their composition (Section 6).

We first discuss how linear ET programs can be transformed into NSSTs. Every
multiref-word over $\Sigma$ and $\mathcal{X}$ describes a document
$\mathbf{D}_{w}$ and a multispan-tuple $\textsf{t}_{w}$. Hence, we can extend
the encoding $\mathtt{enc}(\cdot)$ to multiref-words by setting
$\mathtt{enc}(w)=\mathtt{enc}(\textsf{t}_{w},\mathbf{D}_{w})$. Intuitively
speaking, applying the function $\mathtt{enc}(\cdot)$ on a multiref-word $w$
simply means that every maximal factor $u\in\Gamma_{\mbox{$\mathcal{X}$}}^{*}$
of $w$ is re-ordered according to the order $\preceq$ on $\mathcal{X}$, and
superfluous matching brackets
$\prescript{}{\textsf{x}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}}$ are
removed (since several of those in the same maximal factor over
$\Gamma_{\mbox{$\mathcal{X}$}}$ would describe the same empty span several
times). We define $\mathtt{enc}(L)=\\{\mathtt{enc}(w)\mid w\in L\\}$ for
multiref-languages $L$.

Let us consider a linear ET program ${\lsem{}{E\cdot T}\rsem}$, i. e., $E$ is
a regex multispanner represented by some multispanner-expression $r$, and $T$
is a linear polyregular function represented by some DSST $\mathcal{T}$. The
high-level idea of the proof is to construct an NSST $\mathcal{T}^{\prime}$
that simulates a DFA $M$ for $\mathtt{enc}(\mathcal{L}(r))$ and the DSST
$\mathcal{T}$ in parallel. More precisely, we read an input
$\mathbf{D}\in\Sigma^{*}$, but between reading a symbol $\mathbf{D}[i]$ and
the next symbol $\mathbf{D}[i+1]$, we pretend to read a sequence of symbols
from $\Gamma_{\mbox{$\mathcal{X}$}}$ with $\mathcal{T}$ and $M$ at the same
time. Thus, we virtually read some multiref-word $w$ with the property
$\mathbf{D}_{w}=\mathbf{D}$. We need the DSST $\mathcal{T}$ for producing an
output on that multiref-word, and we need the DFA $M$ to make sure that the
virtual multiref-word has the form $\mathtt{enc}(t,\mathbf{D})$ for some $t\in
E(\mathbf{D})$.

One may wonder why we want $M$ to be a DFA rather than an NFA. The reason is:
Having to deal with bag semantics (rather than just set semantics) makes
things more complicated. In particular, this means that we need $M$ to be
deterministic to have a one-to-one correspondence between the accepting runs
of $\mathcal{T}^{\prime}$ and the accepting runs of $M$ on the corresponding
multiref-word. Otherwise, if $M$ was an NFA, the different possible accepting
paths of $M$ on the same multiref-word would translate into different
accepting paths of $\mathcal{T}^{\prime}$ which would cause erroneous
duplicates in ${\lsem{}{\mathcal{T}^{\prime}}\rsem}(\mathbf{D})$.

We can transform $r$ into a DFA $M$ for $\mathtt{enc}(\mathcal{L}(r))$ by
standard automata constructions, but the fact that $M$ needs to be
deterministic means that the construction is (one-fold) exponential in $|r|$,
and the fact that it has to accept $\mathtt{enc}(\mathcal{L}(r))$ and not just
$\mathcal{L}(r)$ means that the construction is also (one-fold) exponential in
$|\mbox{$\mathcal{X}$}|$. In summary, we obtain the following result.

######  Theorem 4.1.

Given a regex multispanner $E$ over $\Sigma$ and $\mathcal{X}$ (represented by
a multispanner-expression $r$), and a linear polyregular string-to-string
function $T$ with input alphabet $\Sigma\cup\Gamma_{\mbox{$\mathcal{X}$}}$
(represented by a DSST with $h$ states), we can construct an NSST
$\mathcal{T}$ with ${\lsem{}{\mathcal{T}}\rsem}={\lsem{}{E\cdot T}\rsem}$ in
time
$\textsf{}(2^{4|r|+9|\mathcal{X}|}|\Sigma|^{3}|\mbox{$\mathcal{X}$}|^{2}h^{2})$.

Let us now move on to representing general NSSTs by ET programs. When an NSST
$\mathcal{T}$ is in a state $p$ and reads a symbol $b\in\Sigma$, then the
number of possible nondeterministic choices it can make is the sum over all
the multiplicities of elements $(p,b,\sigma,q)\in\Delta$ (recall that $\Delta$
is the bag of transitions). We shall call this number the _nondeterministic
branching factor of $p$ and $b$_. The _nondeterministic branching factor_ of
$\mathcal{T}$ is the maximum over all the nondeterministic branching factors
of $p$ and $b$ for all $(p,b)\in Q\times\Sigma$.

The only obstacle in the simulation of an NSST by a DSST is that the latter
cannot deal with the nondeterministic choices. However, in linear ET programs,
a DSST gets an annotated version of the actual document $\mathbf{D}$ as input,
i. e., a multiref-word $w$ with $\mathbf{D}_{w}=\mathbf{D}$. Consequently, the
DSST could interpret the additional information given by $w$ in the form of
the symbols from $\Gamma_{\mbox{$\mathcal{X}$}}$ as information that
determines which nondeterministic choices it should make. More formally, we
can construct a regex multispanner that, for every
$i\in[1,2,\ldots,|\mathbf{D}|]$, nondeterministically chooses some
$\textsf{x}_{\ell}\in\\{\textsf{x}_{1},\textsf{x}_{2},\ldots,\textsf{x}_{m}\\}$,
where $m$ is the NSST’s nondeterministic branching factor, and puts the empty
span $[i,i\rangle$ into $t(\textsf{x})$. On the level of multiref-words, this
simply means that every symbol is preceded by
$\prescript{}{\textsf{x}_{\ell}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}_{\ell}}$
for some $\ell$. Such an occurrence of
$\prescript{}{\textsf{x}_{\ell}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}_{\ell}}$
can then be interpreted by the DSST as an instruction to select the
$\ell^{\text{th}}$ nondeterministic choice when processing the next symbol
from $\Sigma$. In summary, we obtain the following result.

######  Theorem 4.2.

Given an NSST $\mathcal{T}$ with $n$ states, input alphabet $\Sigma$ and
nondeterministic branching factor $m$, we can construct a regex multispanner
$E$ over $\Sigma$ and
$\\{\textsf{x}_{1},\textsf{x}_{2},\ldots,\textsf{x}_{\max\\{n,m\\}}\\}$ and a
linear polyregular function $T$ with ${\lsem{}{E\cdot
T}\rsem}={\lsem{}{\mathcal{T}}\rsem}$. Moreover, $E$ is represented by a
multispanner-expression $r$ with $|r|=\textsf{}(|\Sigma|+\max\\{n,m\\})$, $T$
is represented by a DSST $\mathcal{T}^{\prime}$ with
$\textsf{}(\max\\{n,m\\}\cdot n)$ states, and both $r$ and
$\mathcal{T}^{\prime}$ can be constructed in time
$\textsf{}(|\mathcal{T}|+n\cdot\max\\{n,m\\}+|\Sigma|)$.

Let us conclude this section by mentioning that the statement of Theorem 4.1
is also true, if $E$ is a multispanner represented by an NFA (this stronger
version is proven in the appendix).

##  5 Evaluation of linear ET programs

In this section, we present the main technical result of the paper, regarding
the evaluation of linear ET programs. Specifically, we consider the following
enumeration problem (let $E$ be a regex multispanner and $T$ a linear
polyregular function).

Problem: $\textsc{EnumLinearET}[(E,T)]$ Input: A document $\mathbf{D}$ Output:
Enumerate ${\lsem{}{E\cdot T}\rsem}(\mathbf{D})$

Notice that ${\lsem{}{E\cdot T}\rsem}(\mathbf{D})$ is a bag; thus, the task is
to produce an enumeration that contains each element of the bag exactly once,
e. g., $(a,a,b,c,a)$ is a possible enumeration of
$\\{\\!\\!\\{b,a,a,a,c\\}\\!\\!\\}$.

As usual, we measure the running time in _data complexity_ , namely, we assume
that $E$ and $T$ are fixed. Given this assumption, we can assume that $E$ is
given as a multispanner-expression, and $T$ as a DSST. Otherwise, we can
convert $E$ and $T$ to satisfy this requirement.

For this problem, we strive for an _enumeration algorithm with linear
preprocessing and output-linear delay_ , i. e., in a _preprocessing phase_ it
receives the input and produces some data structure DS which encodes the
expected output, and in the following _enumeration phase_ it produces a
sequential enumeration $w_{1},\ldots,w_{\ell}$ of the results from DS.
Moreover, the time for the preprocessing phase is $\textsf{}(|\mathbf{D}|)$,
the time for producing $w_{1}$ is less than $c\cdot|w_{1}|$, and the time
between producing $w_{i-1}$ and $w_{i}$ is less than $c\cdot|w_{i}|$, for some
fixed constant $c$ that does not depend on the input. As it is common [43], we
assume the computational model of _Random Access Machines_ (RAM) with uniform
cost measure and addition and subtraction as basic operations [1]. We obtain
the following result.

######  Theorem 5.1.

$\textsc{{EnumLinearET}}[(E,T)]$ admits an enumeration algorithm with linear
preprocessing time and output-linear delay.

Due to space restrictions, all the details and the analysis of the enumeration
algorithm are deferred to the Appendix. In the following, we highlight the
main technical challenges of this algorithm.

The first step of the algorithm is to apply Theorem 4.1 and convert the pair
$(E,T)$ into an NSST $\mathcal{T}_{E,T}$. This takes time exponential in
$|E|$; nevertheless, it does not depend on $|\mathbf{D}|$ and so we can
consider it as constant time. Therefore, our enumeration algorithm aims for
computing ${\lsem{}{\mathcal{T}_{E,T}}\rsem}(\mathbf{D})$ with linear time
preprocessing and output-linear delay.

For evaluating $\mathcal{T}_{E,T}$ over $\mathbf{D}$, the first challenge that
we need to overcome is that its runs could maintain registers with content
that is not used at the end of the run. For an illustration, consider the
following NSST (note that $I(q)$ is the valuation $X:=\textsf{\varepsilon}$
and $Y:=\textsf{\varepsilon}$, and $F(p)=X$ and $F(r)=Y$):

$q$pt$\begin{array}[]{l}X:=\textsf{\varepsilon}\vspace{-1mm}\\\
Y:=\textsf{\varepsilon}\end{array}\\!\\!\\!$pt$a\ \
\begin{array}[]{|l}X:=aX\vspace{-1mm}\\\ Y:=Y\end{array}$pt$b\ \
\begin{array}[]{|l}X:=X\vspace{-1mm}\\\ Y:=bY\end{array}$$p$pt$X$$r$pt$Y$pt$a\
\ \begin{array}[]{|l}X:=aX\vspace{-1mm}\\\ Y:=Y\end{array}$pt$b\ \
\begin{array}[]{|l}X:=X\vspace{-1mm}\\\ Y:=bY\end{array}$

For each input word $w$ with $n$ $a$-symbols and $m$ $b$-symbols, the NSST
outputs $a^{n}$ if $w$ ends with $a$ and $b^{m}$ if $w$ ends with $b$.
Consequently, every run on a word that ends with $a$ produces “garbage” in
register $Y$, since the content of this register is not used for the output
(and analogously with register $X$ for inputs that end with $b$). This
behavior of storing “garbage” will be problematic for our enumeration
approach, given that the delay depends on the (potentially useless) contents
of the registers.

Given the above discussion, we formalize the notion of “garbage” as follows.
Consider an NSST $\mathcal{T}=(Q,\Sigma,\Omega,\mathcal{R},\Delta,I,F)$. For
$u\in(\mathcal{R}\cup\Omega)^{*}$, let $\textsf{reg}(u)$ be the set of all
registers $X\in\mathcal{R}$ that appear in $u$. For
$\sigma:\mathcal{R}\rightharpoonup(\mathcal{R}\cup\Omega)^{*}$ let
$\textsf{reg}(\sigma)=\bigcup_{X\in\textsf{dom}(\sigma)}\textsf{reg}(\sigma(X))$,
namely, $\textsf{reg}(\sigma)$ is the set of all registers used by $\sigma$.
We say that $\mathcal{T}$ is _garbage-free_ if, and only if, for every string
$w=a_{1}\ldots a_{n}$ and every accepting run $\rho$ of the form:

$\rho\ :=\
(q_{0},\nu_{0})\xrightarrow{a_{1}/\sigma_{1}}(q_{1},\nu_{1})\xrightarrow{a_{2}/\sigma_{2}}\ldots\xrightarrow{a_{n}/\sigma_{n}}(q_{n},\nu_{n})$

it holds that $\textsf{dom}(\nu_{i})=\textsf{reg}(\sigma_{i+1})$ for every
$i<n$, and $\textsf{dom}(\nu_{n})=\textsf{reg}(F(q_{n}))$. In other words, the
registers $\textsf{dom}(\nu_{i})$ that we have filled with content so far
coincide with the registers $\textsf{reg}(\sigma_{i+1})$ that we use on the
right hand sides of the next assignment.

The first challenge is to show how to make NSSTs garbage-free.

######  Proposition 5.2.

For every NSST $\mathcal{T}$, there exists a garbage-free NSST
$\mathcal{T}^{\prime}$ such
${\lsem{}{\mathcal{T}}\rsem}(w)={\lsem{}{\mathcal{T}^{\prime}}\rsem}(w)$ for
every string $w$.

The construction of Proposition 5.2 causes a blow-up that is exponential in
the number of registers, since we turn an NSST with $|Q|$ states into an NSST
with $|Q|\times 2^{|\mathcal{R}|}$ states. Of course, if we start with a
garbage-free NSST, this blow-up can be avoided. Interestingly, we can show
that one can check the garbage-free property in polynomial time.

######  Proposition 5.3.

Given an NSST $\mathcal{T}=(Q,\Sigma,\Omega,\mathcal{R},\Delta,I,F)$, we can
decide in time $\textsf{}(|\Delta|\cdot|\mathcal{R}|)$ whether $\mathcal{T}$
is garbage-free.

The second challenge is maintaining the set of outputs compactly for
enumerating them. The main problem here is that the output of a run is not
produced linearly as a single string (as is the case for classical spanners
[9, 6]) but instead in parallel on different registers that are combined in
some order at the end of the input. To solve this, we follow the approach in
[32, 33] and present an extension of _Enumerable Compact Sets_ (ECS), a data
structure that stores sets of strings compactly and retrieves them with
output-linear delay. We modify ECS for storing sets of valuations and we call
it _ECS with assignments_. For storing valuations, we use assignments in the
internal nodes of the data structure, which allows us to encode the runs’
output and keep the content of different registers synchronous.

Although we can eliminate the garbage from an NSST (cf., Proposition 5.2), the
machine can still swap and move registers during a run, producing assignments
that permute the registers’ content but do not contribute to a final output.
We call these assignments _relabelings_. Thus, the last challenge is taking
care of relabeling assignments. Similarly as in [33] (i.e., with shifts), we
treat them as special objects and compact them in the data structure whenever
possible. These extensions require to revisit ECS and to provide new ways for
extending or unifying sets of valuations by also taking care of relabeling
assignments.

##  6 Composition of linear ET programs

A valuable property of ET programs is that they receive documents as input and
produce documents as outputs. In this line, it is natural to think on reusing
the output of one ET program $(E_{1},T_{1})$ to feed a second ET program
$(E_{2},T_{2})$, namely, to compose them. Formally, we define the
_composition_ $(E_{1}\cdot T_{1})\circ(E_{2}\cdot T_{2})$ as a function
${\lsem{}{(E_{1}\cdot T_{1})\circ(E_{2}\cdot T_{2})}\rsem}$ that maps
documents to a bag of documents such that for every document $\mathbf{D}$:

${\lsem{}{(E_{1}\cdot T_{1})\circ(E_{2}\cdot T_{2})}\rsem}(\mathbf{D})\ =\
\bigcup_{\mathbf{D}^{\prime}\in{\lsem{}{E_{1}\cdot
T_{1}}\rsem}(\mathbf{D})}{\lsem{}{E_{2}\cdot
T_{2}}\rsem}(\mathbf{D}^{\prime}).$

Note that we use here the union of bags, which is defined in the natural way
(a formal definition is given in the Appendix, Section A).

For extraction and transformation of information, it is useful to evaluate the
composition efficiently. One naive approach is to evaluate
${\lsem{}{E_{1}\cdot T_{1}}\rsem}(\mathbf{D})$ (e.g., by using the evaluation
algorithm of Section 5 in case that $(E_{1},T_{1})$ is a _linear_ ET program),
and for every output $\mathbf{D}^{\prime}$ in ${\lsem{}{E_{1}\cdot
T_{1}}\rsem}(\mathbf{D})$ compute ${\lsem{}{E_{2}\cdot
T_{2}}\rsem}(\mathbf{D}^{\prime})$, gathering all the outputs together. Of
course, this could be time consuming, since $|{\lsem{}{E_{1}\cdot
T_{1}}\rsem}(\mathbf{D})|$ could be exponential in $|\mathbf{D}|$ in the worst
case.

Towards solving the previous algorithmic problem, in the next result we show
that every composition of NSSTs can be defined by an NSST. Formally, let us
denote the input and output alphabet of some NSST $\mathcal{T}$ by
$\Sigma(\mathcal{T})$ and $\Omega(\mathcal{T})$, respectively. Given two NSSTs
$\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ such that
$\Omega(\mathcal{T}_{1})\subseteq\Sigma(\mathcal{T}_{2})$, we define the
composition $\mathcal{T}_{1}\circ\mathcal{T}_{2}$ as the function from
documents to bags of documents:
${\lsem{}{\mathcal{T}_{1}\circ\mathcal{T}_{2}}\rsem}(\mathbf{D})=\
\bigcup_{\mathbf{D}^{\prime}\in{\lsem{}{\mathcal{T}_{1}}\rsem}(\mathbf{D})}{\lsem{}{\mathcal{T}_{2}}\rsem}(\mathbf{D}^{\prime})$.
We obtain the following result.

######  Theorem 6.1.

For every pair of NSSTs $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ such that
$\Omega(\mathcal{T}_{1})\subseteq\Sigma(\mathcal{T}_{2})$, there exists an
NSST $\mathcal{T}$ such that
${\lsem{}{\mathcal{T}}\rsem}={\lsem{}{\mathcal{T}_{1}\circ\mathcal{T}_{2}}\rsem}$.
The construction of $\mathcal{T}$ is effective, and
$|\mathcal{T}|=\textsf{}(2^{\mathsf{poly(|\mathcal{T}_{1}|,|\mathcal{T}_{2}|)}})$.

The statement of Theorem 6.1 for set semantics rather than bag semantics was
obtained by [4, 5]. The novelty of Theorem 6.1 is that we extend the result to
bag semantics; namely, we need to maintain the multiplicities of the final
outputs correctly. The proof revisits (and simplifies) the construction in [4,
5]: we simulate $\mathcal{T}_{1}$ over $\mathbf{D}$ while $\mathcal{T}_{2}$
runs over the registers’ content of $\mathcal{T}_{1}$, compactly representing
subruns of $\mathcal{T}_{2}$ by using pairs of states and assignment summaries
[3]. The extension requires two changes for working under bag semantics.
First, similar to the evaluation of NSSTs, garbage on
$\mathcal{T}_{1}$-registers could generate additional runs for
$\mathcal{T}_{2}$, producing outputs with wrong multiplicities. Therefore, our
first step is to remove this garbage by constructing equivalent garbage-free
NSSTs by using Propositon 5.2. Second, the construction in [4] guesses subruns
of $\mathcal{T}_{2}$ for each register content and each starting state. In the
end, we will use one of these guesses, and then unused subruns could modify
the output multiplicity. Therefore, we simplify the construction in [4] by
guessing a single subrun for each register content, using the non-determinism
to discard wrong guesses. Interestingly, this simplification overcomes the
error pointed out by Joost Engelfriet in the construction of [4], which was
solved recently in [5]. Our construction does not need the machinery of [5];
thus, an adaptation of our construction for NSSTs (with set semantics) can be
considered as a simplified version of the proof in [4, 5]. We conclude by
mentioning that as an alternative proof of Theorem 6.1 we could move to MSO
transductions [19], extend the logic with a bag semantics, and then do the
composition at a logical level; however, this strategy would lead to a non-
elementary blow-up.

By combining Theorem 4.1, 6.1 and 4.2, we get the following corollary
regarding the expressiveness of linear ET programs and their composition.

######  Corollary 6.2.

For every pair of linear ET programs $(E_{1},T_{1})$ and $(E_{2},T_{2})$,
there exists a linear ET program $(E,T)$ such that ${\lsem{}{E\cdot T}\rsem}\
\ =\ \ {\lsem{}{(E_{1}\cdot T_{1})\circ(E_{2}\cdot T_{2})}\rsem}$.

We conclude this section by the following corollary regarding the evaluation
of the composition of linear ET programs, obtained by combining Theorem 6.1
and 5.1.

######  Corollary 6.3.

Given linear ET programs $(E_{1},T_{1}),\ldots,(E_{k},T_{k})$ we can evaluate
the composition:

${\lsem{}{(E_{1}\cdot T_{1})\circ\ldots\circ(E_{k}\cdot
T_{k})}\rsem}(\mathbf{D})$

with linear time preprocessing and output-linear delay in data complexity.

##  7 Future Work

There are two obvious further research questions directly motivated by our
results. Firstly, the framework of multispanners deserves further
investigation. In particular, we wish to find out which results and properties
of classical spanners directly carry over to multispanners, and in which
regards these two models differ. Secondly, while we provide a sound
formalisation of the class of polyregular ET programs (and have argued that it
covers relevant extract and transform tasks), our technical results focus on
the subclass of linear ET programs. Our future work will focus on proving
similar results for the full class of polyregular ET programs.

## References

  * [1] Alfred V Aho and John E Hopcroft.  The design and analysis of computer algorithms.  Pearson Education India, 1974.
  * [2] Rajeev Alur, Mikołaj Bojańczyk, Emmanuel Filiot, Anca Muscholl, and Sarah Winter.  Regular Transformations (Dagstuhl Seminar 23202).  Dagstuhl Reports, 13(5):96–113, 2023.
  * [3] Rajeev Alur and Pavol Cerný.  Expressiveness of streaming string transducers.  In FSTTCS, pages 1–12, 2010.
  * [4] Rajeev Alur and Jyotirmoy V. Deshmukh.  Nondeterministic streaming string transducers.  In ICALP, volume 6756, pages 1–20, 2011.
  * [5] Rajeev Alur, Taylor Dohmen, and Ashutosh Trivedi.  Composing copyless streaming string transducers.  CoRR, abs/2209.05448, 2022.
  * [6] Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth.  Enumeration on trees with tractable combined complexity and efficient updates.  In PODS, pages 89–103. ACM, 2019.
  * [7] Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth.  Constant-delay enumeration for nondeterministic document spanners.  SIGMOD Rec., 49(1):25–32, 2020.
  * [8] Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth.  Constant-delay enumeration for nondeterministic document spanners.  ACM Transactions on Database Systems (TODS), 46(1):1–30, 2021.
  * [9] Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth.  Constant-delay enumeration for nondeterministic document spanners.  ACM Trans. Database Syst., 46(1):2:1–2:30, 2021.
  * [10] Jean Berstel.  Transductions and context-free languages.  Springer-Verlag, 2013.
  * [11] Mikolaj Bojanczyk.  Polyregular functions.  CoRR, abs/1810.08760, 2018.
  * [12] Mikolaj Bojanczyk.  Transducers of polynomial growth.  In LICS, pages 1:1–1:27. ACM, 2022.
  * [13] Pierre Bourhis, Alejandro Grez, Louis Jachiet, and Cristian Riveros.  Ranked enumeration of MSO logic on words.  In 24th International Conference on Database Theory, ICDT 2021, March 23-26, 2021, Nicosia, Cyprus, pages 20:1–20:19, 2021.
  * [14] Johannes Doleschal, Benny Kimelfeld, and Wim Martens.  The complexity of aggregates over extractions by regular expressions.  Logical Methods in Computer Science, 19(3), 2023.
  * [15] Johannes Doleschal, Benny Kimelfeld, Wim Martens, Yoav Nahshon, and Frank Neven.  Split-correctness in information extraction.  In Proceedings of the 38th ACM Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pages 149–163, 2019.
  * [16] Johannes Doleschal, Benny Kimelfeld, Wim Martens, Yoav Nahshon, and Frank Neven.  Split-correctness in information extraction.  In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 149–163, 2019.
  * [17] Johannes Doleschal, Benny Kimelfeld, Wim Martens, and Liat Peterfreund.  Weight annotation in information extraction.  Logical Methods in Computer Science, 18, 2022.
  * [18] James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, and Robert Endre Tarjan.  Making data structures persistent.  In STOC, pages 109–121, 1986.
  * [19] Joost Engelfriet and Hendrik Jan Hoogeboom.  MSO definable string transductions and two-way finite-state transducers.  ACM Trans. Comput. Log., 2(2):216–254, 2001.
  * [20] Joost Engelfriet and Sebastian Maneth.  Two-way finite state transducers with nested pebbles.  In MFCS, pages 234–244. Springer, 2002.
  * [21] Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren.  Spanners: a formal framework for information extraction.  In PODS, pages 37–48. ACM, 2013.
  * [22] Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren.  Document spanners: A formal approach to information extraction.  Journal of the ACM (JACM), 62(2):1–51, 2015.
  * [23] Fernando Florenzano, Cristian Riveros, Martín Ugarte, Stijn Vansummeren, and Domagoj Vrgoč.  Efficient enumeration algorithms for regular document spanners.  ACM Transactions on Database Systems (TODS), 45(1):1–42, 2020.
  * [24] Dominik Freydenberger and Mario Holldack.  Document spanners: From expressive power to decision problems.  Theory of Computing Systems, 62:854–898, 2018.
  * [25] Dominik D. Freydenberger.  A logic for document spanners.  Theory Comput. Syst., 63(7):1679–1754, 2019.
  * [26] Dominik D. Freydenberger, Benny Kimelfeld, and Liat Peterfreund.  Joining extractions of regular expressions.  In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, pages 137–149, 2018.
  * [27] Dominik D. Freydenberger and Sam M. Thompson.  Dynamic complexity of document spanners.  In 23rd International Conference on Database Theory, ICDT 2020, March 30-April 2, 2020, Copenhagen, Denmark, pages 11:1–11:21, 2020.
  * [28] Dominik D. Freydenberger and Sam M. Thompson.  Splitting spanner atoms: A tool for acyclic core spanners.  In Proc. ICDT 2022, pages 10:1–10:18, 2022.
  * [29] Jerry R. Hobbs, Douglas E. Appelt, John Bear, David J. Israel, Megumi Kameyama, Mark E. Stickel, and Mabry Tyson.  FASTUS: A cascaded finite-state transducer for extracting information from natural-language text.  CoRR, cmp-lg/9705013, 1997.
  * [30] Lauri Karttunen.  The replace operator.  Finite-State Language Processing, pages 117–147, 1997.
  * [31] Francisco Maturana, Cristian Riveros, and Domagoj Vrgoc.  Document spanners for extracting incomplete information: Expressiveness and complexity.  In PODS, pages 125–136, 2018.
  * [32] Martin Muñoz and Cristian Riveros.  Streaming enumeration on nested documents.  In ICDT, volume 220 of LIPIcs, pages 19:1–19:18, 2022.
  * [33] Martin Muñoz and Cristian Riveros.  Constant-delay enumeration for slp-compressed documents.  In ICDT, volume 255, pages 7:1–7:17, 2023.
  * [34] Anca Muscholl and Gabriele Puppis.  The many facets of string transducers (invited talk).  In Rolf Niedermeier and Christophe Paul, editors, STACS, volume 126 of LIPIcs, pages 2:1–2:21, 2019.
  * [35] Liat Peterfreund.  Grammars for document spanners.  In Ke Yi and Zhewei Wei, editors, ICDT, volume 186 of LIPIcs, pages 7:1–7:18, 2021.
  * [36] Liat Peterfreund, Dominik D. Freydenberger, Benny Kimelfeld, and Markus Kröll.  Complexity bounds for relational algebra over document spanners.  In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019., pages 320–334, 2019.
  * [37] Liat Peterfreund, Balder ten Cate, Ronald Fagin, and Benny Kimelfeld.  Recursive programs for document spanners.  In 22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal, pages 13:1–13:18, 2019.
  * [38] Cristian Riveros, Nicolás Van Sint Jan, and Domagoj Vrgoc.  Rematch: a novel regex engine for finding all matches.  VLDB, 16(11):2792–2804, 2023.
  * [39] Markus L. Schmid and Nicole Schweikardt.  A purely regular approach to non-regular core spanners.  In Ke Yi and Zhewei Wei, editors, 24th International Conference on Database Theory, ICDT 2021, March 23-26, 2021, Nicosia, Cyprus, volume 186 of LIPIcs, pages 4:1–4:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [40] Markus L. Schmid and Nicole Schweikardt.  Spanner evaluation over slp-compressed documents.  In PODS’21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Virtual Event, China, June 20-25, 2021, pages 153–165, 2021.
  * [41] Markus L. Schmid and Nicole Schweikardt.  Document spanners - A brief overview of concepts, results, and recent developments.  In Leonid Libkin and Pablo Barceló, editors, PODS ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, pages 139–150. ACM, 2022.
  * [42] Markus L. Schmid and Nicole Schweikardt.  Query evaluation over slp-represented document databases with complex document editing.  In PODS ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, pages 79–89, 2022.
  * [43] Luc Segoufin.  Enumerating with constant delay the answers to a query.  In ICDT, pages 10–20, 2013.
  * [44] https://www.tutorialsteacher.com/regex/substitution, 2024.  Accessed on 2024-03-15.
  * [45] https://learn.microsoft.com/en-us/dotnet/standard/base-types/substitutions-in-regular-expressions, 2024\.  Accessed on 2024-03-15.
  * [46] Panos Vassiliadis.  A survey of extract–transform–load technology.  International Journal of Data Warehousing and Mining (IJDWM), 5(3):1–27, 2009.

## APPENDIX

##  Appendix A Definitions for bags

Let us provide some formal details on bag semantics that will be useful in our
formal proofs.

A _bag_ $B$ is a surjective function $B:I\rightarrow U$ where $I$ is a finite
set of identifiers (or ids) and $U$ is the underlying set of the bag. Given
any bag $B$, we refer to these components as $I(B)$ and $U(B)$, respectively.
For example, a bag $B=\\{\\!\\!\\{a,a,b\\}\\!\\!\\}$ (where $a$ is repeated
twice) can be represented with a surjective function $B_{0}=\\{0\mapsto
a,1\mapsto a,2\mapsto b\\}$ where $I(B_{0})=\\{0,1,2\\}$ and
$U(B_{0})=\\{a,b\\}$. In general, we will use the standard notation for bags
$\\{\\!\\!\\{a_{0},\ldots,a_{n-1}\\}\\!\\!\\}$ to denote the bag $B$ whose
identifiers are $I(B)=\\{0,\ldots,n{-}1\\}$ and $B(i)=a_{i}$ for each $i\in
I(B)$. When we refer to the _elements of $B$_ we mean $I(B)$, namely,
considering every object of $B$ by its identity (i.e., its identifier).

For every $a$, we define the multiplicity of $a$ in $B$ as
$\textsf{mult}_{B}(a)=|\\{i\mid B(i)=a\\}|$, namely, the number of occurrences
of $a$ in $B$. Furthermore, we define $|B|=|I(B)|$. We say that a bag $B$ is
_contained_ in the bag $B^{\prime}$, and write $B\subseteq B^{\prime}$, if
$\textsf{mult}_{B}(a)\leq\textsf{mult}_{B^{\prime}}(a)$ for every $a$. We also
say that two bags $B$ and $B^{\prime}$ are _equal_ , and write $B=B^{\prime}$,
if $B\subseteq B^{\prime}$ and $B^{\prime}\subseteq B$. Given a set $A$, we
say that _$B$ is a bag of $A$_ if $U(B)\subseteq A$. Note that if
$B:I\rightarrow U$ is injective, then $B$ encodes a standard set (i.e., no
repetitions). Then we write $a\in B$ iff $B(i)=a$ for some $i\in I(B)$ and
define the empty bag $\emptyset$ as the bag such that
$I(\emptyset)=\emptyset$.

We define the _union_ $B_{1}\cup B_{2}$ of bags $B_{1}$ and $B_{2}$ such that
$I(B)=I(B_{1})\uplus I(B_{2})$, where $\uplus$ is the disjoint union, and
$B(i)=B_{1}(i)$ if $i\in I(B_{1})$ and $B(i)=B_{2}(i)$, otherwise. Note that
the union is associative, up to bag equivalence. For a function $f$ from a
finite set $A$ to bags of $A$, and a bag $B$ of $A$, we write $\bigcup_{b\in
B}f(b)$ to denote the bag representing $\bigcup_{i\in I(B)}f(B(i))$, namely,
the _generalized union_ where each element of $B$ contributes to the union.

##  Appendix B Formalisms for Polyregular Functions

As discussed in [12, 11], there are many equivalent formalisms for polyregular
functions. We discuss two classes of representations: pebble transducers and
for-transducers. As an example polyregular function, let us consider the
function $T_{2}$ of the example ET program $(E_{2},T_{2})$ discussed in the
introduction, i. e., the function

$\displaystyle T_{2}:\ \ \ $ $\displaystyle
u\>\\#\prescript{}{\textsf{x}}{\textsf{\vdash}}u_{\textsf{x}}\textsf{\dashv}_{\textsf{x}};\prescript{}{\textsf{y}}{\textsf{\vdash}}u_{\textsf{y}}\textsf{\dashv}_{\textsf{y}};\prescript{}{\textsf{z}}{\textsf{\vdash}}v_{\textsf{z},1}\textsf{\dashv}_{\textsf{z}};\prescript{}{\textsf{z}}{\textsf{\vdash}}v_{\textsf{z},2}\textsf{\dashv}_{\textsf{z}}\ldots\prescript{}{\textsf{z}}{\textsf{\vdash}}v_{\textsf{z},k}\textsf{\dashv}_{\textsf{z}}\>u^{\prime}\>\>\mapsto$
$\displaystyle u_{\textsf{y}}\mbox{\kern 0.59998pt\vrule
height=1.29167pt}\vbox{\hrule width=3.00003pt}\hbox{\vrule
height=1.29167pt}u_{\textsf{x}}:v_{\textsf{z},1}\\#u_{\textsf{y}}\mbox{\kern
0.59998pt\vrule height=1.29167pt}\vbox{\hrule width=3.00003pt}\hbox{\vrule
height=1.29167pt}u_{\textsf{x}}:v_{\textsf{z},2}\\#\ldots\\#u_{\textsf{y}}\mbox{\kern
0.59998pt\vrule height=1.29167pt}\vbox{\hrule width=3.00003pt}\hbox{\vrule
height=1.29167pt}u_{\textsf{x}}:v_{\textsf{z},k}\\#\,,$

where $u,u^{\prime}\in\Sigma^{*}$,
$u_{\textsf{x}},u_{\textsf{y}},v_{\textsf{z},1},v_{\textsf{z},2},\ldots,v_{\textsf{z},k}\in\widehat{\Sigma}^{*}$.

A for-transducer is a program of nested for-loops. Its input is some string
$w$. The loops are of the form “for $X$ in $k..l$ do”, where $X$ is a variable
that iterates through $k$ to $l$. The lower bound $k$ is either $1$ ($|w|$) or
the iterating variable of an earlier for-loop, and the upper bound $l$ is
either $|w|$ ($1$, respectively) or the iterating variable of an earlier for-
loop. Note that the loops can iterate either forwardly (i.e., from $1$ to
$|w|$), or backwardly (i.e., from $|w|$ to $1$). In addition, we can use
Boolean variables, if-conditionals, comparisons “$w[X]=b$”, where $X$ is a
for-loop variable and $b$ a symbol from the input alphabet, comparisons
“$X\leq Y$” of for-loop variables $X$ and $Y$, and an instruction “output $b$”
, which produces the output symbol $b$ as the next output symbol.

The Algorithm 1 represents a for-loop transducer for the string-to-string
function $T_{2}$ from above (note that we use “$w[X]\in\widehat{\Sigma}$” as
syntactic sugar).

To see that this for-transducer is correct, observe that the outer for-loop
outputs in Line $17$ all the input symbols from $\widehat{\Sigma}$ in their
order given by the input string, but it starts with the first symbol of
$v_{\textsf{z},1}$, due to the Boolean variable $B_{1}$. Consequently, the
outer loop produces the factors $v_{\textsf{z},j}$ for $j=1,2,\ldots,k$.
However, every time a new factor $v_{\textsf{z},j}$ starts (indicated by the
symbol $\prescript{}{\textsf{z}}{\textsf{\vdash}}$), we output $\\#$ and then
use the two inner loops to first produce ‘$u_{\textsf{y}}\mbox{\kern
0.59998pt\vrule height=1.29167pt}\vbox{\hrule width=3.00003pt}\hbox{\vrule
height=1.29167pt}$’ (first inner loop) followed by ‘$u_{\textsf{x}}$’ (second
inner loop), followed by the symbol ‘$:$’.

A _$k$ -pebble transducer_ is a finite automaton with a two-way input head and
$k$ pebbles that can be placed on input positions. However, the pebbles are
organised in a stack: We can place pebble $1$ on the current position $i$ of
the input head, which means that we push $i$ onto a stack, later in the
computation, we can place another pebble on the current position $j$ of the
input head, which means that we push $j$ onto the stack, and so on. Removing
the pebbles can only be done by popping the positions from the stack, i. e.,
we can only remove the pebble that has last been placed.

Depending on the current state, the current symbol, the symbols on the pebble
positions, and the relative order of the pebble positions, the pebble
transducer updates it states, moves the input head to the left or to the right
or leaves it unchanged, places a pebble on the current head position (and
pushes its position onto the stack) or pops the topmost pebble position from
the stack, and outputs an output symbol (or nothing). Pebble transducers are
equivalent to for-transducers and therefore describe the set of polyregular
functions [20, 12].

A pebble transducer with $1$ pebble can realise the string-to-string function
$T_{2}$ from above as follows. We find the first position of
$\prescript{}{\textsf{z}}{\textsf{\vdash}}$ and place a pebble on this
position. Then we move back with the input head until we see
$\prescript{}{\textsf{y}}{\textsf{\vdash}}$ and we output
$u_{\textsf{y}}\mbox{\kern 0.59998pt\vrule height=1.29167pt}\vbox{\hrule
width=3.00003pt}\hbox{\vrule height=1.29167pt}$. Then we move back with the
input head until we see $\prescript{}{\textsf{x}}{\textsf{\vdash}}$ and we
output $u_{\textsf{x}}$. Then we move to the position of the pebble, we pop
the pebble from the stack and we output $v_{\textsf{z},1}$. The input head is
now on the first occurrence of $\textsf{\dashv}_{\textsf{z}}$. We now check if
there is a further occurrence of $\prescript{}{\textsf{z}}{\textsf{\vdash}}$
to the right and, if not, we accept, and if yes, we place the pebble on this
occurrence of $\prescript{}{\textsf{z}}{\textsf{\vdash}}$. The pebble is now
on the position of the second occurrence of
$\prescript{}{\textsf{z}}{\textsf{\vdash}}$. We can now repeat this procedure
until there is no further occurrence of
$\prescript{}{\textsf{z}}{\textsf{\vdash}}$.

Algorithm 1 A for-transducer for the polyregular string-to-string function
$T_{2}$

1:procedure for-transducer for $T_{2}$($w$)

2: $B_{1}:=\mathsf{false}$

3: for $Z$ in $1..|w|$ do

4: if $w[Z]=\prescript{}{\textsf{z}}{\textsf{\vdash}}$ then

5: $B_{1}:=\mathsf{true}$

6: $B_{2}:=\mathsf{false}$

7: for $Y$ in $1..|w|$ do

8: if $w[Y]=\prescript{}{\textsf{y}}{\textsf{\vdash}}$ then
$B_{2}:=\mathsf{true}$

9: if $B_{2}$ and $w[Y]\in\widehat{\Sigma}$ then output $w[Y]$

10: if $B_{2}$ and $w[Y]=\textsf{\dashv}_{\textsf{y}}$ then
$B_{2}:=\mathsf{false}$

11: output ‘ ’

12: for $X$ in $1..|w|$ do

13: if $w[X]=\prescript{}{\textsf{x}}{\textsf{\vdash}}$ then
$B_{2}:=\mathsf{true}$

14: if $B_{2}$ and $w[X]\in\widehat{\Sigma}$ then output $w[X]$

15: if $B_{2}$ and $w[X]=\textsf{\dashv}_{\textsf{x}}$ then
$B_{2}:=\mathsf{false}$

16: output ‘$:$’

17: if $B_{1}$ and $w[Z]\in\widehat{\Sigma}$ then output $w[Z]$

18: if $w[Z]=\textsf{\dashv}_{\textsf{z}}$ then output ‘$\\#$’

##  Appendix C Proofs of Section 4

###  C.1 Proof of Theorem 4.1

We first need the following definitions.

We extend the encoding $\mathtt{enc}(\cdot)$ to multiref-words and multiref-
languages in a natural way. Let
$\mbox{$\mathcal{X}$}=\\{\textsf{x}_{1},\textsf{x}_{2},\ldots,\textsf{x}_{m}\\}$
with $\textsf{x}_{1}\preceq\textsf{x}_{2}\preceq\ldots\preceq\textsf{x}_{m}$.
A string $u\in\Gamma_{\mbox{$\mathcal{X}$}}^{*}$ is called a
_$\Gamma_{\mbox{$\mathcal{X}$}}$ -sequence_ if, for every $\ell\in[m]$, the
subsequence of the occurrences of
$\prescript{}{\textsf{x}_{\ell}}{\textsf{\vdash}}$ and of
$\textsf{\dashv}_{\textsf{x}_{\ell}}$ of $u$ has the form
$(\textsf{\dashv}_{\textsf{x}_{\ell}})^{o_{\ell}}(\prescript{}{\textsf{x}_{\ell}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}_{\ell}})^{e_{\ell}}(\prescript{}{\textsf{x}_{\ell}}{\textsf{\vdash}})^{c_{\ell}}$
for some $o_{\ell},c_{\ell}\in\\{0,1\\}$ and $e_{\ell}\geq 0$ (i. e., $u$ is
the factor of a valid multiref-word). Moreover, for every, $\ell\in[m]$, we
call
$(\textsf{\dashv}_{\textsf{x}_{\ell}})^{o_{\ell}}(\prescript{}{\textsf{x}_{\ell}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}_{\ell}})^{e_{\ell}}(\prescript{}{\textsf{x}_{\ell}}{\textsf{\vdash}})^{c_{\ell}}$
the _$\textsf{x}_{\ell}$ -sequence_ of $u$. For every
$\Gamma_{\mbox{$\mathcal{X}$}}$-sequence $u$ with $\textsf{x}_{\ell}$-sequence
$u_{\ell}=(\textsf{\dashv}_{\textsf{x}_{\ell}})^{o_{\ell}}(\prescript{}{\textsf{x}_{\ell}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}_{\ell}})^{e_{\ell}}(\prescript{}{\textsf{x}_{\ell}}{\textsf{\vdash}})^{c_{\ell}}$
for every $\ell\in[m]$, we define
$\mathtt{enc}(u_{\ell})=(\textsf{\dashv}_{\textsf{x}_{\ell}})^{o_{\ell}}(\prescript{}{\textsf{x}_{\ell}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}_{\ell}})^{e^{\prime}_{\ell}}(\prescript{}{\textsf{x}_{\ell}}{\textsf{\vdash}})^{c_{\ell}}$
where $e^{\prime}_{\ell}=0$ if $e_{\ell}=0$ and $e^{\prime}_{\ell}=1$
otherwise. And we define
$\mathtt{enc}(u)=\mathtt{enc}(u_{1})\mathtt{enc}(u_{2})\ldots\mathtt{enc}(u_{m})$.
Any $\Gamma_{\mbox{$\mathcal{X}$}}^{*}$-sequence $u$ is called _normalised_ ,
if $u=\mathtt{enc}(u)$. For any multiref-word $w=u_{1}b_{1}u_{2}b_{2}\ldots
u_{n}b_{n}u_{n+1}$ with $b_{i}\in\Sigma$ for every $i\in[n]$ and
$u_{j}\in\Gamma_{\mbox{$\mathcal{X}$}}^{*}$ for every $j\in[n+1]$, we set
$\mathtt{enc}(w)=\mathtt{enc}(u_{1})b_{1}\mathtt{enc}(u_{2})b_{2}\ldots\mathtt{enc}(u_{n})b_{n}\mathtt{enc}(u_{n+1})$.
It can be easily verified that, for every multi-refword $w$, we have that
$\mathtt{enc}(w)=\mathtt{enc}(\textsf{t}_{w},\mathbf{D}_{w})$. Finally, for
any multiref-language $L$, we set $\mathtt{enc}(L)=\\{\mathtt{enc}(w)\mid w\in
L\\}$.

The next lemma will be crucial for the proof.

######  Lemma C.1.

Given an NFA $M$ with $n$ states such that $\mathcal{L}(M)$ is a multiref-
language over $\Sigma$ and $\mathcal{X}$ with $|\mbox{$\mathcal{X}$}|=m$, and
every word of $\mathcal{L}(M)$ ends with a symbol of $\Sigma$. Then we can
construct a DFA $N$ with $\textsf{}(2^{2n+3m}|\Sigma|m)$ states and
$\mathcal{L}(N)=\mathtt{enc}(\mathcal{L}(M))$ in time
$\textsf{}(2^{2n+3m}|\Sigma|m)$.

###### Proof.

We first transform $M$ into an equivalent DFA $M_{1}$ with $\textsf{}(2^{n})$
states by standard constructions. Without loss of generality, we assume that
every state is reachable from the initial state, and every state can reach a
final state. In particular, this means that all strings over
$\Gamma_{\mbox{$\mathcal{X}$}}^{*}$ that can be read between two states must
be $\Gamma_{\mbox{$\mathcal{X}$}}$-sequences.

Next, we transform $M_{1}$ into a DFA $M_{2}$ that simulates $M_{1}$, but
whenever it has read some input $u\in\Gamma_{\mbox{$\mathcal{X}$}}^{*}$ or
some input with a suffix $bu\in\Sigma\Gamma_{\mbox{$\mathcal{X}$}}^{*}$, then
the current state stores $\mathtt{enc}(u)$, which we call the current
$\Gamma_{\mbox{$\mathcal{X}$}}$-sequence. This can be done by simply updating
the current $\Gamma_{\mbox{$\mathcal{X}$}}$-sequence after every transition of
a run. More precisely, let us assume that the current
$\Gamma_{\mbox{$\mathcal{X}$}}$-sequence is $u_{1}u_{2}\ldots u_{m}$ such
that, for every $\ell\in[m]$,
$u_{\ell}=(\textsf{\dashv}_{\textsf{x}_{\ell}})^{o_{\ell}}(\prescript{}{\textsf{x}_{\ell}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}_{\ell}})^{e_{\ell}}(\prescript{}{\textsf{x}_{\ell}}{\textsf{\vdash}})^{c_{\ell}}$
for some $o_{\ell},e_{\ell},c_{\ell}\in\\{0,1\\}$. If we read some symbol
$b\in\Sigma$, then we update the current
$\Gamma_{\mbox{$\mathcal{X}$}}$-sequence to $\textsf{\varepsilon}$. If we read
a symbol
$\gamma\in\\{\prescript{}{\textsf{x}_{\ell}}{\textsf{\vdash}},\textsf{\dashv}_{\textsf{x}_{\ell}}\\}$
for some $\ell\in[m]$, then we update the current
$\Gamma_{\mbox{$\mathcal{X}$}}$-sequence to
$u^{\prime}_{1}u^{\prime}_{2}\ldots u^{\prime}_{m}$, where
$u^{\prime}_{j}=u_{j}$ for every $j\in[m]\setminus\\{\ell\\}$, and
$u^{\prime}_{\ell}=\mathtt{enc}(u_{\ell}\gamma)$. Formally, we interpret the
states of $M_{2}$ as pairs $(p,u)$, where $p$ is a state of $M_{1}$ and $u$ is
some normalised $\Gamma_{\mbox{$\mathcal{X}$}}$-sequence. Moreover,
$(q_{0},\textsf{\varepsilon})$ is the initial state, where $q_{0}$ is
$M_{1}$’s initial state, and every state $(q_{f},u)$ is a final state if
$q_{f}$ is final in $M_{1}$. We observe that $M_{2}$ has
$\textsf{}(2^{n}8^{m})=\textsf{}(2^{n+3m})$ states, and $M_{2}$ can be
constructed in time $\textsf{}(2^{n+3m}(|\Sigma|+m))$. Also note that
$|M_{2}|=\textsf{}(2^{n+3m}(|\Sigma|+m))$. Obviously, $M_{2}$ is still
deterministic and accepts the same language $\mathcal{L}(M)$.

Then, we construct a directed and arc-labelled graph $G$ whose nodes are the
states from $M_{1}$. For each two states $(p_{1},\textsf{\varepsilon})$ and
$(p_{2},u)$ of $M_{2}$, we compute whether in $M_{2}$ there is some path from
$(p_{1},\textsf{\varepsilon})$ to $(p_{2},u)$ labelled with some sequence over
$\Gamma_{\mbox{$\mathcal{X}$}}$, or $p_{1}=p_{2}$ and
$u=\textsf{\varepsilon}$. This can be done by removing all
$\Sigma$-transitions from $M_{2}$ and then perform a breadth-first-search in
each state $(p,\textsf{\varepsilon})$. Hence, time
$\textsf{}(2^{n}|M_{2}|)=\textsf{}(2^{2n+3m}(|\Sigma|+m))$ is sufficient. For
all states $(p_{1},\textsf{\varepsilon})$ and $(p_{2},u)$ of $M_{2}$ such that
the latter is $\Gamma_{\mbox{$\mathcal{X}$}}$-reachable from the former, and
every transition $((p_{2},u),b,(p_{3},\textsf{\varepsilon}))$ of $M_{2}$ for
some $b\in\Sigma$, we add to $G$ a length-$(|ub|)$ path of new nodes (we call
these new nodes _path states_) from $p_{1}$ to $p_{3}$ such that this path is
labelled with $ub$ (note that this needs $|ub|-1=\textsf{}(m)$ new path
states). For this we have to consider each pair $(p_{1},p_{2})$ of states of
$M_{1}$, each normalised $\Gamma_{\mbox{$\mathcal{X}$}}$-sequence $u$, and
every outgoing $\Sigma$-arc from $(p_{2},u)$ in $M_{2}$ (which is
deterministic), and for each of those we have to add at $\textsf{}(m)$ new
path states. Hence, this can be done in time
$\textsf{}(2^{2n}2^{3m}|\Sigma|m)=\textsf{}(2^{2n+3m}|\Sigma|m)$. Furthermore,
the total number of nodes is also $\textsf{}(2^{2n+3m}|\Sigma|m)$.

We can now interpret $G$ as an NFA $M_{3}$, and it can be easily seen that
this NFA accepts $\mathtt{enc}(\mathcal{L}(M))$. As observed above, $M_{3}$
has $\textsf{}(2^{2n+3m}|\Sigma|m)$ states.

It remains to turn $M_{3}$ into a DFA $N$. To this end, we first observe that
it is possible that a non-path state $p$ has two different paths to some non-
path state $q$ that are both labelled with the same string $ub$. This can
happen, because in $M_{2}$ it is possible that we can go from
$(p,\textsf{\varepsilon})$ to a state $(p^{\prime},u)$, but with different
permutations $u_{1}$ and $u_{2}$ of $u$, and there is a transition
$((p^{\prime},u),b,(q,\textsf{\varepsilon}))$. We simply delete such
duplicates. Now, for every non-path state $p$ that has an outgoing path
labelled with $ub$ and a different outgoing path labelled with a different
$u^{\prime}b^{\prime}$, neither $ub$ is a proper prefix of
$u^{\prime}b^{\prime}$ nor $u^{\prime}b^{\prime}$ is a proper prefix of $ub$
(this is due to the fact that
$u,u^{\prime}\in\Gamma_{\mbox{$\mathcal{X}$}}^{*}$ and
$b,b^{\prime}\in\Sigma$). Consequently, for every fixed non-path state, we can
merge all its outgoing paths into a tree according to their common prefixes
and know that these paths will all necessarily branch off before they reach
their target state. The result is a determinised version of the NFA, which we
call $N$. This can be done in time $\textsf{}(2^{2n+3m}|\Sigma|m)$. We note
that we still have $\mathcal{L}(N)=\mathtt{enc}(\mathcal{L}(M))$ and $N$ has
$\textsf{}(2^{2n+3m}|\Sigma|m)$ states. ∎

We are now ready to prove Theorem 4.1, but we actually prove the following
slightly stronger result (which allows $E$ to be a regular multispanner
instead of only a regex multispanner). Note that the statement of Theorem 4.1
follows from the fact that any regular expression $r$ can be transformed into
an equivalent NFA of size $\textsf{}(|r|)$.

######  Theorem C.2.

Given a regular multispanner $E$ over $\Sigma$ (represented by an NFA with $n$
states), and a linear polyregular string-to-string function $T$ with input
alphabet $\Sigma\cup\Gamma_{\mbox{$\mathcal{X}$}}$ (represented by a DSST with
$h$ states), then we can construct an NSST $\mathcal{T}$ with
${\lsem{}{\mathcal{T}}\rsem}={\lsem{}{E\cdot T}\rsem}$ in time
$\textsf{}(2^{4n+9|\mbox{$\mathcal{X}$}|}|\Sigma|^{3}|\mbox{$\mathcal{X}$}|^{2}h^{2})$.

###### Proof.

Let us assume that
$\mbox{$\mathcal{X}$}=\\{\textsf{x}_{1},\textsf{x}_{2},\ldots,\textsf{x}_{m}\\}$
with $m\geq 1$ and
$\textsf{x}_{1}\preceq\textsf{x}_{2}\preceq\ldots\preceq\textsf{x}_{m}$. Let:

$\widetilde{\mathcal{T}}=(Q_{\widetilde{\mathcal{T}}},\Sigma,\Omega,\mathcal{R},\Delta_{\widetilde{\mathcal{T}}},I_{\widetilde{\mathcal{T}}},F_{\widetilde{\mathcal{T}}})$

be the DSST that represents $T$. Let $N$ be the NFA that describes $E$. We
assume that all multiref-words from $\mathcal{L}(N)$ end with a symbol from
$\Sigma$. This is without loss of generality: We extend $\Sigma$ by a dummy
symbol $\\#$ and change $N$ such that from every accepting state we can go
with $\\#$ to a new state, and we declare this new state to be the only
accepting state. Then we change $\widetilde{\mathcal{T}}$ such that it simply
interprets every input $w\\#$ as the input $w$.

By Lemma C.1, we can construct a DFA
$M=(Q_{M},\Sigma\cup\Gamma_{\mbox{$\mathcal{X}$}},q_{0,M},\delta_{M},F_{M})$
with $\textsf{}(2^{2n+3m}|\Sigma|m)$ states in time
$\textsf{}(2^{2n+3m}|\Sigma|m)$ that accepts $\mathtt{enc}(\mathcal{L}(N))$.
Without loss of generality, we assume that $M$ is such that every state can be
reached by the start state and every state can reach some accepting state
(note that this means that $M$ may be incomplete).

Since $M$ accepts $\mathtt{enc}(\mathcal{L}(N))$, we know that if $M$ reads an
input $u\in\Gamma_{\mbox{$\mathcal{X}$}}^{*}$ or an input with a suffix $bu$
with $b\in\Sigma$ and $u\in\Gamma_{\mbox{$\mathcal{X}$}}^{*}$, then $u$ is a
normalised $\Gamma_{\mbox{$\mathcal{X}$}}$-sequence.

We will now define an NSST
$\mathcal{T}=(Q_{\mathcal{T}},\Sigma,\Omega,\mathcal{R},\Delta_{\mathcal{T}},I_{\mathcal{T}},F_{\mathcal{T}})$
by combining $M$ and $\widetilde{\mathcal{T}}$.

Let us fix some notation for NSSTs with some input alphabet $A$ (and therefore
also for DSSTs). Obviously, we can interpret an NSST as a directed graph whose
arcs are labelled with pairs $(b,\sigma)$, where $b\in A$ and $\sigma$ is an
assignment. A _path_ from a state $q$ to a state $q^{\prime}$ in the NSST is
then any sequence

$p_{0},(b_{1},\sigma_{1}),p_{1},(b_{2},\sigma_{2}),p_{2},\ldots,(b_{k},\sigma_{k}),p_{k}\,,$

where $p_{i}$ is a state for every $i\in\\{0\\}\cup[k]$, $(b_{j},\sigma_{j})$
is the label of an arc from $p_{j-1}$ to $p_{j}$ for every $j\in[k]$, and
$p_{0}=q$ and $p_{k}=q^{\prime}$. Furthermore, $b_{1}b_{2}\ldots b_{k}$ is
called the _label_ of the path, and
$\sigma_{1}\circ\sigma_{2}\circ\ldots\circ\sigma_{k}$ is called the _composed
assignment_ of the path. We use analogous notions for NFAs and DFAs.

We define $Q_{\mathcal{T}}=Q_{M}\times Q_{\widetilde{\mathcal{T}}}$, we set
$I_{\mathcal{T}}((q_{0,M},p))=I_{\widetilde{\mathcal{T}}}(p)$ for every $p\in
Q_{\widetilde{\mathcal{T}}}$ with $I_{\widetilde{\mathcal{T}}}(p)$ defined
(otherwise $I_{\mathcal{T}}((q_{0,M},p))$ is undefined), we set
$F_{\mathcal{T}}((q_{f},p))=F_{\widetilde{\mathcal{T}}}(p)$ for every
$q_{f}\in F_{M}$ and for every $p\in Q_{\widetilde{\mathcal{T}}}$ with
$F_{\widetilde{\mathcal{T}}}(p)$ defined (otherwise
$F_{\mathcal{T}}((q_{f},p))$ is undefined). It remains to define
$\Delta_{\mathcal{T}}$, which we shall do next.

For every $p,p^{\prime}\in Q_{M}$, every $q,q^{\prime}\in
Q_{\widetilde{\mathcal{T}}}$, every $b\in\Sigma$ and every normalised
$\Gamma_{\mbox{$\mathcal{X}$}}$-sequence
$u\in(\Gamma_{\mbox{$\mathcal{X}$}})^{*}$ such that

  * •

in $M$ there is a path from $p$ to $p^{\prime}$ with label $ub$, and

  * •

in $\widetilde{\mathcal{T}}$ there is a path from $q$ to $q^{\prime}$ with
label $ub$ and some composed assignment $\sigma$,

we add the transition $((p,q),b,\sigma,(p^{\prime},q^{\prime}))$ to
$\Delta_{\mathcal{T}}$. This concludes the definition of $\mathcal{T}$.

In order to effectively construct $\Delta_{\mathcal{T}}$, we have to consider
all states $p,p^{\prime}\in Q_{N}$, $q,q^{\prime}\in
Q_{\widetilde{\mathcal{T}}}$, all $b\in\Sigma$ and all normalised
$\Gamma_{\mbox{$\mathcal{X}$}}$-sequences
$u\in(\Gamma_{\mbox{$\mathcal{X}$}})^{*}$. For each such tuple
$(p,p^{\prime},q,q^{\prime},b,u)$, the properties from above can be checked
(and $\sigma$ computed) in time
$\textsf{}(|ub|)=\textsf{}(|\mbox{$\mathcal{X}$}|)=\textsf{}(m)$, since in
each of $M$ and $\widetilde{\mathcal{T}}$ there is at most one path to
consider (recall that both $M$ and $\widetilde{\mathcal{T}}$ are
deterministic). Since there are $8^{m}$ different normalised
$\Gamma_{\mbox{$\mathcal{X}$}}$-sequences, we can construct
$\Delta_{\mathcal{T}}$ in time
$\textsf{}(2^{4n+9m}|\Sigma|^{3}m^{2}|Q_{\widetilde{\mathcal{T}}}|^{2})$.

Let $\mathbf{D}\in\Sigma^{*}$ be a document with $|\mathbf{D}|=k$. We have to
prove that ${\lsem{}{\mathcal{T}}\rsem}(\mathbf{D})={\lsem{}{E\cdot
T}\rsem}(\mathbf{D})$. We first need the following definition. A _condensed
run_ of $\widetilde{\mathcal{T}}$ on some input $u_{1}b_{1}u_{2}b_{2}\ldots
u_{k}b_{k}$ with $u_{i}\in\Gamma_{\mbox{$\mathcal{X}$}}^{*}$ and
$b_{i}\in\Sigma$ for every $i\in[k]$ is a sequence

$(q_{0},\nu_{0})\xrightarrow{u_{1}b_{1}/\sigma_{1}}(q_{1},\nu_{1})\xrightarrow{u_{2}b_{2}/\sigma_{2}}\ldots\xrightarrow{u_{k}b_{k}/\sigma_{k}}(q_{k},\nu_{k})$

where $q_{0},q_{1},\ldots,q_{k}$ are states with
$I_{\widetilde{\mathcal{T}}}(q_{0})$ and $F_{\widetilde{\mathcal{T}}}(q_{k})$
defined, and, for every $i\in[k]$, there is a run

$(q^{\prime}_{i,0},\nu^{\prime}_{i,0})\xrightarrow{c_{i,1}/\sigma^{\prime}_{i,1}}(q^{\prime}_{i,1},\nu^{\prime}_{i,1})\xrightarrow{c_{i,2}/\sigma^{\prime}_{i,2}}\ldots\xrightarrow{c_{i,k_{i}}/\sigma^{\prime}_{i,k_{i}}}(q^{\prime}_{i,k_{i}},\nu^{\prime}_{i,k_{i}})$

with $(q^{\prime}_{i,0},\nu^{\prime}_{i,0})=(q_{i-1},\nu_{i-1})$,
$(q^{\prime}_{i,k_{i}},\nu^{\prime}_{i,k_{i}})=(q_{i},\nu_{i})$,
$c_{i,1}c_{i,2}\ldots c_{i,k_{i}}=u_{i}b_{i}$, and
$\sigma^{\prime}_{i,1}\circ\sigma^{\prime}_{i,2}\circ\ldots\circ\sigma^{\prime}_{i,k_{i}}=\sigma_{i}$.

We start with showing
${\lsem{}{\mathcal{T}}\rsem}(\mathbf{D})\subseteq{\lsem{}{E\cdot
T}\rsem}(\mathbf{D})$. Let
$\mathbf{D}^{\prime}\in{\lsem{}{\mathcal{T}}\rsem}(\mathbf{D})$ and let

$\rho\ :=\
((p_{0},q_{0}),\nu_{0})\xrightarrow{\mathbf{D}[1]/\sigma_{1}}\ldots\xrightarrow{\mathbf{D}[n]/\sigma_{n}}((p_{k},q_{k}),\nu_{k})$

be an accepting run of $\mathcal{T}$ with
$\mathbf{D}^{\prime}=\textsf{out}(\rho)$. This also means that
$p_{0}=q_{M,0}$, $p_{k}\in F_{M}$,
$I_{\widetilde{\mathcal{T}}}(q_{0})\neq\bot$ and
$F_{\widetilde{\mathcal{T}}}(q_{k})\neq\bot$.

For every $i\in[m]$, let $u_{i}\in\Gamma_{\mbox{$\mathcal{X}$}}$ be the
normalised $\Gamma_{\mbox{$\mathcal{X}$}}$-sequence that is responsible for
the transition $((p_{i-1},q_{i-1}),\mathbf{D}[i],\sigma_{i},(p_{i},q_{i}))$,
i. e., $u_{i}$ is such that in $M$ there is a path from $p_{i-1}$ to $p_{i}$
with label $u_{i}\mathbf{D}[i]$, and in $\widetilde{\mathcal{T}}$ there is a
path from $q_{i-1}$ to $q_{i}$ with label $u_{i}\mathbf{D}[i]$ and with
composed assignment $\sigma_{i}$. Since $M$ and $\widetilde{\mathcal{T}}$ are
deterministic, for every $i\in[m]$ there is exactly one normalised
$\Gamma_{\mbox{$\mathcal{X}$}}$-sequence $u_{i}$ with these properties. Hence,
the $u_{1},u_{2},\ldots,u_{m}$ are uniquely defined.

Then, $w=u_{1}\mathbf{D}[1]u_{2}\mathbf{D}[2]\ldots u_{k}\mathbf{D}[k]$ is
accepted by $M$, and there is a condensed accepting run

$\rho^{\prime}\ :=\
(q_{0},\nu_{0})\xrightarrow{u_{1}\mathbf{D}[1]/\sigma_{1}}\ldots\xrightarrow{u_{n}\mathbf{D}[n]/\sigma_{n}}(q_{k},\nu_{n})$

of $\widetilde{\mathcal{T}}$ and
$\textsf{out}(\rho^{\prime})=\textsf{out}(\rho)=\mathbf{D}^{\prime}$. This
implies that $\textsf{t}_{w}\in E(\mathbf{D})$ and
$T(w)=T(\mathtt{enc}(\mathbf{D},\textsf{t}_{w}))=\mathbf{D}^{\prime}$; thus,
$\mathbf{D}^{\prime}\in{\lsem{}{E\cdot T}\rsem}$.

Moreover, each individual accepting run of $\mathcal{T}$ on input $\mathbf{D}$
with output $\mathbf{D}^{\prime}$ yields a distinct tuple
$(u_{1},u_{2},\ldots,u_{m})$ of normalised
$\Gamma_{\mbox{$\mathcal{X}$}}$-sequences, which means that there is a
distinct $t\in E(\mathbf{D})$ with
$T(\mathtt{enc}(\mathbf{D},t))=\mathbf{D}^{\prime}$. This is due to the fact
that two different accepting runs of $\mathcal{T}$ on input $\mathbf{D}$ with
output $\mathbf{D}^{\prime}$ can only differ in their states, which, since $M$
and $\widetilde{\mathcal{T}}$ are deterministic, means that for at leat one
$i\in[k]$, the two transitions of the different runs that read symbol
$\mathbf{D}[i]$ must be due to different normalised
$\Gamma_{\mbox{$\mathcal{X}$}}$-sequences.

Hence, for every $\mathbf{D}^{\prime}\in\Omega^{*}$, we have that
$\textsf{mult}_{{\lsem{}{\mathcal{T}}\rsem}(\mathbf{D})}(\mathbf{D}^{\prime})\leq\textsf{mult}_{{\lsem{}{E\cdot
T}\rsem}(\mathbf{D})}(\mathbf{D}^{\prime})$. This means that
${\lsem{}{\mathcal{T}}\rsem}(\mathbf{D})\subseteq{\lsem{}{E\cdot
T}\rsem}(\mathbf{D})$.

Now let us prove ${\lsem{}{E\cdot
T}\rsem}(\mathbf{D})\subseteq{\lsem{}{\mathcal{T}}\rsem}(\mathbf{D})$. To this
end, let $\mathbf{D}^{\prime}\in{\lsem{}{E\cdot T}\rsem}(\mathbf{D})$, which
means that there is a $t\in E(\mathbf{D})$ and
$\mathbf{D}^{\prime}=T(\mathtt{enc}(\mathbf{D},t))$. Let
$w=u_{1}\mathbf{D}[1]u_{2}\mathbf{D}[2]\ldots
u_{k}\mathbf{D}[k]=\mathtt{enc}(\mathbf{D},t)$. Since $M$ accepts
$\mathtt{enc}(\mathcal{L}(N))$, we know that $w\in\mathcal{L}(M)$. Let
$p_{0}=q_{0,M}$ and, for every $i\in[k]$, let $p_{i}$ be the state of $M$’s
accepting run after reading $u_{1}\mathbf{D}[1]\ldots u_{i}\mathbf{D}[i]$.
Furthermore, there must be a condensed accepting run

$\rho\ :=\
(q_{0},\nu_{0})\xrightarrow{u_{1}\mathbf{D}[1]/\sigma_{1}}\ldots\xrightarrow{u_{n}\mathbf{D}[n]/\sigma_{n}}(q_{k},\nu_{n})$

of $\widetilde{\mathcal{T}}$ and $\mathbf{D}^{\prime}$. Note that this means
that $I_{\widetilde{\mathcal{T}}}(q_{0})$ and
$F_{\widetilde{\mathcal{T}}(q_{k})}$ are defined, and that
$\textsf{out}(\rho)=\mathbf{D}^{\prime}$.

By definition, this means that $\mathcal{T}$ has a transition
$((p_{i-1},q_{i-1}),\mathbf{D}[i],\sigma_{i},(p_{i},q_{i}))$ for every
$i\in[k]$. Consequently, there is an accepting run

$\rho^{\prime}\ :=\
((p_{0},q_{0}),\nu_{0})\xrightarrow{\mathbf{D}[1]/\sigma_{1}}\ldots\xrightarrow{\mathbf{D}[n]/\sigma_{n}}((p_{k},q_{k}),\nu_{n})$

of $\mathcal{T}$. Furthermore,
$\textsf{out}(\rho^{\prime})=\textsf{out}(\rho)=\mathbf{D}^{\prime}$. This
implies that $\mathbf{D}^{\prime}\in{\lsem{}{\mathcal{T}}\rsem}(\mathbf{D})$.

Moreover, each distinct $t\in E(\mathbf{D})$ with
$\mathbf{D}^{\prime}=T(\mathtt{enc}(\mathbf{D},t))$ yields a distinct
multiref-word $w=u_{1}\mathbf{D}[1]u_{2}\mathbf{D}[2]\ldots
u_{k}\mathbf{D}[k]=\mathtt{enc}(\mathbf{D},t)$. Since $M$ and
$\widetilde{\mathcal{T}}$ are deterministic, this also yields a distinct
accepting run of $M$ on $w$ and a distinct accepting run of
$\widetilde{\mathcal{T}}$ on $w$, and therefore a distinct accepting run of
$\mathcal{T}$. Hence, for every $\mathbf{D}^{\prime}\in\Omega^{*}$, we have
that $\textsf{mult}_{{\lsem{}{E\cdot
T}\rsem}(\mathbf{D})}(\mathbf{D}^{\prime})\leq\textsf{mult}_{{\lsem{}{\mathcal{T}}\rsem}(\mathbf{D})}(\mathbf{D}^{\prime})$.
This means that ${\lsem{}{E\cdot
T}\rsem}(\mathbf{D})\subseteq{\lsem{}{\mathcal{T}}\rsem}(\mathbf{D})$.

∎

###  C.2 Proof of Theorem 4.2

We need the following definitions. Let
$\mathcal{T}=(Q,\Sigma,\Omega,\mathcal{R},\Delta,I,F)$ be an NSST. When
$\mathcal{T}$ is in a state $p\in Q$ and reads a symbol $b\in\Sigma$, then the
number of possible nondeterministic choices it can make is the sum over all
the multiplicities (recall that $\Delta$ is a bag) of elements
$(p,b,\sigma,q)\in\Delta$. We shall call this number the _nondeterministic
branching factor of $p$ and $b$_. More formally, we define
$\textsf{ndet}(p,b)=\sum_{(p,b,\sigma,q)\in\Delta}\textsf{mult}_{\Delta}((p,b,\sigma,q))$.
Furthermore, we define the _nondeterministic branching factor of
$\mathcal{T}$_ as $\textsf{ndet}(\mathcal{T})=\max_{p\in
Q,b\in\Sigma}\\{\textsf{ndet}(p,b)\\}$.

Now, let us restate Theorem 4.2 and prove it.

######  Theorem C.3.

Given an NSST $\mathcal{T}$ with $n$ states, input alphabet $\Sigma$ and
nondeterministic branching factor $m$, then we can construct a regex
multispanner $E$ over $\Sigma$ and variables
$\\{\textsf{x}_{1},\textsf{x}_{2},\ldots,\textsf{x}_{\max\\{n,m\\}}\\}$ and a
linear polyregular function $T$ with ${\lsem{}{E\cdot
T}\rsem}={\lsem{}{\mathcal{T}}\rsem}$. Moreover, $E$ is represented by a
multispanner-expression $r$ with $|r|=\textsf{}(|\Sigma|+\max\\{n,m\\})$, $T$
is represented by an DSST $\mathcal{T}^{\prime}$ with
$\textsf{}(\max\\{n,m\\}\cdot n)$ states, and both $r$ and
$\mathcal{T}^{\prime}$ can be constructed in time
$\textsf{}(|\mathcal{T}|+n\cdot\max\\{n,m\\}+|\Sigma|)$.

###### Proof.

Let $\mathcal{T}\ =\
(Q_{\mathcal{T}},\Sigma,\Omega,\mathcal{R}_{\mathcal{T}},\Delta_{\mathcal{T}},I_{\mathcal{T}},F_{\mathcal{T}})$.
For the sake of convenience, we represent the bag $\Delta_{\mathcal{T}}$ as
the set

$\displaystyle\widehat{\Delta}_{\mathcal{T}}=$
$\displaystyle\\{(p,b,\sigma,q,1),(p,b,\sigma,q,2),\ldots,$
$\displaystyle(p,b,\sigma,q,\textsf{mult}_{\Delta}((p,b,\sigma,q)))\mid(p,b,\sigma,q)\in\Delta_{\mathcal{T}}\\}\,.$

This is obviously an equivalent representation compared to the representation
by a surjective function that has a set of identifiers as domain.

Let us assume that, for every $q\in Q_{\mathcal{T}}$ and $b\in\Sigma$, we have
a numbering of all $\textsf{ndet}(p,b)$ transitions of the form
$(p,b,\sigma,q,\textsf{id})$, i. e., every transition
$(p,b,\sigma,q,\textsf{id})\in\widehat{\Delta}_{\mathcal{T}}$ has a unique
number $\pi((p,b,\sigma,q,\textsf{id}))\in[\textsf{ndet}(p,b)]$. Obviously,
$\pi((p,b,\sigma,q,\textsf{id}))\leq\textsf{ndet}(\mathcal{T})=m$ for every
transition $(p,b,\sigma,q,\textsf{id})\in\widehat{\Delta}_{\mathcal{T}}$. Such
a numbering can be easily constructed from $\widehat{\Delta}_{\mathcal{T}}$ in
time $\textsf{}(|\widehat{\Delta}_{\mathcal{T}}|)$.

We also extend the numbering $\pi$ to the states, i. e., every state $q\in Q$
has a unique number $\pi(q)\in[n]$.

Let

$\rho\ :=\
(q_{0},\nu_{0})\xrightarrow{b_{1}/\sigma_{1}}(q_{1},\nu_{1})\xrightarrow{b_{2}/\sigma_{2}}\ldots\xrightarrow{b_{k}/\sigma_{k}}(q_{k},\nu_{k})$

be a run of $\mathcal{T}$ on some input $b_{1}b_{2}\ldots b_{k}$. For every
$i\in[k]$, $\mathcal{T}$ reads symbol $b_{i}$ by a transition
$s_{i}=(q_{i-1},b_{i},\sigma_{i},q_{i},\textsf{id}_{i})\in\widehat{\Delta}_{\mathcal{T}}$,
which is one possible nondeterministic choice of the
$\textsf{ndet}(q_{i-1},b_{i})$ many possible transitions of the form
$(q_{i-1},b_{i},\sigma,p,\textsf{id})$. Moreover, the choice of the start
state $q_{0}$ with $I(q_{0})\neq\bot$ is another nondeterministic choice. We
can therefore uniquely represent the run $\rho$ of $\mathcal{T}$ on input
$b_{1}b_{2}\ldots b_{k}$ as a string from $[n]([m]\times\Sigma)^{*}$, namely
the string

$\pi(q_{0})(\pi(s_{1}),b_{1})(\pi(s_{2}),b_{2})\ldots(\pi(s_{k}),b_{k})\,.$

In the following, we call every string
$h^{\prime}(h_{1},b_{1})(h_{2},b_{2})\ldots(h_{k},b_{k})$ with
$h^{\prime}\in[n]$, $h_{i}\in[m]$ and $b_{i}\in\Sigma$ an _nd-annotation of
$b_{1}b_{2}\ldots b_{k}$_.

Let $w=h^{\prime}(h_{1},b_{1})(h_{2},b_{2})\ldots(h_{k},b_{k})$ be an nd-
annotation of $b_{1}b_{2}\ldots b_{k}$. We can now transform $w$ into a run
$\rho_{w}$ of $\mathcal{T}$ by the following procedure. We start in state
$q_{0}$ with $\pi(q_{0})=h^{\prime}$ if $I_{\mathcal{T}}(q_{0})$ is defined,
and interrupt otherwise. Then, for every $i=1,2,\ldots,k$, if we are currently
in a state $q_{i-1}$, then we extend the current run with the transition
$(q_{i-1},b_{i},\sigma_{i},q_{i},\textsf{id}_{i})$ with
$\pi((q_{i-1},b_{i},\sigma_{i},q_{i},\textsf{id}_{i}))=h_{i}$ next, or
interrupt if no such transition exist (which is the case if
$h_{i}>\textsf{ndet}(q_{i-1},b_{i})$).

We say that the nd-annotation $w$ of some input $b_{1}\ldots b_{k}$ is _valid_
, if it can be completely transformed into a run $\rho_{w}$ without
interrupting the procedure from above, and it is called _accepting_ , if it is
valid and $\rho_{w}$ is an accepting run.

It can be easily verified that for every $\mathbf{D}\in\Sigma^{*}$,

${\lsem{}{\mathcal{T}}\rsem}(\mathbf{D})=\\{\\!\\!\\{\textsf{out}(\rho_{w})\mid\text{$\rho$
is an accepting nd-annotation of $\mathbf{D}$}\\}\\!\\!\\}\,.$

Moreover, we can transform $\mathcal{T}$ into a DSST $\mathcal{T}^{\prime}$
with input alphabet $[\max\\{n,m\\}]\cup\Sigma$ that, for every
$\mathbf{D}\in\Sigma^{*}$, maps each accepting nd-annotation $w$ of
$\mathbf{D}$ to $\textsf{out}(\rho_{w})$. More precisely,
$\mathcal{T}^{\prime}$ simply carries out the run $\rho_{w}$ represented by
the input $w$ as described above. When the input $w$ is not a valid nd-
annotation, then $\mathcal{T}^{\prime}$ just stops and rejects. If $w$ is
valid but not accepting, then it rejects as well. If $\rho_{w}$ is accepting,
then $\mathcal{T}^{\prime}$ accepts and therefore outputs the element
$\textsf{out}(\rho_{w})$. In particular, note that if $\mathcal{T}$ has
several different accepting runs on $\mathbf{D}$ with the same output
$\mathbf{D}^{\prime}$, then $\mathcal{T}^{\prime}$ will also produce
$\mathbf{D}^{\prime}$ for each of the annotated inputs resulting from
$\mathcal{T}$’s different accepting runs.

We observe that $\mathcal{T}^{\prime}$ can simulate $\mathcal{T}$ in a
completely deterministic way, since the explicit annotations in the input
allow $\mathcal{T}^{\prime}$ to deterministically determine the transitions of
$\mathcal{T}$ that should be applied (or check whether the input is a valid
nd-annotation). Since $\mathcal{T}^{\prime}$ needs to store in its states the
number that precedes the next symbol of $\Sigma$ of the input, it needs
$\textsf{}(n\cdot\max\\{n,m\\})$ states. Furthermore, $\mathcal{T}^{\prime}$
can be constructed in time $\textsf{}(|\mathcal{T}|+n\cdot\max\\{n,m\\})$.

Let
$\mbox{$\mathcal{X}$}=\\{\textsf{x}_{1},\textsf{x}_{2},\ldots,\textsf{x}_{\max\\{n,m\\}}\\}$.
We represent nd-annotations as multiref-words over $\Sigma$ and $\mathcal{X}$
in the obvious way, i. e., in an nd-annotation, we simply represent every
number $i$ by the parentheses
$\prescript{}{\textsf{x}_{i}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}_{i}}$.
This obviously represents an nd-annotation as a normalised multiref-word.

Let us now define a multispanner-expression. For $i\in\mathbb{N}$, let
$r_{i}=(\prescript{}{\textsf{x}_{1}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}_{1}})+(\prescript{}{\textsf{x}_{2}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}_{2}})+\ldots+(\prescript{}{\textsf{x}_{i}}{\textsf{\vdash}}\textsf{\dashv}_{\textsf{x}_{i}})$,
let $r=r_{n}\cdot\big{(}r_{m}\cdot\Sigma\big{)}^{*}$. Obviously,
$\mathcal{L}(r)$ is the set of all possible nd-annotations for an input over
$\Sigma$ in the multiref-word interpretation explained above. Moreover,
$\mathtt{enc}(\mathcal{L}(r))=\mathcal{L}(r)$,
$|r|=\textsf{}(|\Sigma|+\max\\{m,n\\})$ and $r$ can be constructed in time
$\textsf{}(|\Sigma|+\max\\{m,n\\})$.

With our considerations from above, we can therefore conclude that
${\lsem{}{r\cdot\mathcal{T}^{\prime}}\rsem}(\mathbf{D})={\lsem{}{\mathcal{T}}\rsem}(\mathbf{D})$
for every $\mathbf{D}\in\Sigma^{*}$. ∎

##  Appendix D Proofs of Section 5

###  D.1 Proof of Proposition 5.2

###### Proof.

During this proof, the following notation will be useful. Let
$R\subseteq\mathcal{R}$ be a set of registers. For an assignment $\sigma$, we
denote by $\pi_{R}(\sigma)$ the restriction of $\sigma$ to $R$, namely,
$\textsf{dom}(\pi_{R}(\sigma))=\textsf{dom}(\sigma)\cap R$ and
$[\pi_{R}(\sigma)](X)=\sigma(X)$ for every $X\in\textsf{dom}(\sigma)\cap R$.

Let $\mathcal{T}=(Q,\Sigma,\Omega,\mathcal{R},\Delta,I,F)$ be an NSST, which
we will transform into an equivalent NSST that is garbage-free. The intuitive
idea is that we use states $(q,R)$ with $q\in Q$ and $R\subseteq\mathcal{R}$,
where $R$ simply stores the registers that are to be used by the next
assignment, i. e., $R=\textsf{reg}(\sigma)$, where $\sigma$ is the assignment
of the next transition. Moreover, to achieve garbage-freeness, $R$ must also
be the domain of the assignment of the previous transition that led to state
$(q,R)$. Consequently, if we move from state $(q,R)$ to
$(q^{\prime},R^{\prime})$, this must be done by a transition with an
assignment $\sigma$ that satisfies $R=\textsf{reg}(\sigma)$ and
$\textsf{dom}(\sigma)=R^{\prime}$. Note that for the next transition in a
computation, $R^{\prime}$ now plays the role of the registers to be used by
the next assignment $\sigma^{\prime}$, i. e.,
$R^{\prime}=\textsf{reg}(\sigma^{\prime})$, where $\sigma^{\prime}$ is the
assignment of the following transition. If we simulate $\mathcal{T}$ while
maintaining the sets $R$ of the states $(q,R)$ like described above, we
satisfy the requirement of garbage-freeness, and obtain an equivalent NSST.
Let us now define this formally.

Let
$\mathcal{T}^{\prime}=(Q^{\prime},\Sigma,\Omega,\mathcal{R},\Delta^{\prime},I^{\prime},F^{\prime})$
be an NSST such that $Q^{\prime}=Q\times\powerset(\mathcal{R})$,
$I^{\prime}((q,R))=\pi_{R}(I(q))$ whenever $I(q)\neq\bot$, and
$F^{\prime}((q,R))=F(q)$ iff $F(q)\neq\bot$ and $R=\textsf{reg}(F(q))$ for
every $(q,R)\in Q^{\prime}$. Furthermore, we will have that
$((q,R),a,\sigma,(q^{\prime},R^{\prime}))\in\Delta^{\prime}$ if, and only if,
there exists $(q,a,\tau,q^{\prime})\in\Delta$ such that
$\sigma=\pi_{R^{\prime}}(\tau)$, and $R=\textsf{reg}(\sigma)$. Furthermore, we
assume that each transition
$((q,R),a,\sigma,(q^{\prime},R^{\prime}))\in\Delta^{\prime}$ is repeated in
$\Delta^{\prime}$ as many times as transitions $(q,a,\tau,q^{\prime})$ exist
satisfying the above properties.

First, we notice that $\mathcal{T}^{\prime}$ is garbage-free. Indeed, consider
an accepting run:

$\rho\ :=\
((q_{0},R_{0}),\nu_{0})\xrightarrow{a_{1}/\sigma_{1}}((q_{1},R_{1}),\nu_{1})\xrightarrow{a_{2}/\sigma_{2}}\ldots\xrightarrow{a_{n}/\sigma_{n}}((q_{n},R_{n}),\nu_{n})$

of $\mathcal{T}^{\prime}$ over $a_{1}\ldots a_{n}$. One can easily prove by
induction that $\textsf{dom}(\nu_{i})=R_{i}$ for every $i\leq n$. Given that
$R_{i}=\textsf{reg}(\sigma_{i+1})$ by the definition of $\Delta^{\prime}$, we
conclude that $\textsf{dom}(\nu_{i})=\textsf{reg}(\sigma_{i+1})$. Furthermore,
given that $R_{n}=\textsf{reg}(F^{\prime}((q_{n},R_{n})))$ by the definition
of $F^{\prime}$, then
$\textsf{dom}(\nu_{n})=\textsf{reg}(F^{\prime}((q_{n},R_{n})))$ and we proved
that $\mathcal{T}^{\prime}$ is garbage-free.

Next, we show that $\mathcal{T}^{\prime}$ is equivalent to $\mathcal{T}$,
namely,
${\lsem{}{\mathcal{T}}\rsem}(w)={\lsem{}{\mathcal{T}^{\prime}}\rsem}(w)$ for
every string $w$. For one direction, let $\rho$ be an accepting run of
$\mathcal{T}$ over $a_{1}\ldots a_{n}$ of the form:

$\rho\ :=\
(q_{0},\nu_{0})\xrightarrow{a_{1}/\tau_{1}}(q_{1},\nu_{1})\xrightarrow{a_{2}/\tau_{2}}\ldots\xrightarrow{a_{n}/\tau_{n}}(q_{n},\nu_{n})$
(†)

Furthermore, let $R_{0},\ldots,R_{n}$ be sets of registers defined recursively
as follow: $R_{n}=\textsf{reg}(F(q_{n}))$ and for every $i<n$:
$R_{i}=\bigcup_{X\in R_{i+1}}\textsf{reg}(\sigma_{i+1}(X)).$ Then, we can
construct a run $\rho^{\prime}$ of $\mathcal{T}^{\prime}$ over $a_{1}\ldots
a_{n}$ such that:

$\rho^{\prime}\ :=\
((q_{0},R_{0}),\nu_{0}^{\prime})\xrightarrow{a_{1}/\sigma_{1}}((q_{1},R_{1}),\nu_{1}^{\prime})\xrightarrow{a_{2}/\sigma_{2}}\ldots\xrightarrow{a_{n}/\sigma_{n}}((q_{n},R_{n}),\nu_{n}^{\prime})$
(‡)

where $\sigma_{i}=\pi_{R_{i}}(\tau_{i})$ and
$\nu_{i}^{\prime}=\pi_{R_{i}}(\nu_{i})$ for every $i\leq n$. By construction,
we can verify that $\rho^{\prime}$ is an accepting run of
$\mathcal{T}^{\prime}$ over $a_{1}\ldots a_{n}$ and
$\nu_{n}(F(q_{n}))=\nu_{n}^{\prime}(F((q_{n},R_{n})))$. Conversely, we can
verify that if we have an accepting run $\rho^{\prime}$ of
$\mathcal{T}^{\prime}$ over $a_{1}\ldots a_{n}$ like († ‣ D.1), then we can
find the corresponding run $\rho$ of $\mathcal{T}$ over $a_{1}\ldots a_{n}$
like (‡ ‣ D.1). ∎

###  D.2 Proof of Proposition 5.3

###### Proof.

Let us assume that $\mathcal{T}$ is _trim_ , which means that every state can
be reached by some run, and every run can be extended to some accepting run
(by standard automata constructions, this is without loss of generality). We
also assume that, for every state $p\in Q$, if $I(p)$ is defined, then $p$ has
at least one outgoing transition, and if $F(p)$ is defined, then $p$ has at
least one incoming transition.

By definition, $\mathcal{T}$ is _not_ garbage-free if and only if there exists
an accepting run

$\rho\ :=\
((q_{0},R_{0}),\nu_{0})\xrightarrow{a_{1}/\sigma_{1}}((q_{1},R_{1}),\nu_{1})\xrightarrow{a_{2}/\sigma_{2}}\ldots\xrightarrow{a_{n}/\sigma_{n}}((q_{n},R_{n}),\nu_{n})$

such that one of the following properties is satisfied:

  1. $\textsf{dom}(\nu_{0})\neq\textsf{reg}(\sigma_{1})$.

  2. $\textsf{dom}(\nu_{i})\neq\textsf{reg}(\sigma_{i+1})$, for some $i$ with $0\leq i\leq n-1$.

  3. $\textsf{dom}(\nu_{n})\neq\textsf{reg}(F(q_{n}))$.

We observe that, by induction, this means that $\mathcal{T}$ is _not_ garbage-
free if and only if one of the following properties is satisfied:

  1. 1.

There is a transitions $(p,a,\sigma,q)\in\Delta$ such that $I(p)$ is defined
and $\textsf{dom}(I(p))\neq\textsf{reg}(\sigma)$.

  2. 2.

There are transitions $(p,a,\sigma_{1},q),(q,b,\sigma_{2},r)\in\Delta$ such
that $\textsf{dom}(\sigma_{1})\neq\textsf{reg}(\sigma_{2})$.

  3. 3.

There is a transition $(p,a,\sigma,q)\in\Delta$ such that $F(q)$ is defined
and $\textsf{dom}(\sigma)\neq\textsf{reg}(F(q))$.

For every state $p\in Q$, we say that $p$ is _reg-consistent_ if there are no
two outgoing transitions $(p,a,\sigma_{1},q),(p,b,\sigma_{2},r)\in\Delta$ with
$\textsf{reg}(\sigma_{1})\neq\textsf{reg}(\sigma_{2})$, and we say that $p$ is
_dom-consistent_ if there are no two incoming transitions
$(q,a,\sigma_{1},p),(r,b,\sigma_{2},p)\in\Delta$ with
$\textsf{dom}(\sigma_{1})\neq\textsf{dom}(\sigma_{2})$.

If there is a state that is not reg-consistent or not dom-consistent, then one
of the three properties from above is satisfied. Indeed, let us assume that
$p$ is not reg-consistent, which means that there are
$(p,a,\sigma_{1},q),(p,b,\sigma_{2},r)\in\Delta$ with
$\textsf{reg}(\sigma_{1})\neq\textsf{reg}(\sigma_{2})$. If $I(p)$ is defined,
then either $\textsf{dom}(I(p))\neq\textsf{reg}(\sigma_{1})$ or
$\textsf{dom}(I(p))\neq\textsf{reg}(\sigma_{2})$, which means that the first
property is satisfied. If $I(p)$ is not defined, then, since $\mathcal{T}$ is
trim, there must be at least one incoming transition
$(s,c,\sigma_{3},p)\in\Delta$. Thus,
$\textsf{dom}(\sigma_{3})\neq\textsf{reg}(\sigma_{1})$ or
$\textsf{dom}(\sigma_{3})\neq\textsf{reg}(\sigma_{2})$, which means that the
second property is not satisfied. On the other hand, if $p$ is not dom-
consistent, then there are $(q,a,\sigma_{1},p),(r,b,\sigma_{2},p)\in\Delta$
with $\textsf{dom}(\sigma_{1})\neq\textsf{dom}(\sigma_{2})$. Now if $F(p)$ is
defined, then $\textsf{dom}(\sigma_{1})\neq\textsf{reg}(F(p))$ or
$\textsf{dom}(\sigma_{2})\neq\textsf{reg}(F(p))$, which means that the third
property is satisfied. If $F(p)$ is not defined, then, since $\mathcal{T}$ is
trim, there must be at least one outgoing transition
$(p,c,\sigma_{3},s)\in\Delta$. Thus,
$\textsf{dom}(\sigma_{1})\neq\textsf{reg}(\sigma_{3})$ or
$\textsf{dom}(\sigma_{2})\neq\textsf{reg}(\sigma_{3})$, which means that the
second property is satisfied.

If all states are both reg-consistent and dom-consistent, then every state $p$
has a unique _reg-value_ $\mathsf{regv}(p)$ (i. e., the set
$\textsf{reg}(\sigma)$ for any transition $(p,a,\sigma,q)\in\Delta$, or
undefined if $p$ has no outgoing transition) and a unique _dom-value_
$\mathsf{domv}(p)$ (i. e., the set $\textsf{dom}(\sigma)$ for any transition
$(q,a,\sigma,p)\in\Delta$, or undefined if $p$ has no incoming transitions).

We can check whether every state is reg- and dom-consistent as follows. We
iterate through all transitions $(p,a,\sigma,q)\in\Delta$, and for each such
transition, we set $\mathsf{regv}(q)$ to $\textsf{reg}(\sigma)$ and we set
$\mathsf{domv}(p)$ to $\textsf{dom}(\sigma)$. Whenever we overwrite an already
set dom- or reg-value of a state with a _different_ dom- or reg-value, we have
discovered a state that is not dom- or not reg-consistent. Otherwise, all
states are dom- and reg-consistent and we have computed the values
$\mathsf{regv}(p)$ and $\mathsf{domv}(p)$ for every $p\in Q$. This requires
time $\textsf{}(|\Delta||\mathcal{R}|)$.

If all the states are indeed dom- and reg-consistent, then the only way of how
one of the three properties from above can be satisfied is that for some $p\in
Q$ we have that $I(p)$ is defined and $\textsf{dom}(I(p))\neq\mathsf{regv}(p)$
(note that, by assumption, $\mathsf{regv}(p)$ must be defined), or that $F(p)$
is defined and $\textsf{reg}(F(p))\neq\mathsf{domv}(p)$ (note that, by
assumption, $\mathsf{domv}(p)$ must be defined), or that both
$\mathsf{regv}(p)$ and $\mathsf{domv}(p)$ are defined, but
$\mathsf{regv}(p)\neq\mathsf{domv}(p)$.

Since we have already computed the values $\mathsf{regv}(p)$ and
$\mathsf{domv}(p)$ for every $p\in Q$, this can be checked in time
$\textsf{}(|Q||\mathcal{R}|)$.

Hence, we can check whether $\mathcal{T}$ is garbage-free in time
$\textsf{}(|\Delta||\mathcal{R}|)$. ∎

###  D.3 Proof of Theorem 5.1

In this subsection, we present an enumeration algorithm with linear-time
preprocessing for the problem $\textsc{EnumLinearET}[(E,T)]$. As stated
before, we can assume that $E$ is given by a regex multispanner and $T$ by a
DSST. Then, the algorithm starts by converting $(E,T)$ into an
$\mathcal{T}_{E,T}$ equivalent to $(E,T)$ by Theorem 4.1. For this reason, we
dedicate the rest of this subsection on the following enumeration problem. Let
$\mathcal{T}$ be an NSST.

Problem: $\textsc{EnumNSST}[\mathcal{T}]$ Input: A string $w\in\Sigma^{*}$
Output: Enumerate ${\lsem{}{\mathcal{T}}\rsem}(w)$

By Proposition 5.2, we can further assume that $\mathcal{T}$ is garbage-free.
We will use this property towards the end of this section, when we present the
final evaluation algorithm.

The rest of this section is as follows. We start by presenting the data
structure, called Enumerable Compact Set with Assignments. We continue by
showing how to enumerate the results from this data structure and the
conditions we need to enforce output-linear delay. Then, we present the
operations we use to extend and union results in the data structure. We end by
showing and analyzing the evaluation algorithm, using the data structure and
the garbage-free property.

#### The data structure

Let $\mathcal{R}$ be a finite set of registers and $\Omega$ a finite alphabet.
Recall that $\textsf{Asg}(\mathcal{R},\Omega)$ is the set of all copyless
assignment and $\textsf{Val}(\mathcal{R},\Omega)$ the set of all valuations,
both over $\mathcal{R}$ and $\Omega$. We say that
$\gamma\in\textsf{Asg}(\mathcal{R},\Omega)$ is a _relabel_ (or relabeling
assignment) iff it is a partial function
$\gamma:\mathcal{R}\rightharpoonup\mathcal{R}$. Note that, since a relabel
$\gamma$ must be copyless, then $\gamma$ just reassigns the content between
registers. We say that $\sigma$ is a _non-relabeling_ assignment if $\sigma$
is not a relabel. We usually denote $\sigma$ for an assignment, $\nu$ for a
valuation, and $\gamma$ for a relabeling.

We define a _Enumerable Compact Set with Assignments_ (ECSA) as a tuple:

$\mathcal{D}=(\mathcal{R},\Omega,\textsf{N},\ell,r,\lambda)$

such that N is a finite set of nodes,
$\ell\colon\textsf{N}\rightharpoonup\textsf{N}$ and
$r\colon\textsf{N}\rightharpoonup\textsf{N}$ are the left and right partial
functions, and