DI ENS, ENS, CNRS, PSL University, Paris, France and Inria, Paris,
<EMAIL_ADDRESS>A part of this work was done while affiliated with
IRIF – CNRS & Université de Paris, Paris, France, and with University of
Edinburgh, Edinburgh, UK. This work is supported by the Fondation des Sciences
Mathématiques de Paris (FSMP). Liat PeterfreundA full version of this paper is
available at https://arxiv.org/abs/2003.06880 [300]Information systems
Information extraction [300]Information systems Relational database model
[300]Information systems Data model extensions

###### Acknowledgements.

I would like to thank the anonymous reviewers for their extremely valuable
comments, and in particular those that enabled me to extend the enumeration
algorithm to a broader class of extraction grammars. I am grateful to Arnaud
Durand, Michael Kaminski, Benny Kimelfeld, and Leonid Libkin for useful
discussions, and to Dominik D. Freydenberger for references. Ke Yi and Zhewei
Wei 2 24th International Conference on Database Theory (ICDT 2021) ICDT 2021
ICDT 2021 March 23–26, 2021 Nicosia, Cyprus 186 5

# Grammars for Document Spanners

Liat Peterfreund

###### Abstract

We propose a new grammar-based language for defining information-extractors
from documents (text) that is built upon the well-studied framework of
document spanners for extracting structured data from text. While previously
studied formalisms for document spanners are mainly based on regular
expressions, we use an extension of context-free grammars, called extraction
grammars, to define the new class of context-free spanners. Extraction
grammars are simply context-free grammars extended with variables that capture
interval positions of the document, namely spans. While regular expressions
are efficient for tokenizing and tagging, context-free grammars are also
efficient for capturing structural properties. Indeed, we show that context-
free spanners are strictly more expressive than their regular counterparts. We
reason about the expressive power of our new class and present a pushdown-
automata model that captures it. We show that extraction grammars can be
evaluated with polynomial data complexity. Nevertheless, as the degree of the
polynomial depends on the query, we present an enumeration algorithm for
unambiguous extraction grammars that, after quintic preprocessing, outputs the
results sequentially, without repetitions, with a constant delay between every
two consecutive ones.

###### keywords:

Information Extraction, Document Spanners, Context-Free Grammars, Constant-
Delay Enumeration, Regular Expressions, Pushdown Automata.

##  1 Introduction

The abundance and availability of valuable textual resources in the last
decades position text analytics as a standard component in data-driven
workflows. One of the core operations that aims to facilitate the analysis and
integration of textual content is Information Extraction (IE), the extraction
of structured data from text. IE arises in a large variety of domains,
including social media analysis [4], health-care analysis [44], customer
relationship management [1], information retrieval [46], and more.

_Rules_ have always been a key component in various paradigms for IE, and
their roles have varied and evolved over the time. Systems such as Xlog [39]
and IBM’s SystemT [28, 6] use rules to extract relations from text (e.g.,
tokenizer, dictionary lookup, and part-of-speech tagger) that are further
manipulated with relational query languages. Other systems use rules to
generate features for machine-learning classifiers [27, 36].

Document Spanners. The framework of document spanners, presented by Fagin et
al., provides a theoretical basis for investigating the principles of
relational rule systems for IE [12]. The research on document spanners has
focused on their expressive power [12, 15, 35, 18, 33, 20] their computational
complexity [2, 14, 19, 34], incompleteness [30, 34], and other system aspects
such as cleaning [13], dynamic complexity [21], distributivity [8] and an
annotated variant [9].

x | y
---|---
$[1,2\rangle$ | $[2,3\rangle$
$[3,4\rangle$ | $[4,5\rangle$
$[3,4\rangle$ | $[4,6\rangle$
Figure 1:  Extracted relation

${S}\rightarrow B\vdash_{x}\mathtt{a}A\mathtt{b}\dashv_{y}B$
---
$A\rightarrow\mathtt{a}A\mathtt{b}\,\,\vline\,\,\dashv_{x}\vdash_{y}$
$B\rightarrow\mathtt{a}B\,\,\vline\,\,\mathtt{b}B\,\,\vline\,\,\epsilon$
Figure 2: Production rules

$\vdash_{x}\mathtt{a}\mathtt{a}\dashv_{x}\vdash_{y}\mathtt{b}\mathtt{b}\dashv_{y}\mathtt{b}$
---
$\mathtt{a}\mathtt{a}\vdash_{x}\mathtt{a}\mathtt{a}\dashv_{x}\vdash_{y}\mathtt{b}\mathtt{b}\dashv_{y}\mathtt{b}$
$\mathtt{a}\mathtt{a}\vdash_{x}\mathtt{a}\dashv_{x}\vdash_{y}\mathtt{b}\dashv_{y}\mathtt{b}$
Figure 3: Ref-words

In the documents spanners framework, a _document_ $\mathbf{d}$ is a string
over a fixed finite alphabet, and a _spanner_ is a function that extracts from
a document a relation over the spans of $\mathbf{d}$. A _span_ $x$ is a half-
open interval of positions of $\mathbf{d}$ and it represents a substring
$\mathbf{d}_{x}$ of $\mathbf{d}$ that is identified by these positions. A
natural way to specify a spanner is by a _regex formula_ : a regular
expression with embedded _capture variables_ that are viewed as relational
attributes. For instance, the spanner that is given by the regex formula
$(\mathtt{a}\vee\mathtt{b})^{*}\vdash_{x}\mathtt{a}\mathtt{a}^{*}\dashv_{x}\vdash_{y}\mathtt{b}\mathtt{b}^{*}\dashv_{y}(\mathtt{a}\vee\mathtt{b})^{*}$
extracts from documents spans $x$ and $y$ that correspond, respectively, with
a non-empty substring of $\mathtt{a}$’s followed by a non-empty substring of
$\mathtt{b}$’s. In particular, it extracts from the document
$\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{b}\mathtt{b}$ the relation depicted in
Figure 3.

The class of _regular spanners_ is the class of spanners definable as the
closure of regex formulas under positive relational algebra operations:
projection, natural join and union. The class of regular spanners can be
represented alternatively by finite state machines, namely _variable-set
automata (vset-automata)_ , which are nondeterministic finite-state automata
that can open and close variables (that, as in the case of regex formulas,
play the role of the attributes of the extracted relation). _Core_ spanners
[12] are obtained by extending the class of regular spanners with string-
equality selection on span variables. Although core spanners can express
strictly more than regular spanners, they are still quite limited as, e.g.,
there is no core spanner that extracts all pairs $x$ and $y$ of spans having
the same _length_ [12].

To date, most research on spanners has been focused on the regular
representation, that is, regular expressions and finite state automata. While
regular expressions are useful for segmentation and tokenization, they are not
useful in describing complex nested structures (e.g., syntactic structure of a
natural language sentence) and relations between different parts of the text.
Regular languages also fall short in dealing with tasks such as syntax
highlighting [31] and finding patterns in source code [40]. For all of the
above mentioned tasks we have context-free grammars. It is well known that
context-free languages are strictly more expressive than regular languages.
Büchi [5] has showed that regular languages are equivalent to monadic second
order logic (over strings), and Lautemann et al. [26] have showed that adding
an existential quantification over a binary relation interpreted as a matching
is enough to express all context-free languages. This quantification,
intuitively, is what makes it possible to also express structural properties.

Contribution. In this work we propose a new grammar-based approach for
defining the class of _context-free spanners_. Context-free spanners are
defined via _extraction grammars_ which, like regex formulas, incorporate
_capture variables_ that are viewed as relational attributes. Extraction
grammars produce _ref-words_ which are words over an extended alphabet that
consists of standard terminal symbols along with _variable operations_ that
denote opening and closing of variables. The result of evaluating an
extraction grammar on a document $\mathbf{d}$ is defined via the ref-words
that are produced by the grammar and equal to $\mathbf{d}$ after erasing the
variable operations. For example, the extraction grammar from Figure 3
produces also the ref-words
$\vdash_{x}\mathtt{a}\dashv_{x}\vdash_{y}\mathtt{b}\dashv_{y}\mathtt{a}\mathtt{b}\mathtt{b}$
and
$\mathtt{a}\mathtt{b}\vdash_{x}\mathtt{a}\dashv_{x}\vdash_{y}\mathtt{b}\dashv_{y}\mathtt{b}$.
Hence, it extracts from
$\mathbf{d}:=\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{b}\mathtt{b}$ the two first
tuples from the relation in Figure 3. In Figure 3 there are additional
examples of ref-words produced by this grammar. In general, the given grammar
extracts from documents the spans $x$ and $y$ that correspond, respectively,
with a non-empty substring of $\mathtt{a}$’s followed by an equal-length
substring of $\mathtt{b}$’s. With a slight adaptation of Fagin et al.
inexpressibility proof [12, Theorem 4.21], it can show that this spanner is
inexpressible by core spanners.

Indeed, we show that context-free spanners are strictly more expressive than
regular spanners and that the restricted class of regular extraction grammars
captures the regular spanners. We compare the expressiveness of context-free
spanners against core and generalized core spanners and show that context-free
spanners are incomparable to any of these classes. In addition to extraction
grammars, we present a pushdown automata model that captures the context-free
spanners.

In term of evaluation of context-free spanners we can evaluate extraction
grammars in polynomial time in _data complexity_ , where the spanner is
regarded as fixed and the document as input. However, as the degree of this
polynomial depends on the query (in particular, on the number of variables in
the relation it extracts), we propose an enumeration algorithm for unambiguous
extraction grammars. Our algorithm outputs the results consecutively, after
quintic preprocessing, with constant delay between every two answers. In the
first step of the preprocessing stage we manipulate the extraction grammar so
that it will be adjusted to the input document. In the second step of the
preprocessing we change it in a way that its non-terminals include extra
information on the variable operations. This extra information enables us to
skip sequences of productions that do not affect the output, hence obtaining a
delay that is independent of the input document and linear in the number of
variables associated with the spanner.

Related Work. Grammar-based parsers are widely used in IE systems [45, 38].
There are, as well, several theoretical frameworks that use grammars for IE,
one of which is Knuth’s framework of attribute grammars [24, 25]. In this
framework, the non-terminals of a grammar are attached with attributes111The
term “attributes” was previously used in the relational context; Here the
meaning is different. that pass semantic information up and down a parse-tree.
While both extraction grammars and attribute grammars extract information via
grammars, it seems as if the expressiveness of these formalisms is
incomparable to extraction grammars.

The problem of enumerating words of context-free grammars arises in different
contexts [42, 32]. Providing complexity guarantees on the enumeration is
usually tricky and requires assumptions either on the grammar or on the
output. Mäkinen [29] has presented an enumeration algorithm for regular
grammars and for unambiguous context-free grammars with additional
restrictions (strongly prefix-free and length complete). Later, Dömösi [10]
has presented an enumeration algorithm for unambiguous context-free grammars
that outputs, with quadratic delay, only the words of a fixed length.

Organization. In Section 2, we present extraction grammars and extraction
pushdown automata. In Section 3, we discuss the expressive power of context-
free spanners and their evaluation. In Sections 4 and 5, we present our
enumeration algorithm, and in Section 6 we conclude.

##  2 Context-Free Spanners

In this section we present the class of context-free spanners by presenting
two formalisms for expressing them: extraction grammars and extraction
pushdown automata.

###  2.1 Preliminaries

We start by presenting the formal setup based on notations and definitions
used in previous works on document spanners (e.g., [12, 19]).

Strings and Spans. We set an infinite set $\mathsf{Vars}$ of variables and fix
a finite alphabet $\Sigma$ that is disjoint of $\mathsf{Vars}$. In what
follows we assume that our alphabet $\Sigma$ consists of at least two letters.
A _document_ $\mathbf{d}$ is a finite sequence over $\Sigma$ whose length is
denoted by $|\mathbf{d}|$. A _span_ identifies a substring of $\mathbf{d}$ by
specifying its bounding indices. Formally, if
$\mathbf{d}=\sigma_{1}\cdots\sigma_{n}$ where $\sigma_{i}\in\Sigma$ then a
span of $\mathbf{d}$ has the form $[i,j\rangle$ where $1\leq i\leq j\leq n+1$
and $\mathbf{d}_{[i,j\rangle}$ denotes the substring
$\sigma_{i}\cdots\sigma_{j-1}$. When $i=j$ it holds that
$\mathbf{d}_{[i,j\rangle}$ equals the empty string, which we denote by
$\epsilon$. We denote by $\mathsf{Spans}(\mathbf{d})$ the set of all possible
spans of a document $\mathbf{d}$.

Document Spanners. Let $X\subseteq\mathsf{Vars}$ be a finite set of variables
and let $\mathbf{d}$ be a document. An $(X,\mathbf{d})$-mapping assigns spans
of $\mathbf{d}$ to variables in $X$. An $(X,\mathbf{d})$-relation is a finite
set of $(X,\mathbf{d})$-mappings. A _document spanner_ (or _spanner_ , for
short) is a function associated with a finite set $X$ of variables that maps
documents $\mathbf{d}$ into $(X,\mathbf{d})$-relations.

###  2.2 Extraction Grammars

The _variable operations_ of a variable $x\in\mathsf{Vars}$ are $\vdash_{x}$
and $\dashv_{x}$ where, intuitively, $\vdash_{x}$ denotes the opening of $x$,
and $\dashv_{x}$ its closing. For a finite subset $X\subseteq\mathsf{Vars}$,
we define the set $\Gamma_{X}:=\\{\vdash_{x},\dashv_{x}\,\,\vline\,\,x\in
X\\}$. That is, $\Gamma_{X}$ is the set that consists of all the variable
operations of all variables in $X$. We assume that $\Sigma$ and $\Gamma_{X}$
are disjoint. We extend the classical definition of context-free grammars [23]
by treating the variable operations as special terminal symbols. Formally, a
_context-free extraction grammar_ , or _extraction grammar_ for short, is a
tuple $G:=(X,V,{\Sigma},{P},{S})$ where

  * •

$X\subseteq\mathsf{Vars}$ is a finite set of variables,

  * •

$V$ is a finite set of _non-terminal_ symbols222Note that these are often
referred to as variables, however, here we use the term ‘non-terminals’ to
distinguish between these symbols and elements in $\mathsf{Vars}$.,

  * •

${\Sigma}$ is a finite set of _terminal_ symbols;

  * •

${P}$ is a finite set of _production rules_ of the form $A\rightarrow\alpha$
where $A$ is a non-terminal and $\alpha\in(V\cup\Sigma\cup\Gamma_{X})^{*}$,
and

  * •

$S$ is a designated non-terminal symbol referred to as the _start symbol_.

We say that the extraction grammar $G$ is _associated_ with $X$.

######  Example 2.1.

In this and in the following examples we often denote the elements in $V$ by
upper case alphabet letters from the beginning of the English alphabet
($A,B,C,\ldots$). Let $\Sigma=\\{\mathtt{a},\mathtt{b}\\}$, and let us
consider the grammar disjEqLen associated with the variables $\\{x,y\\}$ that
is given by the following production rules:

  * •

$S\rightarrow
B\vdash_{x}A\dashv_{y}B\,\,\,\vline\,\,\,B\vdash_{y}A\dashv_{x}B$

  * •

$A\rightarrow\mathtt{a}A\mathtt{a}\,\,\,\vline\,\,\,\mathtt{a}A\mathtt{b}\,\,\,\vline\,\,\,\mathtt{b}A\mathtt{b}\,\,\,\vline\,\,\,\mathtt{b}A\mathtt{a}$

  * •

$A\rightarrow\,\dashv_{x}B\vdash_{y}\,\,\,\vline\,\,\,\dashv_{y}B\vdash_{x}$

  * •

$B\rightarrow\epsilon\,\,\,\vline\,\,\,\mathtt{a}B\,\,\,\vline\,\,\,\mathtt{b}B$

Here and in what follows, we use the compact notation for production rules by
writing
$A\rightarrow\alpha_{1}\,\,\,\vline\,\,\,\cdots\,\,\,\vline\,\,\,\alpha_{n}$
instead of the productions
$A\rightarrow\alpha_{1},\cdots,A\rightarrow\alpha_{n}$. As we shall later see,
this grammar extracts pairs of disjoint spans with the same length. ∎

While classical context-free grammars generate words, extraction grammars
generate words over the extended alphabet $\Sigma\cup\Gamma_{X}$. These words
are referred to as _ref-words_ [37]. Similarly to (classical) context-free
grammars, the process of deriving ref-words is defined via the notations
$\Rightarrow,\Rightarrow^{n},\Rightarrow^{*}$ that stand for one, $n$, and
several (possibly zero) derivation steps, respectively. To emphasize the
grammar being discussed, we sometime use the grammar as a subscript (e.g.,
$\Rightarrow^{*}_{G}$). For the full definitions we refer the reader to
Hopcroft et al. [23]. A non-terminal $A$ is called _useful_ if there is some
derivation of the form $S\Rightarrow^{*}\alpha A\beta\Rightarrow^{*}w$ where
$w\in({\Sigma}\cup\Gamma_{X})^{*}$. If $A$ is not useful then it is called
_useless_. For complexity analysis, we define the _size_ $|G|$ of an
extraction grammar $G$ as the sum of the number of symbols at the right-hand
sides (i.e., to the right of $\rightarrow$) of its rules.

###  2.3 Semantics of Extraction Grammars

Following Freydenberger [16] we define the semantics of extraction grammars
using ref-words. A ref-word $\mathbf{r}\in(\Sigma\cup\Gamma_{X})^{*}$ is
_valid (for $X$)_ if each variable of $X$ is opened and then closed exactly
once, or more formally, for each $x\in X$ the string $\mathbf{r}$ has
precisely one occurrence of $\vdash_{x}$, precisely one occurrence of
$\dashv_{x}$, and the former is before (i.e., to the left of) the latter.

######  Example 2.2.

The ref-word
$\mathbf{r}_{1}:=\,\vdash_{x}\mathtt{a}\mathtt{a}\dashv_{y}\vdash_{x}\mathtt{a}\mathtt{b}\dashv_{y}$
is not valid for $\\{x,y\\}$ whereas the ref-words
$\mathbf{r}_{2}:=\,\vdash_{x}\mathtt{a}\mathtt{a}\dashv_{x}\vdash_{y}\mathtt{a}\mathtt{b}\dashv_{y}$
and
$\mathbf{r}_{3}:=\,\vdash_{y}\mathtt{a}\dashv_{y}\vdash_{x}\mathtt{a}\dashv_{x}\mathtt{a}\mathtt{b}$
are valid for $\\{x,y\\}$. ∎

To connect ref-words to terminal strings and later to spanners, we define a
morphism $\mathsf{clr}\colon(\Sigma\cup\Gamma_{X})^{*}\to\Sigma^{*}$ by
$\mathsf{clr}(\sigma):=\sigma$ for $\sigma\in\Sigma$, and
$\mathsf{clr}(\tau):=\epsilon$ for $\tau\in\Gamma_{X}$. For
$\mathbf{d}\in\Sigma^{*}$, let $\mathsf{Ref}(\mathbf{d})$ be the set of all
valid ref-words $\mathbf{r}\in(\Sigma\cup\Gamma_{X})^{*}$ with
$\mathsf{clr}(\mathbf{r})=\mathbf{d}$. By definition, every
$\mathbf{r}\in\mathsf{Ref}(\mathbf{d})$ has a unique factorization
$\mathbf{r}=\mathbf{r}_{x}^{\prime}\mathop{\cdot}\vdash_{x}\mathop{\cdot}\mathbf{r}_{x}\mathop{\cdot}\dashv_{x}\mathop{\cdot}\mathbf{r}_{x}^{\prime\prime}$
for each $x\in X$. With these factorizations, we interpret $\mathbf{r}$ as a
$(X,\mathbf{d})$-mapping $\mu^{\mathbf{r}}$ by defining
$\mu^{\mathbf{r}}(x):=[i,j\rangle$, where
$i:=|\mathsf{clr}(\mathbf{r}^{\prime}_{x})|+1$ and
$j:=i+|\mathsf{clr}(\mathbf{r}_{x})|$. An alternative way of understanding
$\mu^{\mathbf{r}}=[i,j\rangle$ is that $i$ is chosen such that $\vdash_{x}$
occurs between the positions in $\mathbf{r}$ that are mapped to $\sigma_{i-1}$
and $\sigma_{i}$, and $\dashv_{x}$ occurs between the positions that are
mapped to $\sigma_{j-1}$ and $\sigma_{j}$ (assuming that
$\mathbf{d}=\sigma_{1}\cdots\sigma_{|\mathbf{d}|}$, and slightly abusing the
notation to avoid a special distinction for the non-existing positions
$\sigma_{0}$ and $\sigma_{|\mathbf{d}|+1}$).

######  Example 2.3.

Let $\mathbf{d}=\mathtt{a}\mathtt{a}\mathtt{a}\mathtt{b}$. The ref-word
$\mathbf{r}_{2}$ from Example 2.2 is interpreted as the
$(\\{x,y\\},\mathbf{d})$-mapping $\mu^{\mathbf{r}_{2}}$ defined by
$\mu^{\mathbf{r}_{2}}(x):=[1,3\rangle$ and
$\mu^{\mathbf{r}_{2}}(y):=[3,5\rangle$. ∎

Extraction grammars define ref-languages which are sets of ref-words. The ref-
language $\mathcal{R}(G)$ of an extraction grammar $G:=(X,V,{\Sigma},{P},{S})$
is defined by
$\mathcal{R}(G):=\\{\mathbf{r}\in({\Sigma}\cup\Gamma_{X})^{*}\,\vline\,\,{S}\Rightarrow^{*}\mathbf{r}\\}\,.$
Note that we use $\mathcal{R}{(G)}$ instead of $\mathcal{L}{(G)}$ being used
for standard grammars, to emphasize that the produced language is a ref-
language. (We also use $\mathcal{L}{(G)}$ when $G$ is a standard grammar.) To
illustrate the definition let us consider the following example.

######  Example 2.4.

Both ref-words $\mathbf{r}_{1}$ and $\mathbf{r}_{2}$ from Example 2.2 are in
$\mathcal{R}(\text{\sc{disjEqLen}})$ where disjEqLen is the grammar described
in Example 2.1. Producing both $\mathbf{r}_{1}$ and $\mathbf{r}_{2}$ starts
similarly with the sequence:
${S}\Rightarrow\,B\vdash_{x}A\dashv_{y}B\,\Rightarrow^{2}\,\vdash_{x}A\dashv_{y}\,\Rightarrow\,\vdash_{x}\mathtt{a}A\mathtt{b}\dashv_{y}\,\Rightarrow\,\vdash_{x}\mathtt{a}\mathtt{a}A\mathtt{a}\mathtt{b}\dashv_{y}$.
The derivation of $\mathbf{r}_{1}$ continues with
$\Rightarrow\,\vdash_{x}\mathtt{a}\mathtt{a}\dashv_{y}B\vdash_{x}\mathtt{a}\mathtt{b}\dashv_{y}\,\Rightarrow\,\vdash_{x}\mathtt{a}\mathtt{a}\dashv_{y}\vdash_{x}\mathtt{a}\mathtt{b}\dashv_{y}$
whereas that of $\mathbf{r}_{2}$ continues with
$\Rightarrow\,\vdash_{x}\mathtt{a}\mathtt{a}\dashv_{x}B\vdash_{y}\mathtt{a}\mathtt{b}\dashv_{y}\,\Rightarrow\,\vdash_{x}\mathtt{a}\mathtt{a}\dashv_{x}\vdash_{y}\mathtt{a}\mathtt{b}\dashv_{y}$.
∎

We denote by $\mathsf{Ref}(G)$ the set of all ref-words in $\mathcal{R}(G)$
that are valid for $X$. Finally, we define the set
$\mathsf{Ref}(G,\mathbf{d})$ of ref-words in $\mathsf{Ref}(G)$ that
$\mathsf{clr}$ maps to $\mathbf{d}$. That is,
$\mathsf{Ref}(G,\mathbf{d}):=\mathsf{Ref}(G)\cap\mathsf{Ref}(\mathbf{d})\,.$
The result of evaluating the spanner $\llbracket{G}\rrbracket$ on a document
$\mathbf{d}$ is then defined as

$\llbracket{G}\rrbracket(\mathbf{d}):=\\{\mu^{\mathbf{r}}\,\,\vline\,\,\mathbf{r}\in\mathsf{Ref}(G,\mathbf{d})\\}\,.$

######  Example 2.5.

Let us consider the document
$\mathbf{d}:=\mathtt{a}\mathtt{a}\mathtt{b}\mathtt{a}$. The grammar disjEqLen
maps $\mathbf{d}$ into a set of $(\\{x,y\\},\mathbf{d})$-mappings, amongst are
$\mu^{\mathbf{r}_{2}}$ that is defined by
$\mu^{\mathbf{r}_{2}}(x):=[1,3\rangle$ and
$\mu^{\mathbf{r}_{2}}(y):=[3,5\rangle$ and $\mu^{\mathbf{r}_{3}}$ that is
defined by $\mu^{\mathbf{r}_{3}}(x):=[2,3\rangle$ and
$\mu^{\mathbf{r}_{3}}(y):=[1,2\rangle$. It can be shown that the grammar
disjEqLen maps every document $\mathbf{d}$ into all possible
$(\\{x,y\\},\mathbf{d})$-mappings $\mu$ such that $\mu(x)$ and $\mu(y)$ are
disjoint (i.e., do not overlap) and have the same length (i.e.,
$|\mathbf{d}_{\mu(x)}|=|\mathbf{d}_{\mu(y)}|$). ∎

A spanner $S$ is said to be _definable_ by an extraction grammar $G$ if
$S(\mathbf{d})=\llbracket{G}\rrbracket(\mathbf{d})$ for every document
$\mathbf{d}$.

######  Definition 2.6.

A _context-free spanner_ is a spanner definable by an extraction grammar.

###  2.4 Extraction Pushdown Automata

An _extraction pushdown automaton_ , or _extraction $\mathsf{PDA}$_, is
associated with a finite set $X\subseteq\mathsf{Vars}$ of variables and can be
viewed as a standard pushdown automata over the extended alphabet
$\Sigma\cup\Gamma_{X}$. Formally, an _extraction $\mathsf{PDA}$_ is a tuple
$A:=(X,Q,\Sigma,\Delta,\delta,q_{0},Z,F)$ where $X$ is a finite set of
variables; $Q$ is a finite set of states; $\Sigma$ is the input alphabet;
$\Delta$ is a finite set which is called _the stack alphabet_ ; $\delta$ is a
mapping
$Q\times\big{(}\Sigma\cup\\{\epsilon\\}\cup\Gamma_{X}\big{)}\times\Delta\rightarrow
2^{Q\times\Delta^{*}}$ which is called the _transition function_ ; $q_{0}\in
Q$ is the _initial state_ ; $Z\in\Delta$ is the _initial stack symbol_ ; and
$F\subseteq Q$ is the set of _accepting states_. Indeed, extraction
$\mathsf{PDA}$s run on ref-words (i.e., finite sequences over
$\Sigma\cup\Gamma_{X}$), as opposed to classical $\mathsf{PDA}$s whose input
are words (i.e., finite sequences over $\Sigma$). Similarly to classical
$\mathsf{PDA}$s, the computation of extraction $\mathsf{PDA}$s can be
described using sequences of configurations: a _configuration_ of $A$ is a
triple $(q,w,\gamma)$ where $q$ is the state, $w$ is the remaining input, and
$\gamma$ is the stack content such that the top of the stack is the left end
of $\gamma$ and its bottom is the right end. We use the notation
${\vdash}^{*}$ similarly to how it is used in the context of $\mathsf{PDA}$s
[22] and define the ref-language $\mathcal{R}{(A)}$:

$\mathcal{R}{(A)}:=\\{\mathbf{r}\in({\Sigma}\cup\Gamma_{X})^{*}\,\,\vline\,\,\exists\alpha\in\Delta^{*},q_{f}\in
F:(q_{0},\mathbf{r},Z)\vdash^{*}(q_{f},\epsilon,\alpha)\\}\,.$

We denote the language of $A$ by $\mathcal{R}(A)$ to emphasize that it is a
ref-language, and denote by $\mathsf{Ref}(A)$ the set of all ref-words in
$\mathcal{R}(A)$ that are valid for $X$. The result of evaluating the spanner
$\llbracket{A}\rrbracket$ on a document $\mathbf{d}$ is then defined as

$\llbracket{A}\rrbracket(\mathbf{d}):=\\{\mu^{\mathbf{r}}\,\,\vline\,\,\mathbf{r}\in\mathsf{Ref}(A)\cap\mathsf{Ref}(\mathbf{d})\\}\,.$

######  Example 2.7.

We define the extraction $\mathsf{PDA}$ that maps a document $\mathbf{d}$ into
the set of $(\\{x,y\\},\mathbf{d})$-mappings $\mu$ where $\mu(x)$ ends before
$\mu(y)$ starts and their lengths are the same. The stack alphabet consists of
the bottom symbol $\bot$ and $C$, and the transition function $\delta$ is
described in Figure 5 where a transition from state $q$ to state $q^{\prime}$
that is labeled with $\tau,A/\ \gamma$ denotes that the automaton moves from
state $q$ to state $q^{\prime}$ upon reading $\tau$ with $A$ at the top of the
stack, while replacing $A$ with $\gamma$. We can extend the automaton in a
symmetric way such that it will represent the same spanner as that represented
by the grammar disjEqLen from Example 2.1. ∎

We say that a spanner $S$ is _definable_ by an extraction $\mathsf{PDA}$ $A$
if for every document $\mathbf{d}$ it holds that
$\llbracket{A}\rrbracket(\mathbf{d})=S(\mathbf{d})$. Treating the variable
operations as terminal symbols enables us to use the equivalence of
$\mathsf{PDA}$s and context-free grammars and conclude the following
straightforward observation.

######  Proposition 2.8.

The class of spanners definable by extraction grammars is equal to the class
of spanners definable by extraction PDAs.

Thus, we have also an automata formalism for defining context-free spanners.

$q_{0}$$q_{x}$$q_{xy}$$q_{y}$$q_{f}$$\scriptstyle{\vdash_{x},C/\
C}$$\scriptstyle{\dashv_{x},C/\ C}$$\scriptstyle{\vdash_{y},C/\
C}$$\scriptstyle{\dashv_{y},\bot/\ \bot}$$\scriptstyle{\Sigma,\bot/\
\bot}$$\scriptstyle{\Sigma,\bot/\ \bot}$$\scriptstyle{\Sigma,C/\
CC}$$\scriptstyle{\Sigma,C/\ C}$$\scriptstyle{\Sigma,C/\ \epsilon}$ Figure 4:
Transition function of Example 2.7

$\scriptsize{S\rightarrow
B\vdash_{x}A_{1}\dashv_{y}B\,\,\,\vline\,\,\,B\vdash_{y}A_{2}\dashv_{x}B}$
---
$\scriptsize{A_{i}\rightarrow\mathtt{a}A_{i}\mathtt{a}\,\,\,\vline\,\,\mathtt{a}A_{i}\mathtt{b}\,\,\,\vline\,\,\,\mathtt{b}A_{i}\mathtt{b}\,\,\,\vline\,\,\,\mathtt{b}A_{i}\mathtt{a},\,\,i=1,2}$
$\scriptsize{A_{1}\rightarrow\,\dashv_{x}B\vdash_{y}}$ ,
$\scriptsize{A_{2}\rightarrow\,\dashv_{y}B\vdash_{x}}$
$\scriptsize{B\rightarrow\epsilon\,\,\,\vline\,\,\,\mathtt{a}B\,\,\,\vline\,\,\,\mathtt{b}B}$
Figure 5: Productions of Example 2.9

###  2.5 Functional Extraction Grammars

Freydenberger and Holldack [17] have presented the notion of _functionality_
in the context of regular spanners. We now extend it to extraction grammars.
The intuition is that interpreting an extraction grammar as a spanner
disregards ref-words that are not valid. We call an extraction grammar $G$
_functional_ if every ref-word in $\mathcal{R}(G)$ is valid.

######  Example 2.9.

The grammar disjEqLen in our running example is not functional. Indeed, we saw
in Example 2.4 that the ref-word $\mathbf{r}_{1}$, although it is not valid,
is in $\mathcal{R}(\text{\sc{disjEqLen}})$. We can, however, simply modify the
grammar to obtain an equivalent functional one. Notice that the problem arises
due to the production rules $S\rightarrow B\vdash_{x}A\dashv_{y}B$ and
$S\rightarrow B\vdash_{y}A\dashv_{x}B$. For the non-terminal $A$ we have
$A\Rightarrow^{*}\mathbf{r}_{1}$ where $\mathbf{r}_{1}$ contains both
$\dashv_{x}$ and $\vdash_{y}$, and we also have
$A\Rightarrow^{*}\mathbf{r}_{2}$ where $\mathbf{r}_{2}$ contains both
$\dashv_{y}$ and $\vdash_{x}$. To fix that, we can replace the non-terminal
$A$ with two non-terminals, namely $A_{1}$ and $A_{2}$, and change the
production rules so that for every ref-word $\mathbf{r}$, if
$A_{1}\Rightarrow^{*}\mathbf{r}$ then $\mathbf{r}$ contains both $\dashv_{x}$
and $\vdash_{y}$, and if $A_{2}\Rightarrow^{*}\mathbf{r}$ then $\mathbf{r}$
contains both $\dashv_{y}$ and $\vdash_{x}$. It can be shown that the grammar
$G$ whose production rules appear in Figure 5 is functional and that
$\llbracket{G}\rrbracket=\llbracket{\text{\sc{disjEqLen}}}\rrbracket$. ∎

######  Proposition 2.10.

Every extraction grammar $G$ can be converted into an equivalent functional
extraction grammar $G^{\prime}$ in $O(|G|^{2}+3^{2k}|G|)$ time where $k$ is
the number of variables $G$ is associated with.

Inspired by Chomsky’s hierarchy, we say that an extraction grammar is in
_Chomsky Normal Form (CNF)_ if it is in CNF when viewed as a grammar over the
extended alphabet $\Sigma\cup\Gamma_{X}$. We remark that, in Proposition 2.10,
$G^{\prime}$ is in CNF.

###  2.6 Unambiguous Extraction Grammars

A grammar $G$ is said to be unambiguous if every word it produces has a unique
parse-tree. We extend this definition to extraction grammars. An extraction
grammar $G$ is said to be _unambiguous_ if for every document $\mathbf{d}$ and
every $(X,\mathbf{d})$-mapping $\mu\in\llbracket{G}\rrbracket(\mathbf{d})$ it
holds that there is a unique ref-word $\mathbf{r}$ for which
$\mu^{\mathbf{r}}=\mu$ and this ref-word has a unique parse-tree. Unambiguous
extraction grammars are less expressive than their ambiguous counterparts as
the Boolean case shows – unambiguous context-free grammars are less expressive
than ambiguous context-free grammars [23].

######  Example 2.11.

The extraction grammar given in Example 2.9 is not unambiguous since it
produces the ref-words $\vdash_{x}\dashv_{x}\vdash_{y}\dashv_{y}$ and
$\vdash_{y}\dashv_{y}\vdash_{x}\dashv_{x}$ that correspond to the same
mapping. It can be shown that replacing the derivation $B\rightarrow\epsilon$
with $B\rightarrow\mathtt{a}\,\,\vline\,\,\mathtt{b}$ results in an
unambiguous extraction grammar which is equivalent to disjEqLen on any
document different than $\epsilon$. (Note however that this does not imply
that the ref-languages both grammars produce are equal.) ∎

Our main enumeration algorithm for extraction grammars relies on unambiguity
and the following observation.

######  Proposition 2.12.

In Proposition 2.10, if $G$ is unambiguous then so is $G^{\prime}$.

##  3 Expressive Power and Evaluation

In this section we compare the expressiveness of context-free spanners
compared to other studied classes of spanners and discuss its evaluation
shortly.

###  3.1 Regular Spanners

A _variable-set automaton_ $A$ (or _vset-automaton_ , for short) is a tuple
$A:=(X,Q,q_{0},q_{f},\delta)$ where $X\subseteq\mathsf{Vars}$ is a finite set
of variables also referred to as $\mathsf{Vars}(A)$, $Q$ is the set of
_states_ , $q_{0},q_{f}\in Q$ are the _initial_ and the _final_ states,
respectively, and $\delta\colon
Q\times(\Sigma\cup\\{\epsilon\\}\cup\Gamma_{X})\to 2^{Q}$ is the _transition
function_. To define the semantics of $A$, we interpret $A$ as a non-
deterministic finite state automaton over the alphabet $\Sigma\cup\Gamma_{X}$,
and define $\mathcal{R}(A)$ as the set of all ref-words
$\mathbf{r}\in(\Sigma\cup\Gamma_{X})^{*}$ such that some path from $q_{0}$ to
$q_{f}$ is labeled with $\mathbf{r}$. Like for regex formulas, we define
$\mathsf{Ref}(A,\mathbf{d})=\mathcal{R}(A)\cap\mathsf{Ref}(\mathbf{d})$ and
finally we define for every document $\mathbf{d}\in\Sigma^{*}$:
$\llbracket{A}\rrbracket(\mathbf{d}):=\\{\mu^{\mathbf{r}}\,\,\vline\,\,\mathbf{r}\in\mathsf{Ref}(A,\mathbf{d})\\}.$
The class of _regular spanners_ equals the class of spanners that are
expressible as a vset-automaton [12].

Inspired by Chomsky’s hierarchy, we say that an extraction grammar $G$ is
_regular_ if its productions are of the form $A\rightarrow\sigma B$ and
$A\rightarrow\sigma$ where $A,B$ are non-terminals and
$\sigma\in(\Sigma\cup\Gamma_{X})$. We then have the following equivalence that
is strongly based on the equivalence of regular grammars and finite state
automata.

######  Proposition 3.1.

The class of spanners definable by regular extraction grammars is equal to the
class of regular spanners.

###  3.2 (Generalized) Core Spanners

An alternative way to define regular spanners is based on the notion of regex
formulas: Formally, a _regex formula_ is defined recursively by
$\alpha:=\hskip
3.5pt\emptyset\mid\epsilon\mid\sigma\mid\alpha\vee\alpha\mid\alpha\cdot\alpha\mid\alpha^{*}\mid\,\vdash_{x}\alpha\dashv_{x}$
where $\sigma\in\Sigma$ and $x\in\mathsf{Vars}$. We denote the set of
variables whose variable operations occur in $\alpha$ by
$\mathsf{Vars}(\alpha)$, and interpret each regex formula $\alpha$ as a
generator of a ref-word language $\mathcal{R}(\alpha)$ over the extended
alphabet $\Sigma\cup\Gamma_{\mathsf{Vars}(\alpha)}$. For every document
$\mathbf{d}\in\Sigma^{*}$, we define
$\mathsf{Ref}(\alpha,\mathbf{d})=\mathcal{R}(\alpha)\cap\mathsf{Ref}(\mathbf{d})$,
and the spanner $\llbracket{\alpha}\rrbracket$ by
$\llbracket{\alpha}\rrbracket(\mathbf{d}):=\\{\mu^{\mathbf{r}}\,\,\vline\,\,\mathbf{r}\in\mathsf{Ref}(\alpha,\mathbf{d})\\}$.
The class of regular spanners is then defined as the closure of regex formulas
under the relational algebra operators: union, projection and natural join.
(See full definitions in [12].)

In their efforts to capture the core of AQL which is IBM’s SystemT query
language, Fagin et al. [12] have presented the class of core spanners which is
the closure of regex formulas under the positive operators, i.e., union,
natural join and projection, along with the string equality selection that is
defined as follows Let $S$ be a spanner and let $x,y\in\mathsf{Vars}(S)$, the
_string equality selection_ $\zeta^{=}_{x,y}S$ is defined by
$\mathsf{Vars}(\zeta^{=}_{x,y}S)=\mathsf{Vars}(S)$ and, for all
$\mathbf{d}\in\Sigma^{*}$, $\zeta^{=}_{x,y}S(\mathbf{d})$ is the set of all
$\mu\in S(\mathbf{d})$ where $\mathbf{d}_{\mu(x)}=\mathbf{d}_{\mu(y)}$. Note
that unlike the join operator that joins mappings that have identical spans in
their shared variables, the selection operator compares the substrings of
$\mathbf{d}$ that are described by the spans, and does not distinguish between
different spans that span the same substrings.

The class of _generalized core spanners_ is obtained by adding the difference
operator. That is, it is defined as the closure of regex formulas under union,
natural join, projection, string equality, and difference. We say that two
classes $\mathcal{S},\mathcal{S}^{\prime}$ of spanners are _incomparable_ if
both $\mathcal{S}\setminus\mathcal{S}^{\prime}$ and
$\mathcal{S}^{\prime}\setminus\mathcal{S}$ are not empty.

######  Proposition 3.2.

The classes of core spanners and generalized core spanners are each
incomparable with the class of context-free spanners.

We conclude the discussion by a straightforward result on closure properties.

######  Proposition 3.3.

The class of context-free spanners is closed under union and projection, and
not closed under natural join and difference.

###  3.3 Evaluating Context-Free Spanners

The _evaluation_ problem of extraction grammars is that of computing
$\llbracket{G}\rrbracket(\mathbf{d})$ where $\mathbf{d}$ is a document and $G$
is an extraction grammar. Our first observation is the following.

######  Proposition 3.4.

For every extraction grammar $G$ and every document $\mathbf{d}$ it holds that
$\llbracket{G}\rrbracket(\mathbf{d})$ can be computed in
$O(|G|^{2}+|\mathbf{d}|^{2k+3}\,k^{3}\,|G|)$ time where $k$ is the number of
variables $G$ is associated with.

The proof of this proposition is obtained by iterating through all valid ref-
words and using the Cocke-Younger-Kasami (CYK) parsing algorithm [23] to check
whether the current valid ref-word is produced by $G$. We can, alternatively,
use Valiant’s parser [41] and obtain
$O(|G|^{2}+|\mathbf{d}|^{2k+\omega}\,k^{\omega}\,|G|)$ where $\omega<2.373$ is
the matrix multiplication exponent [43].

While the evaluation can be done in polynomial time in data complexity (where
$G$ is regarded as fixed and $\mathbf{d}$ as input), the output size might be
quite big. To be more precise, for an extraction grammar $G$ associated with
$k$ variables, the output might consist of up to $|\mathbf{d}|^{2k}$ mappings.
Instead of outputting these mappings altogether, we can output them
sequentially (without repetitions) after some preprocessing.

Our main enumeration result is the following.

######  Theorem 3.5.

For every unambiguous extraction grammar $G$ and every document $\mathbf{d}$
there is an algorithm that outputs the mappings in
$\llbracket{G}\rrbracket(\mathbf{d})$ with delay $O(k)$ after
$O(|\mathbf{d}|^{5}|G|^{2}3^{4k})$ preprocessing where $k$ is the number of
variables $G$ is associated with.

Our algorithm consists of two main stages: preprocessing and enumeration. In
the preprocessing stage, we manipulate the extraction grammar and do some
precomputations which are later exploited in the enumeration stage in which we
output the results sequentially. We remark that unambiguity is crucial for the
enumeration stage as it allows to output the mappings without repetition.

Through the lens of data complexity, our enumeration algorithm outputs the
results with constant delay after quintic preprocessing. That should be
contrasted with regular spanners for which there exists a constant delay
enumeration algorithm whose preprocessing is linear [2, 14]. In the following
sections, we present the enumeration algorithm and discuss its correctness but
before we deal with the special case $\mathbf{d}:=\epsilon$. In this case,
$\llbracket{G}\rrbracket(\mathbf{d})$ is either empty or contains exactly one
mapping (since, by definition, the document $\epsilon$ has exactly one span,
namely $[1,1\rangle$). Notice that $\llbracket{G}\rrbracket(\mathbf{d})$ is
empty if and only if $G$ does not produce a ref-word that consists only of
variable operations. To check this, it suffices to change the production rules
of $G$ by replacing every occurrence of $\tau\in\Gamma_{X}$ with $\epsilon$,
and checking whether the new grammar produces $\epsilon$. This can be done in
linear time [22], which completes the proof of this case. From now on it is
assumed that $\mathbf{d}\neq\epsilon$.

##  4 Preprocessing of the Enumeration Algorithm

Due to Propositions 2.10 and 2.12, we can assume that our unambiguous
extraction grammar is functional and in CNF. As this conversion requires
$O(3^{2k}|G|^{2})$, it can be counted as part of our preprocessing.

The preprocessing stage consists of two steps: in the first we adjust the
extraction grammar to a given document and add subscripts to non-terminals to
track this connection, and in the second we use superscripts to capture extra
information regarding the variable operations.

###  4.1 Adjusting the Extraction Grammar to $\mathbf{d}$

Let ${G}:=(X,V,{\Sigma},{P},{S})$ be an extraction grammar in CNF, and let
$\mathbf{d}:=\sigma_{1}\cdots,\sigma_{n},n\geq 1$ be a document. The goal of
this step is to restrict $G$ so that it will produce only the ref-words which
$\mathsf{clr}$ maps to $\mathbf{d}$. To this end, we define the grammar
$G_{\mathbf{d}}$ that is associated with the same set $X$ of variables as $G$,
and is defined as follows:

  * •

The non-terminals are $\\{A_{i,j}\,\,\vline\,\,A\in V,\,1\leq i\leq j\leq
n\\}\cup\\{A_{\epsilon}\,\,\vline\,\,A\in V\\}$,

  * •

the terminals are $\Sigma$,

  * •

the initial non-terminal is $S_{1,n}$, and

  * •

the production rules are defined as follows:

    * –

$A_{i,i}\rightarrow\sigma_{i}$ for any $A\rightarrow\sigma_{i}\in{P}$,

    * –

$A_{\epsilon}\rightarrow\sigma$ for any $A\rightarrow\sigma\in{P}$ with
$\sigma\in\Gamma_{X}$,

    * –

$A_{\epsilon}\rightarrow B_{\epsilon}C_{\epsilon}$ for any $A\rightarrow
BC\in{P}$,

    * –

$A_{i,j}\rightarrow B_{i,j}C_{\epsilon}$ for any $1\leq i\leq j\leq n$ and any
$A\rightarrow BC\in{P}$,

    * –

$A_{i,j}\rightarrow B_{\epsilon}C_{i,j}$ for any $1\leq i\leq j\leq n$ and any
$A\rightarrow BC\in{P}$,

    * –

$A_{i,j}\rightarrow B_{i,i^{\prime}}C_{i^{\prime}+1,j}$ for any $1\leq i\leq
i^{\prime}<j\leq n$ and $A\rightarrow BC\in{P}$.

We eliminate useless non-terminals from $G_{\mathbf{d}}$ and by a slight abuse
of notation refer to the result as $G_{\mathbf{d}}$ from now on. The intuition
behind this construction is that if the subscript of a non-terminal is $i,j$
then this non-terminal produces a ref-word that $\mathsf{clr}$ maps to
$\sigma_{i}\cdots\sigma_{j}$, and if it is $\epsilon$ then it produces a ref-
word that consists only of variable operations.

######  Example 4.1.

Figure 9 presents a possible parse-tree of a grammar $G_{\mathbf{d}}$. ∎

We establish the following connection between $G$ and $G_{\mathbf{d}}$.

######  Lemma 4.2.

For every extraction grammar $G$ in CNF, every document
$\mathbf{d}:=\sigma_{1}\cdots\sigma_{n}$, every non-terminal $A$ of $G$, and
every ref-word $\mathbf{r}\in(\Sigma\cup\Gamma_{X})^{*}$ with
$\mathsf{clr}(\mathbf{r})=\sigma_{i}\cdots\sigma_{j}$ the following holds:
$A\Rightarrow_{G}^{*}\mathbf{r}$ if and only if
$A_{i,j}\Rightarrow_{G_{\mathbf{d}}}^{*}\mathbf{r}$

This allows us to conclude the following straightforward corollary.

######  Corollary 4.3.

For every extraction grammar $G$ in CNF and for every document $\mathbf{d}$,
it holds that $\mathsf{Ref}(G,\mathbf{d})=\mathcal{L}(G_{\mathbf{d}})$.

We note that adjusting our extraction grammar to $\mathbf{d}$ is somewhat
similar to the CYK algorithm [23] and therefore it is valid on extraction
grammars $G$ in CNF. For a similar reason, we obtain the following complexity
which is cubic in $|\mathbf{d}|$.

######  Proposition 4.4.

For every extraction grammar $G$ in CNF and for every document $\mathbf{d}$,
it holds that $G_{\mathbf{d}}$ can be constructed in
$O({|\mathbf{d}|}^{3}|G|)$.

Can the complexity of the adjustment be improved? We leave this as an open
question. We note, however, that it might be possible to use similar ideas
used by Earley’s algorithm [11] to decrease the complexity of this step.

###  4.2 Constructing the Decorated Grammar

The goal of this step of the preprocessing is to encode the information on the
produced variable operations within the terminals and non-terminals. We obtain
from $G_{\mathbf{d}}$, constructed in the previous step, a new grammar, namely
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$, that produces _decorated words_ over
the alphabet
$\\{(\mathbf{x},i,\mathbf{y})\,\,\vline\,\,\mathbf{x},\mathbf{y}\subseteq\Gamma_{X},1\leq
i\leq n\\}$. A terminal $(\mathbf{x},i,\mathbf{y})$ indicates that
$\mathbf{x}$ and $\mathbf{y}$ are variable operations that occur right before
and right after $\sigma_{i}$, respectively. (Notice that
$\mathbf{x},\mathbf{y}$ does not necessarily contain all of these variable
operations as some of the variable operations that appear, e.g., after $i$,
can be contained in $\mathbf{x}^{\prime}$ in case
$(\mathbf{x}^{\prime},i+1,\mathbf{y}^{\prime})$ is the terminal that appears
right after $(\mathbf{x},i,\mathbf{y})$.) This information is propagated also
to the non-terminals such that a non-terminal with a superscript
$\mathbf{x},\mathbf{y}$ indicates that $\mathbf{x}$ and $\mathbf{y}$ are
variable operations at the beginning and end, respectively, of the sub
decorated word produced by this non-terminal. Non-terminals with subscript
$\epsilon$ are those that produce sequences of variable operations.

To define $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$, we need $G$ to be
functional. The following key observation is used in the formal definition of
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ and is based on the functionality of
$G$.

######  Proposition 4.5.

For every functional extraction grammar $G$ and every non-terminal $A$ of $G$
there is a set $\mathbf{x}_{A}\subseteq\Gamma_{X}$ of variable operations such
that for every ref-word $\mathbf{r}$ where $A\Rightarrow^{*}\mathbf{r}$ the
variable operations that appear in $\mathbf{r}$ are exactly those in
$\mathbf{x}_{A}$. Computing all sets $\mathbf{x}_{A}$ can be done in $O(|G|)$.

In other words, for functional extraction grammars, the information on the
variable operations is stored implicitly in the non-terminals. The grammar
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ is defined in three steps as we now
describe.

Step 1. We set the following production rules for all subsets
$\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w}\subseteq\Gamma_{X}$ that are
pairwise disjoint:

  * •

$A^{\emptyset,\emptyset}_{i,i}\rightarrow\sigma_{i}$ for every rule
$A_{i,i}\rightarrow\sigma_{i}$ in $G_{\mathbf{d}}$,

  * •

$A_{\epsilon}\rightarrow\epsilon$ for every rule $A_{\epsilon}\rightarrow\tau$
in $G_{\mathbf{d}}$ (with $\tau\in\Gamma_{X}$),

  * •

$A_{\epsilon}\rightarrow B_{\epsilon}C_{\epsilon}$ for every rule
$A_{\epsilon}\rightarrow B_{\epsilon}C_{\epsilon}$ in $G_{\mathbf{d}}$,

  * •

$A^{\mathbf{x},\mathbf{y}\cup\mathbf{x}_{C}}_{i,j}\rightarrow
B^{\mathbf{x},\mathbf{y}}_{i,j}C_{\epsilon}$ for every rule
$A_{i,j}\rightarrow B_{i,j}C_{\epsilon}$ in $G_{\mathbf{d}}$ and
$\mathbf{x}\cap\mathbf{x}_{C}=\mathbf{y}\cap\mathbf{x}_{C}=\emptyset$,

  * •

$A^{\mathbf{x}\cup\mathbf{x}_{B},\mathbf{y}}_{i,j}\rightarrow
B_{\epsilon}C^{\mathbf{x},\mathbf{y}}_{i,j}$ for every rule
$A_{i,j}\rightarrow B_{\epsilon}C_{i,j}$ in $G_{\mathbf{d}}$ and
$\mathbf{x}\cap\mathbf{x}_{B}=\mathbf{y}\cap\mathbf{x}_{B}=\emptyset$,

  * •

$A^{\mathbf{x},\mathbf{w}}_{i,j}\rightarrow
B^{\mathbf{x},\mathbf{y}}_{i,i^{\prime}}C^{\mathbf{z},\mathbf{w}}_{i^{\prime}+1,j}$
for every rule $A_{i,j}\rightarrow B_{i,i^{\prime}}C_{i^{\prime}+1,j}$ in
$G_{\mathbf{d}}$ and pairwise disjoint
$\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w}$,

with $\mathbf{x}_{B}$ and $\mathbf{x}_{C}$ defined as in Proposition 4.5.

Step 2. We process the resulting grammar by three standard operations [23] in
the following order: $(i)$ we eliminate useless non-terminals (i.e., those
that do not produce a terminal string or are not reachable from the initial
non-terminal), $(ii)$ we eliminate epsilon-productions, and $(iii)$ we
eliminate unit productions (i.e., rules of the form $A\rightarrow B$ were
$A,B$ are non-terminals). We elaborate on $(iii)$ as it is important for the
sequel. To eliminate unit productions we compute for each non-terminal the set
of non-terminals that are reachable from it by unit productions only. That is,
we say that a non-terminal $B$ is _reachable_ form non-terminal $A$ if there
is a sequence of unit productions of the form $A_{1}\rightarrow
A_{2},\ldots,A_{n-1}\rightarrow A_{n}$ with $A_{1}=A$ and $A_{n}=B$. We then
replace every production $B\rightarrow\alpha$ which is not a unit production
with $A\rightarrow\alpha$, and after that discard all unit productions.

Step 3. The last step of the construction is adding a fresh start symbol $S$
and adding the production rules $S\rightarrow S_{1,n}^{\mathbf{x},\mathbf{y}}$
for every non-terminal of the form $S_{1,n}^{\mathbf{x},\mathbf{y}}$. We also
replace each production of the form
$A_{i,i}^{\mathbf{x},\mathbf{y}}\rightarrow\sigma_{i}$ with
$A_{i,i}^{\mathbf{x},\mathbf{y}}\rightarrow(\mathbf{x},i,\mathbf{y})$. This
can be viewed as a ‘syntactic sugar’ since it is only intended to help us
formulate easily the connection between the grammar $G$ and
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$.

######  Example 4.6.

Figures 9 and 9 illustrate the different steps in the construction of the
decorated grammar $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$. For simplicity, we
present the superscripts as pairs of sequences (each represent elements in the
set) separated by commas ‘,’. ∎

$\scriptstyle{A_{1,2}}$$\scriptstyle{B_{1,1}}$$\scriptstyle{D_{1,1}}$$\scriptstyle{H_{\epsilon}}$$\vdash_{x}$$\scriptstyle{I_{1,1}}$$\sigma_{1}$$\scriptstyle{E_{\epsilon}}$$\scriptstyle{J_{\epsilon}}$$\dashv_{x}$$\scriptstyle{K_{\epsilon}}$$\vdash_{y}$$\scriptstyle{C_{2,2}}$$\scriptstyle{F_{\epsilon}}$$\dashv_{y}$$\scriptstyle{G_{2,2}}$$\sigma_{2}$
Figure 6:  After the adjustment to $\mathbf{d}$

$\scriptstyle{A_{1,2}^{\vdash_{x},\emptyset}}$$\scriptstyle{B_{1,1}^{\vdash_{x},\dashv_{x}\vdash_{y}}}$$\scriptstyle{D_{1,1}^{\vdash_{x},\emptyset}}$$\scriptstyle{I_{1,1}^{\emptyset,\emptyset}}$${\sigma_{1}}$$\scriptstyle{C_{2,2}^{\dashv_{y},\emptyset}}$$\scriptstyle{G_{2,2}^{\emptyset,\emptyset}}$${\sigma_{2}}$
Figure 7:  Before step 2 $(iii)$

$\scriptstyle{A_{1,2}^{\vdash_{x},\emptyset}}$$\scriptstyle{B^{\vdash_{x},\dashv_{x}\vdash_{y}}_{1,1}}$$\scriptstyle{(\vdash_{x},1,\dashv_{x}\vdash_{y})}$$\scriptstyle{C^{\dashv_{y},\emptyset}_{2,2}}$$\scriptstyle{(\dashv_{y},2,\emptyset)}$
Figure 8:  After step 3

$\scriptstyle{S^{\emptyset,\emptyset}_{1,n}}$$\scriptstyle{A_{1,1}^{\emptyset,\emptyset}}$$\scriptstyle{B_{2,n}^{\emptyset,\emptyset}}$$\scriptstyle{C_{2,2}^{\emptyset,\emptyset}}$$\scriptstyle{\cdots}$$\scriptstyle{E_{n-2,n-2}^{\emptyset,\emptyset}}$$\scriptstyle{F^{\emptyset,\emptyset}_{n-1,n}}$$\scriptstyle{G^{\emptyset,\vdash_{x}\dashv_{x}}_{n-1,n-1}}$$\scriptstyle{G_{n,n}^{\emptyset,\emptyset}}$
Figure 9:  Non-stable non-terminals

Note that by a simple induction it can be shown that the resulting grammar
does no longer contain non-terminals of the form $A_{\epsilon}$. We denote the
resulting grammar and its set of non-terminals by
$\text{\sc{decorGrmr}}({G}_{\mathbf{d}})$ and $V^{\text{\sc{dec}}}$,
respectively.

The $(X,d)$-mapping $\mu^{w}$ that corresponds with
$w:=(\mathbf{x}_{1},1,\mathbf{y}_{1})\cdots(\mathbf{x}_{n},n,\mathbf{y}_{n})$
(which is a decorated word produced by
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$) is defined by
$\mu^{w}(x)=[i,j\rangle$ where
$\vdash_{x}\in\mathbf{x}_{i}\cup\mathbf{y}_{i-1}$ and
$\dashv_{x}\in\mathbf{x}_{j}\cup\mathbf{y}_{j-1}$ with
$\mathbf{y}_{0}=\mathbf{x}_{n+1}=\emptyset$. We say that a decorated word $w$
is _valid_ if $\mu^{w}(x)$ is well-defined for every $x\in X$.

######  Proposition 4.7.

For every functional extraction grammar $G$ in CNF and for every document
$\mathbf{d}$, if $G$ is unambiguous then
$\text{\sc{decorGrmr}}({G}_{\mathbf{d}})$ is unambiguous.

This allows us to establish the following connection between
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ and
$\llbracket{G}\rrbracket(\mathbf{d})$.

######  Lemma 4.8.

For every functional unambiguous extraction grammar $G$ in CNF and for every
document $\mathbf{d}$, every decorated word produced by
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ is valid and

$\llbracket{G}\rrbracket(\mathbf{d})=\\{\mu^{w}\,\,\vline\,\,S\Rightarrow^{*}_{\text{\sc{decorGrmr}}(G_{\mathbf{d}})}w\\}.$

Finally, combining Proposition 4.7 and Lemma 4.8 leads to the following direct
corollary.

######  Corollary 4.9.

For every functional unambiguous extraction grammar $G$ in CNF and for every
document $\mathbf{d}$, enumerating mappings in
$\llbracket{G}\rrbracket(\mathbf{d})$ can be done by enumerating parse-trees
of decorated words in
$\\{w\,\,\vline\,\,S\Rightarrow^{*}_{\text{\sc{decorGrmr}}(G_{\mathbf{d}})}w\\}$.

To summarize the complexity of constructing
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ we have:

######  Proposition 4.10.

For every functional unambiguous extraction grammar $G$ in CNF and for every
document $\mathbf{d}$, $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ can be
constructed in $O(|G_{\mathbf{d}}|\,5^{2k})=O({|\mathbf{d}|}^{3}|G|\,5^{2k})$
where $k$ is the number of variables associated with $G$.

##  5 Enumeration Algorithm

Our enumeration algorithm builds recursively the parse-trees of the decorated
grammar $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$. Before presenting it, we
discuss some of the main ideas that allow us to obtain a constant delay
between every two consecutive outputs.

###  5.1 Stable non-terminals

The non-terminals of $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ are decorated
with superscripts and subscripts that give extra information that can be
exploited in the process of the derivation.

######  Example 5.1.

Figure 11 presents a partial parse-tree (without the leaves and the first
production) for a decorated word in $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$.
Notice that the variable operations that appear in the subtrees rooted in the
non-terminal $C_{1,3}^{\vdash_{x}\vdash_{y},\dashv_{y}}$ are only those
indicated in its superscript. That is, there are no variable operations that
occur between positions $1,2$, and no such between positions $2,3$. ∎

Motivated by this, we say that a non-terminal
$A^{\mathbf{x},\mathbf{y}}_{i,j}$ of $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$
is _stable_ if $\mathbf{x}_{A}=\mathbf{x}\cup\mathbf{y}$.

######  Lemma 5.2.

For every functional extraction grammar $G$ in CNF and for every document
$\mathbf{d}$, the set of stable non-terminals of
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ is computable in
$O(|G_{\mathbf{d}}|5^{2k})$ where $k$ is the number of variables $G$ is
associated with.

Therefore, while constructing the parse-trees of
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ whenever we reach a stable non-
terminal we can stop since its subtree does not affect the mapping.

###  5.2 The Jump Function

If $G$ is associated with $k$ variables, there are exactly $2k$ variable
operations in each ref-word produced by $G$. Hence, we can bound the number of
non-stable non-terminals in a parse-tree of
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$. Nevertheless, the depth of a non-
stable non-terminal can be linear in $|\mathbf{d}|$ as the following example
suggests.

######  Example 5.3.

Consider the non-stable non-terminal $F_{n-1,n}^{\emptyset,\emptyset}$ in the
partial parse-tree in Figure 9 of the decorated word
$(\emptyset,1,\emptyset)\cdots(\emptyset,n-1,\vdash_{x}\dashv_{x})(\emptyset,n,\emptyset)$.
Observe that the depth of this non-terminal is linear in $n$. ∎

Since we want the delay of our algorithm to be independent of $|\mathbf{d}|$,
we skip parts of the parse-tree in which no variable operation occurs. This
idea somewhat resembles an idea that was implemented by Amarilli et al. [2] in
their constant delay enumeration algorithm for regular spanners represented as
vset-automata. There, they defined a function that ‘jumps’ from one state to
the other if the path from the former to the latter does not contain any
variable operation. We extend this idea to extraction grammars by defining the
notion of skippable productions. Intuitively, when we focus on a non-terminal
in a parse-tree, the corresponding mapping is affected by either the left
subtree of this non-terminal, or by its right subtree, or by the production
applied on the non-terminal itself (or by any combination of the above). If
the mapping is affected exclusively by the left (right, respectively) subtree
then we can skip the production and move to check the left (right,
respectively) subtree, and do so recursively until we reach a production for
which this is no longer the case.

Formally, a _skippable_ production rule is of the form
$A_{i,j}^{\mathbf{x},\mathbf{y}}\rightarrow
B^{\mathbf{x},\mathbf{z}}_{i,i^{\prime}}C^{\mathbf{z}^{\prime},\mathbf{y}}_{i^{\prime}+1,j}$
where $(a)$ $A_{i,j}^{\mathbf{x},\mathbf{y}}$ is non-stable, $(b)$
$\mathbf{z}=\mathbf{z}^{\prime}=\emptyset$, and $(c)$ exactly one of
$B^{\mathbf{x},\mathbf{z}}_{i,i^{\prime}},C^{\mathbf{z}^{\prime},\mathbf{y}}_{i^{\prime}+1,j}$
is stable. Intuitively, $(a)$ assures that the parse-tree rooted in
$A_{i,j}^{\mathbf{x},\mathbf{y}}$ affects the mapping, $(b)$ assures that the
production applied on $A_{i,j}^{\mathbf{x},\mathbf{y}}$ does not affect the
mapping and $(c)$ assures that exactly one subtree of
$A_{i,j}^{\mathbf{x},\mathbf{y}}$ (either the one rooted at
$B^{\mathbf{x},\mathbf{z}}_{i,i^{\prime}}$ if
$C^{\mathbf{z}^{\prime},\mathbf{y}}_{i^{\prime}+1,j}$ is stable, or the one
rooted at $C^{\mathbf{z}^{\prime},\mathbf{y}}_{i^{\prime}+1,j}$ if
$B^{\mathbf{x},\mathbf{z}}_{i,i^{\prime}}$ is stable) affects the mapping. We
then say that a skippable production rule $\rho$ _follows_ a skippable
production rule $\rho^{\prime}$ if the non-stable non-terminal in the right-
hand side of $\rho^{\prime}$ is the non-terminal in the left-hand side of
$\rho$. The function $\text{\sc{jump}}\colon V^{\text{\sc{dec}}}\rightarrow
2^{V^{\text{\sc{dec}}}}$ is defined by
$B\in\text{\sc{jump}}(A_{i,j}^{\mathbf{x},\mathbf{y}})$ if there is a sequence
of skippable production rules $\rho_{1},\cdots,\rho_{m}$ such that:

  * •

$\rho_{\iota}$ follows $\rho_{\iota-1}$ for every $\iota$,

  * •

the left-hand side of $\rho_{1}$ is $A_{i,j}^{\mathbf{x},\mathbf{y}}$,

  * •

the non-stable non-terminal in the right-hand side of $\rho_{m}$ is $B$,

  * •

there is a production rule that is not skippable whose left-hand side is $B$.

######  Example 5.4.

In the decorated grammar whose (one of its) parse-tree appears in Figure 9 it
holds that
$F_{n-1,n}^{\emptyset,\emptyset}\in\text{\sc{jump}}(S_{1,n}^{\emptyset,\emptyset})$.
∎

The acyclic nature of the decorated grammar (that is, the fact that a non-
terminal cannot be produced from itself) enables us to obtain the following
upper bound for the computation of the jump function.

######  Lemma 5.5.

For every functional unambiguous extraction grammar $G$ in CNF and for every
document $\mathbf{d}$, the jump function is computable in
$O(|\mathbf{d}|^{5}3^{4k}|G|^{2})$ where $k$ is the number of variables $G$ is
associated with.

Lemmas 5.2 and 5.5 imply that we can find the non-stable non-terminals as well
as compute the jump function as part of the quintic preprocessing. It is
important to note that if we can reduce the complexity of computing the jump
function to cubic then we can reduce the whole preprocessing time to cubic.

###  5.3 The Algorithm

$\scriptstyle{S^{\vdash_{x}\vdash_{y},\dashv_{z}}_{1,6}}$$\scriptstyle{A_{1,4}^{{\vdash_{x}\vdash_{y},\vdash_{z}}}}$$\scriptstyle{C_{1,3}^{{\vdash_{x}\vdash_{y},\dashv_{y}}}}$$\scriptstyle{G_{1,2}^{{\vdash_{x}\vdash_{y},\emptyset}}}$$\scriptstyle{I_{1,1}^{{\vdash_{x}\vdash_{y},\emptyset}}}$$\scriptstyle{J_{2,2}^{\emptyset,\emptyset}}$
$\scriptstyle{H_{3,3}^{\emptyset,\dashv_{y}}}$$\scriptstyle{D_{4,4}^{\emptyset,{\vdash_{z}}}}$$\scriptstyle{B_{5,6}^{\emptyset,\dashv_{z}}}$$\scriptstyle{E_{5,5}^{\emptyset,\emptyset}}$$\scriptstyle{F_{6,6}^{\dashv_{x},\dashv_{z}}}$
Figure 10:  $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ Parse tree

procedure _$\text{\sc{enumerate}}(\alpha,\mathsf{map})$_

if  _ $\alpha=\epsilon$_ then

output _$\mathsf{map}$_

denote _$\alpha$ by $A\cdot\alpha^{\prime}$_;

foreach  _$B\in\text{\sc{jump}}(A)$_ do

foreach  _ $(\beta,\mathsf{map}^{\prime})\in\text{\sc{applyProd}}(B)$ _ do

$\text{\sc{enumerate}}(\beta\cdot\alpha^{\prime},\mathsf{map}\cup\mathsf{map}^{\prime})$;

Figure 11: Main enumeration algorithm

Our main enumeration algorithm is presented in Figure 11 and outputs
$(X,\mathbf{d})$-mappings $\mu$ represented as sets of pairs
$(\vdash_{x},i),(\dashv_{x},j)$ whenever $\mu(x)=[i,j\rangle$. The procedure
applyProd is called with a non-terminal $A^{\mathbf{x},\mathbf{y}}_{i,j}$ that
is $(a)$ non-stable and $(b)$ appears at the left-hand side of at least one
rule that is not skippable. The iterator applyProd outputs with constant delay
all those pairs $(\beta,\mathsf{map})$ for which there exists a not skippable
rule of the form $A_{i,j}^{\mathbf{x},\mathbf{y}}\rightarrow
B^{\mathbf{x},\mathbf{z}}_{i,i^{\prime}}C^{\mathbf{z}^{\prime},\mathbf{y}}_{i^{\prime}+1,j}$
such that the following hold:

  * •

$\mathsf{map}=\\{(\tau,i^{\prime}+1)\,\,\vline\,\,\tau\in\mathbf{z}\cup\mathbf{z}^{\prime}\\}$,
and

  * •

$\beta$ is the concatenation of the non-stable terminals amongst
$B^{\mathbf{x},\mathbf{z}}_{i,i^{\prime}}$ and
$C^{\mathbf{z}^{\prime},\mathbf{y}}_{i^{\prime}+1,j}$.

Notice that since $A^{\mathbf{x},\mathbf{y}}_{i,j}$ is non-stable and since
$A_{i,j}^{\mathbf{x},\mathbf{y}}\rightarrow
B^{\mathbf{x},\mathbf{z}}_{i,i^{\prime}}C^{\mathbf{z}^{\prime},\mathbf{y}}_{i^{\prime}+1,j}$
is not skippable, it holds that either $\mathbf{z}\neq\emptyset$ or
$\mathbf{z}^{\prime}\neq\emptyset$ (or both). Thus, the returned
$\mathsf{map}$ is not empty which implies that every call to this procedure
adds information on the mapping, and thus the number of calls is bounded.
Notice also that $\beta$ is the concatenation of the non-terminals among
$B^{\mathbf{x},\mathbf{z}}_{i,i^{\prime}}$ and
$C^{\mathbf{z}^{\prime},\mathbf{y}}_{i^{\prime}+1,j}$ that affect the mapping.

######  Example 5.6.

The procedure applyProd applied on $S_{1,6}^{\vdash_{x}\vdash_{y},\dashv_{z}}$
from Figure 11 adds the pair $(\vdash_{z},5)$ to $\mathsf{map}$; When applied
on $A_{1,4}^{\vdash_{x}\vdash_{y},\vdash_{z}}$, it adds the pair
$(\dashv_{y},4)$ to $\mathsf{map}$; When applied on
$B_{5,6}^{\emptyset,\dashv_{z}}$, it adds the pair $(\dashv_{x},6)$ to
$\mathsf{map}$. ∎

The recursive procedure enumerate outputs the mapping as a set of pairs of the
form $(\gamma,i)$ with $\gamma\in\Gamma_{X}$ a variable operation and $1\leq
i\leq n$. The main enumeration algorithm calls the recursive procedure
enumerate with pairs $(S_{1,n}^{\mathbf{x},\mathbf{y}},\mathsf{map})$ where
$S_{1,n}^{\mathbf{x},\mathbf{y}}$ is a non-terminal in
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$, and $\mathsf{map}$ is the set
containing pairs $(\tau,1)$ for any $\tau\in\mathbf{x}$, and $(\tau,n+1)$ for
any $\tau\in\mathbf{y}$. The recursive procedure enumerate gets a pair
$(\alpha,\mathsf{map})$ as input where $\alpha$ is a (possibly empty) sequence
of non-stable non-terminals and $\mathsf{map}$ is a set of pairs of the above
form. It recursively constructs an output mapping by applying derivations on
the non-stable non-terminals (by calling applyProd) while skipping the
skippable productions (by using jump). We assume that enumerate has $O(1)$
access to everything computed in the preprocessing stage, that is, the grammar
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$, the jump function, and the sets of
stable and non-stable non-terminals.

######  Theorem 5.7.

For every functional unambiguous extraction grammar $G$ in CNF and for every
document $\mathbf{d}$, the main enumerating algorithm described above
enumerates the mappings in $\llbracket{G}\rrbracket(\mathbf{d})$ (without
repetitions) with delay of $O(k)$ between each two consecutive mappings where
$k$ is the number of variables $G$ is associated with.

Had $G$ been ambiguous, the complexity guarantees on the delay would not have
held.

Finally, we remark that the proof of Theorem 3.5 follows from Corollary 4.8,
Proposition 4.10, Lemma 5.2, Lemma 5.5, and Theorem 5.7.

##  6 Conclusion

In this paper we propose a new grammar-based language for document spanners,
namely extraction grammars. We compare the expressiveness of context-free
spanners with previously studied classes of spanners and present a pushdown
model for these spanners. We present an enumeration algorithm for unambiguous
grammars that outputs results with a constant delay after quintic
preprocessing in data complexity. We conclude by suggesting several future
research directions.

To reach a full understanding of the expressiveness of context-free spanners,
one should characterize the string relations that can be expressed with
context-free spanners. This can be done by understanding the expressiveness of
context-free grammars enriched with string equality selection. We note that
there are some similarities between recursive Datalog over regex formulas [35]
and extraction grammars. Yet, with the former we reach the full expressiveness
of polynomial time spanners (data complexity) whereas with the latter we
cannot express string equality. Understanding the connection between these two
formalisms better can be a step in understanding the expressive power of
extraction grammars.

Regarding our enumeration complexity, it might be possible to decrease the
preprocessing complexity by using other techniques to compute the jump
function. Another direction is to find restricted classes of extraction
grammars that are more expressive than regular spanners yet allow linear time
preprocessing (similarly to [2]).

It can be interesting to examine more carefully whether the techniques used
here for enumerating the derivations can be applied also for enumerating
queries on trees, or enumerating queries beyond MSO on strings. This connects
to a recent line of work on efficient enumeration algorithms for monadic-
second-order queries on trees [3]. Can our techniques be used to obtain
efficient evaluation for more expressive queries?

## References

  * [1] Jitendra Ajmera, Hyung-Il Ahn, Meena Nagarajan, Ashish Verma, Danish Contractor, Stephen Dill, and Matthew Denesuk.  A CRM system for social media: challenges and experiences.  In WWW, pages 49–58. ACM, 2013.
  * [2] Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth.  Constant-delay enumeration for nondeterministic document spanners.  In ICDT, pages 22:1–22:19, 2019.
  * [3] Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth.  Enumeration on trees with tractable combined complexity and efficient updates.  In PODS, pages 89–103, 2019.
  * [4] Edward Benson, Aria Haghighi, and Regina Barzilay.  Event discovery in social media feeds.  In ACL, pages 389–398. The Association for Computer Linguistics, 2011.
  * [5] J. Richard Büchi and Lawrence H. Landweber.  Definability in the monadic second-order theory of successor.  J. Symb. Log., 34(2):166–170, 1969.
  * [6] Laura Chiticariu, Rajasekar Krishnamurthy, Yunyao Li, Sriram Raghavan, Frederick Reiss, and Shivakumar Vaithyanathan.  SystemT: An algebraic approach to declarative information extraction.  In ACL, pages 128–137, 2010.
  * [7] Noam Chomsky.  On certain formal properties of grammars.  Information and Control, 2(2):137–167, 1959.
  * [8] Johannes Doleschal, Benny Kimelfeld, Wim Martens, Yoav Nahshon, and Frank Neven.  Split-correctness in information extraction.  In PODS, pages 149–163, 2019.
  * [9] Johannes Doleschal, Benny Kimelfeld, Wim Martens, and Liat Peterfreund.  Weight annotation in information extraction.  In ICDT, volume 155 of LIPIcs, pages 8:1–8:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [10] Pál Dömösi.  Unusual algorithms for lexicographical enumeration.  Acta Cybernetica, 14(3):461–468, 2000.
  * [11] Jay Earley.  An efficient context-free parsing algorithm.  Communications of the ACM, 13(2):94–102, 1970.
  * [12] Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren.  Document spanners: A formal approach to information extraction.  J. ACM, 62(2):12, 2015.
  * [13] Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren.  Declarative cleaning of inconsistencies in information extraction.  ACM Trans. Database Syst., 41(1):6:1–6:44, 2016.
  * [14] Fernando Florenzano, Cristian Riveros, Martín Ugarte, Stijn Vansummeren, and Domagoj Vrgoc.  Constant delay algorithms for regular document spanners.  In PODS, pages 165–177. ACM, 2018.
  * [15] Dominik D. Freydenberger.  A logic for document spanners.  In ICDT, volume 68 of LIPIcs, pages 13:1–13:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
  * [16] Dominik D. Freydenberger.  A logic for document spanners.  Theory Comput. Syst., 63(7):1679–1754, 2019.
  * [17] Dominik D. Freydenberger and Mario Holldack.  Document spanners: From expressive power to decision problems.  In ICDT, volume 48 of LIPIcs, pages 17:1–17:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
  * [18] Dominik D. Freydenberger and Mario Holldack.  Document spanners: From expressive power to decision problems.  Theory Comput. Syst., 62(4):854–898, 2018.
  * [19] Dominik D. Freydenberger, Benny Kimelfeld, and Liat Peterfreund.  Joining extractions of regular expressions.  In PODS, pages 137–149, 2018.
  * [20] Dominik D. Freydenberger and Liat Peterfreund.  Finite models and the theory of concatenation.  CoRR, abs/1912.06110, 2019.  URL: http://arxiv.org/abs/1912.06110.
  * [21] Dominik D. Freydenberger and Sam M. Thompson.  Dynamic complexity of document spanners.  In ICDT, volume 155, pages 11:1–11:21, 2020.
  * [22] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman.  Introduction to automata theory, languages, and computation - international edition (2. ed).  Addison-Wesley, 2003.
  * [23] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman.  Introduction to automata theory, languages, and computation, 3rd Edition.  Pearson international edition. Addison-Wesley, 2007.
  * [24] Donald E. Knuth.  Semantics of context-free languages.  Mathematical Systems Theory, 2(2):127–145, 1968.
  * [25] Donald E. Knuth.  Correction: Semantics of context-free languages.  Mathematical Systems Theory, 5(1):95–96, 1971.
  * [26] Clemens Lautemann, Thomas Schwentick, and Denis Thérien.  Logics for context-free languages.  In CSL, volume 933 of Lecture Notes in Computer Science, pages 205–216. Springer, 1994.
  * [27] Yaoyong Li, Kalina Bontcheva, and Hamish Cunningham.  SVM based learning system for information extraction.  In Deterministic and Statistical Methods in Machine Learning, First International Workshop, Sheffield, UK, September 7-10, 2004, Revised Lectures, pages 319–339, 2004.
  * [28] Yunyao Li, Frederick Reiss, and Laura Chiticariu.  SystemT: A declarative information extraction system.  In ACL, pages 109–114. ACL, 2011.
  * [29] Erkki Mäkinen.  On lexicographic enumeration of regular and context-free languages.  Acta Cybernetica, 13(1):55–61, 1997.
  * [30] Francisco Maturana, Cristian Riveros, and Domagoj Vrgoč.  Document spanners for extracting incomplete information: Expressiveness and complexity.  In PODS, pages 125–136, 2018.
  * [31] Andrea Moro, Marco Tettamanti, Daniela Perani, Caterina Donati, Stefano F Cappa, and Ferruccio Fazio.  Syntax and the brain: disentangling grammar by selective anomalies.  Neuroimage, 13(1):110–118, 2001.
  * [32] Takashi Nagashima.  A formal deductive system for CFG.  Hitotsubashi journal of arts and sciences, 28(1):39–43, 1987.
  * [33] Yoav Nahshon, Liat Peterfreund, and Stijn Vansummeren.  Incorporating information extraction in the relational database model.  In WebDB, page 6. ACM, 2016.
  * [34] Liat Peterfreund, Dominik D. Freydenberger, Benny Kimelfeld, and Markus Kröll.  Complexity bounds for relational algebra over document spanners.  In PODS, pages 320–334. ACM, 2019.
  * [35] Liat Peterfreund, Balder ten Cate, Ronald Fagin, and Benny Kimelfeld.  Recursive programs for document spanners.  In ICDT, volume 127 of LIPIcs, pages 13:1–13:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019.
  * [36] Christopher De Sa, Alexander Ratner, Christopher Ré, Jaeho Shin, Feiran Wang, Sen Wu, and Ce Zhang.  Deepdive: Declarative knowledge base construction.  SIGMOD Record, 45(1):60–67, 2016.
  * [37] Markus L. Schmid.  Characterising REGEX languages by regular languages equipped with factor-referencing.  Inf. Comput., 249:1–17, 2016.
  * [38] Rania A Abul Seoud, Abou-Bakr M Youssef, and Yasser M Kadah.  Extraction of protein interaction information from unstructured text using a link grammar parser.  In 2007 International Conference on Computer Engineering & Systems, pages 70–75. IEEE, 2007.
  * [39] Warren Shen, AnHai Doan, Jeffrey F. Naughton, and Raghu Ramakrishnan.  Declarative information extraction using Datalog with embedded extraction predicates.  In VLDB, pages 1033–1044, 2007.
  * [40] Jason M Smith and David Stotts.  SPQR: Flexible automated design pattern extraction from source code.  In 18th IEEE International Conference on Automated Software Engineering, pages 215–224. IEEE, 2003.
  * [41] Leslie G. Valiant.  General context-free recognition in less than cubic time.  J. Comput. Syst. Sci., 10(2):308–315, 1975.  doi:10.1016/S0022-0000(75)80046-8.
  * [42] Huang Wen-Ji.  Enumerating sentences of context free language based on first one in order.  Journal of Computer Research and Development, 41(1):9–14, 2004\.
  * [43] Virginia Vassilevska Williams.  Multiplying matrices faster than coppersmith-winograd.  In STOC, pages 887–898. ACM, 2012.
  * [44] Hua Xu, Shane P. Stenner, Son Doan, Kevin B. Johnson, Lemuel R. Waitman, and Joshua C. Denny.  MedEx: a medication information extraction system for clinical narratives.  JAMIA, 17(1):19–24, 2010.
  * [45] Akane Yakushiji, Yuka Tateisi, Yusuke Miyao, and Jun-ichi Tsujii.  Event extraction from biomedical papers using a full parser.  In Biocomputing 2001, pages 408–419. World Scientific, 2000.
  * [46] Huaiyu Zhu, Sriram Raghavan, Shivakumar Vaithyanathan, and Alexander Löser.  Navigating the intranet with high precision.  In WWW, pages 491–500. ACM, 2007.

##  Appendix A Appendix for Section 2

$\blacktriangleright$ Proposition 2.10. Every extraction grammar $G$ can be
converted into an equivalent functional extraction grammar $G^{\prime}$ in
$O(|G|^{2}+3^{2k}|G|)$ time where $k$ is the number of variables $G$ is
associated with.

######  Proof A.1.

Let $G:=(X,V,{\Sigma},{P},{S})$ be an extraction grammar. We assume that $G$
is in CNF since if it is not then we can convert it into one in $O(|G|^{2})$
with the standard algorithm presented, e.g., in [23]. Note that the resulting
grammar is $O(|G|)$. We define an extraction grammar $G^{\prime}$ that is
associated with $X$ as well as follows. Its non-terminals are $X\times
2^{\Gamma_{X}}$, its terminals are ${\Sigma}$, the start variable is
$(S,\Gamma_{X})$, and its production rules are as follows.

  * •

$(A,X_{1})\rightarrow(B,X_{2})(C,X_{3})$ whenever $A\rightarrow BC\in{P}$, and
$X_{1}=X_{2}\cup X_{3}$, and $X_{2}\cap X_{3}=\emptyset$, and for any $x\in X$
if $\dashv_{x}\in X_{2}$ then $\vdash_{x}\not\in X_{3}$;

  * •

$(A,\emptyset)\rightarrow\sigma$ whenever $A\rightarrow\sigma\in{P}$ with
$\sigma\in\Sigma$; and

  * •

$(A,\\{\tau\\})\rightarrow\tau$ whenever $A\rightarrow\tau\in{P}$ with
$\tau\in\Gamma_{X}$.

A straightforward induction shows that $G^{\prime}$ is functional and that it
is equivalent to $G$. The number of ways to choose two disjoint subsets of
$\Gamma_{X}$ is $3^{2k}$ and therefore complexity of the construction is
$O(|G|^{2}+3^{2k}|G|)$ where $k$ is the number of variables associated with
$G$. Notice that $G^{\prime}$ is in CNF since $G$ is in CNF. Notice also that
if $G$ is in CNF to begin with, the complexity reduces to $O(3^{2k}|G|)$.

$\blacktriangleright$ Proposition 2.12. In Proposition 2.10, if $G$ is
unambiguous then so is $G^{\prime}$.

######  Proof A.2.

Assume that $G$ is unambiguous. It suffices to show that converting it to CNF
$G^{\prime\prime}$ results in an unambiguous extraction grammar and that the
conversion to $G^{\prime}$ preserve unambiguity (that is, if
$G^{\prime\prime}$ is unambiguous then so is $G^{\prime}$). This is
straightforward since if we assume that $G^{\prime}$ is not unambiguous than
we can easily show that so is $G^{\prime\prime}$ (by translating
$G^{\prime}$’s derivations to $G^{\prime\prime}$ by omitting the second
coordinate). So it is left to show that the conversion to CNF preserves
unambiguity. For that, we repeat here the details of the algorithm presented
in [22, Section 7.1.5] for converting a grammar $G$ to CNF. The algortihm
consists of three steps:

  1. 1.

We omit $\epsilon$-productions, unit productions and useless symbols.

  2. 2.

We arrange that all bodies of length 2 or more consists only of variables;

  3. 3.

We break bodies of length 3 or more into a cascade of productions, each with a
body consisting of two variables.

In step 1 we do not add ambiguity as we reduce productions. In step 2 we add
productions of the form $A\rightarrow\sigma$ but these do not affect
unambiguity as these $A$s are fresh non-terminals and for each $\sigma$ we
have a unique $A$. In step 3 we replace rules of the form $A\rightarrow
A_{1}\cdots A_{n}$ into the cascade $A\rightarrow A_{1}B_{1},B_{1}\rightarrow
A_{2}B_{2},\cdots B_{n-2}\rightarrow A_{n-1}A_{n}$ where all $B_{i}$s are
fresh non-terminals. Thus, this step do not affect unambiguity.

##  Appendix B Appendix for Section 3

$\blacktriangleright$ Proposition 3.1. The class of spanners definable by
regular extraction grammars is equal to the class of regular spanners.

######  Proof B.1.

Let us consider the regular spanner represented as the vset-automaton $A$.
Since every regular language is also a context-free language we can construct
a pushdown automaton $A^{\prime}$ such that
$\mathcal{R}(A^{\prime})=\mathcal{R}(A)$. Thus,
$\llbracket{A}\rrbracket=\llbracket{A^{\prime}}\rrbracket$

For the second direction we have to show that every spanner described by a
right-regular extraction grammar is a regular spanner. Let
$G=(V,{\Sigma},{P},{S})$ be a right-regular extraction grammar. We use a
similar construction used for converting a right regular grammar into a non-
deterministic automaton while treating the variable operations as terminal
symbols. The states of the automaton are a new final state $q_{f}$ along with
a state $q_{A}$ for every non-terminal $A\in V$ with the state $q_{{S}}$ as
the initial state. The transition function $\delta$ is the following: for
every $A\rightarrow\sigma B$ we set $\delta(q_{A},\sigma)=q_{B}$ and for
$A\rightarrow\sigma$ we set $\delta(q_{A},\sigma)=q_{f}$. It holds that
$\mathcal{R}(G)=\mathcal{L}(A)$ and in particular, for every $\mathbf{d}$ we
have that
$\llbracket{G}\rrbracket(\mathbf{d})=\llbracket{A}\rrbracket(\mathbf{d})$.

######  Example B.2.

Let us consider the following Boolean core spanner given as the expression
$\pi_{\emptyset}\,\zeta^{=}_{x,y}\big{(}\vdash_{x}\Sigma^{*}\dashv_{x}\vdash_{y}\Sigma^{*}\dashv_{y}\big{)}.$
It can be shown that the spanner
$\llbracket{\zeta^{=}_{x,y}\big{(}\vdash_{x}\Sigma^{*}\dashv_{x}\vdash_{y}\Sigma^{*}\dashv_{y}\big{)}}\rrbracket$
is evaluated to a non-empty $(\\{x,y\\},\mathbf{d})$-relation on $\mathbf{d}$
if and only if $\mathbf{d}$ is of the form $ww$ for some $w\in\Sigma^{*}$ (and
in this case it contains a single $(\\{x,y\\},\mathbf{d})$-mapping). For
instance, on $\mathbf{d}_{1}:=\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{b}$ we
have that
$\llbracket{\zeta^{=}_{x,y}\big{(}\vdash_{x}\Sigma^{*}\dashv_{x}\vdash_{y}\Sigma^{*}\dashv_{y}\big{)}}\rrbracket(\mathbf{d}_{1})$
contains exactly one $(\\{x,y\\},\mathbf{d}_{1})$-mapping $\mu_{1}$ that is
defined such that $\mu_{1}(x)=[1,3\rangle$ and $\mu_{1}(y)=[3,5\rangle$. On
the other hand, on $\mathbf{d}_{2}:=\mathtt{a}\mathtt{b}\mathtt{a}$ and on
$\mathbf{d}_{3}:=\mathtt{a}\mathtt{b}\mathtt{a}\mathtt{a}$ it holds that
$\llbracket{\zeta^{=}_{x,y}\big{(}\vdash_{x}\Sigma^{*}\dashv_{x}\vdash_{y}\Sigma^{*}\dashv_{y}\big{)}}\rrbracket(\mathbf{d}_{i})$
for $i=2,3$ is empty. ∎

$\blacktriangleright$ Proposition 3.2. The classes of core spanners and
generalized core spanners are each incomparable with the class of context-free
spanners.

######  Proof B.3.

The proof of this proposition is based partly on the following observation
which, in turn, is based on the definition: A language $L$ is _definable_ by a
Boolean spanner $S$ if for every word ${w}\in\Sigma^{*}$ it holds that
${S}({w})\neq\emptyset$ if only if $w\in L$. Boolean extraction grammars
capture the context-free languages. This observation is straightforward as
every extraction grammar that is associated with an empty set of variables can
be interpreted as a context-free grammar. We now prove the proposition: To
show that each of the class of core spanners and generalized spanners is not
contained in the class of context-free spanners it suffices to show that there
is a that is not context-free. Indeed, the language
$\\{ww\,|\,w\in\Sigma^{*}\\}$ which, as shown in Example B.2, is definable by
a Boolean core spanner is not a context-free language [23] and hence by
Observation B.3 is not definable by any extraction spanner. For the other
direction, the language $\\{\mathtt{a}^{n}\mathtt{b}^{n}|n\geq 1\\}$ is
context free and hence by Observation B.3 is definable by an extraction
grammar, nevertheless, this language is not accepted by any Boolean core
spanner [12] and not by any generalized core spanner [20].

$\blacktriangleright$ Theorem 3.3. The class of context-free spanners is
closed under union and projection, and not closed under natural join and
difference.

######  Proof B.4.

We show each of the claims separately:

Closure under projection and union. Let $G_{X}:=(V,{\Sigma},{P},{S})$ be an
extraction grammar and let $X^{\prime}\subseteq X$. We define a morphism
$\mathsf{clr}_{X}:(\Sigma\cup V\cup\Gamma_{X})^{*}\rightarrow(\Sigma\cup
V\cup\Gamma_{Y})^{*}$ where $Y:=X\setminus X^{\prime}$ by
$\mathsf{clr}_{X}(\sigma)=\sigma$ for $\sigma\in\Sigma$, and
$\mathsf{clr}_{X}(\gamma)=\gamma$ for $\gamma\in\Gamma_{Y}$ and
$\mathsf{clr}_{X}(\gamma)=\epsilon$ for $\gamma\in\Gamma_{X^{\prime}}$. We
define the grammar
$G^{\prime}=(V^{\prime},{\Sigma}^{\prime},{P}^{\prime},{S}^{\prime})$ where
$V^{\prime}:=V,{\Sigma}^{\prime}:={\Sigma},{S}^{\prime}:={S}$ and
${P}^{\prime}$ is defined as follows: for every $A\rightarrow\alpha\in{P}$ we
have $A\rightarrow\mathsf{clr}_{X}(\alpha)\in{P}^{\prime}$. It is
straightforward that
$\llbracket{G^{\prime}}\rrbracket=\llbracket{\pi_{X^{\prime}}G_{X}}\rrbracket$.
Closure under union can be obtained by the same technique used for unifying
grammars. Let $G_{1},G_{2}$ be two extraction grammars with
$\mathsf{Vars}(G_{1})=\mathsf{Vars}(G_{2})$. We can construct a grammar $G$
with $\mathcal{R}({G})=\mathcal{R}(G_{1})\cup\mathcal{R}(G_{2})$. Therefore,
for every $\mathbf{d}$ it holds that
$\mathsf{Ref}(G,\mathbf{d})=(\mathcal{R}(G_{1})\cup\mathcal{R}(G_{2}))\cap\mathsf{Ref}(\mathbf{d})$
and thus
$\llbracket{G}\rrbracket=\llbracket{G_{1}}\rrbracket\cup\llbracket{G_{2}}\rrbracket$.

Non-closure under natural join and difference. Non-closure properties are
immediate consequence of the case for context-free languages since non-
deterministic automata and push-down automata can be viewed as Boolean vset-
automata and Boolean pushdown automata, respectively. This is due to the fact
that the definitions of Boolean pushdown automaton and non-deterministic
automaton coincide, as well as those of Boolean vset-automaton and non-
deterministic automaton.

$\blacktriangleright$ Proposition 3.4. For every extraction grammar $G$ and
every document $\mathbf{d}$ it holds that
$\llbracket{G}\rrbracket(\mathbf{d})$ can be computed in
$O(|G|^{2}+|\mathbf{d}|^{2k+3}\,k^{3}\,|G|)$ time where $k$ is the number of
variables $G$ is associated with.

######  Proof B.5.

This proposition relies on the celebrated Cocke-Younger-Kasami (CYK) parsing
algorithm for context-free grammars [23]. Given a context-free grammar $G$ in
Chomsky Normal Form [7], as will be defined shortly, and a string $w$, the CYK
algorithm determines whether $G$ produces $w$ (i.e., $w$ is a word in the
language defined by $G$.) A context-free grammar $G$ is in Chomsky Normal Form
(CNF) if all of its production rules are of the form $A\rightarrow BC$ where
$A,B,C$ are non-terminals or of the form $A\rightarrow\sigma$ where $A$ is a
non-terminal and $\sigma$ is a terminal. The algorithm that computes
$\llbracket{G}\rrbracket(\mathbf{d})$ operates as follows: it iterates over
all of the ref-words $\mathbf{r}$ that are (1) valid for the variables
$\mathsf{Vars}(G)$ whose operations appear in $G$ and (2) mapped by
$\mathsf{clr}$ into $\mathbf{d}$. For each such ref-word, it uses CYK
algorithm to determine whether it is produced by $G$ by treating $G$ as a
standard CFG over the extended alphabet $\Sigma\cup\Gamma_{X}$, and after
converting $G$ into CNF. We convert $G$ into $CNF$ in $O(|G|^{2})$. Note that
there are $O(|d|^{2k})$ valid ref-words, and each is represented by a ref-word
of length $O(|\mathbf{d}|+2k)$. For every such ref-word we use CYK to check
whether it belongs to $G$ in $O((|\mathbf{d}|+2k)^{3}|G|)$. Since we repeat
the process for every ref-word the total complexity is
$O(|G|^{2}+|d|^{2k}(|\mathbf{d}|+2k)^{3}|G|)$.

##  Appendix C Appendix for Section 4

$\blacktriangleright$ Lemma 4.2. For every extraction grammar $G$ in CNF,
every document $\mathbf{d}:=\sigma_{1}\cdots\sigma_{n}$, every non-terminal
$A$ of $G$, and every ref-word $\mathbf{r}\in(\Sigma\cup\Gamma_{X})^{*}$ with
$\mathsf{clr}(\mathbf{r})=\sigma_{i}\cdots\sigma_{j}$ the following holds:
$A\Rightarrow_{G}^{*}\mathbf{r}$ if and only if
$A_{i,j}\Rightarrow_{G_{\mathbf{d}}}^{*}\mathbf{r}$

######  Proof C.1.

The proof is by induction on $j-i$. In the base case we have $j=i$ and then
$\mathbf{r}=\sigma_{i}$. By definition we have
$A\Rightarrow^{*}_{G}\sigma_{i}$ if and only if
$A_{i,i}\Rightarrow^{*}_{G_{\mathbf{d}}}\sigma_{i}$. For the induction step:
If $A\Rightarrow^{*}_{G}\mathbf{r}$ with
$\mathbf{r}=\sigma_{i}\cdots\sigma_{j}$ then since $G$ is in CNF we have
$A\Rightarrow^{*}_{G}BC\Rightarrow^{*}_{G}\mathbf{r}_{1}\mathbf{r}_{2}$ where
$\mathsf{clr}(\mathbf{r}_{1})=\sigma_{i}\cdots\sigma_{i+\ell}$ and
$\mathsf{clr}(\mathbf{r}_{2})=\sigma_{i+\ell+1}\cdots\sigma_{j}$. We can use
the induction hypothesis to obtain that
$B_{i,i+\ell}\Rightarrow^{*}_{G_{\mathbf{d}}}\mathbf{r}_{1}$ and that
$C_{i+\ell+1,j}\Rightarrow^{*}_{G_{\mathbf{d}}}\mathbf{r}_{2}$. By definition
of $G_{\mathbf{d}}$ we have that
$A_{i,j}\Rightarrow^{*}_{G_{\mathbf{d}}}B_{i,i+\ell}C_{i+\ell+1,j}$ and thus
we can conclude that $A_{i,j}\Rightarrow^{*}_{G_{\mathbf{d}}}\mathbf{r}$. For
the other direction, let us assume that
$A_{i,j}\Rightarrow^{*}_{G_{\mathbf{d}}}\mathbf{r}$. By definition
$G_{\mathbf{d}}$ is in CNF as well and also by definition we have that
$A_{i,j}\Rightarrow^{*}_{G_{\mathbf{d}}}B_{i,i+\ell}C_{i+\ell+1,j}$ where
$A\Rightarrow^{*}_{G}BC$. Thus, we obtain
$A_{i,j}\Rightarrow^{*}_{G_{\mathbf{d}}}B_{i,i+\ell}C_{i+\ell+1,j}\Rightarrow^{*}_{G_{\mathbf{d}}}\mathbf{r}_{1}\mathbf{r}_{2}=\mathbf{r}$.
By induction hypothesis we have $B\Rightarrow^{*}_{G}\mathbf{r}_{1}$ and
$C\Rightarrow^{*}_{G}\mathbf{r}_{2}$. Combining the above we get
$A\Rightarrow^{*}_{G}BC\Rightarrow^{*}_{G}\mathbf{r}_{1}\mathbf{r}_{2}=\mathbf{r}$.

$\blacktriangleright$ Proposition 4.4. For every extraction grammar $G$ in CNF
and for every document $\mathbf{d}$, it holds that $G_{\mathbf{d}}$ can be
constructed in $O({|\mathbf{d}|}^{3}|G|)$.

######  Proof C.2.

Each production rule in $G$ has at most $|\mathbf{d}|^{3}$ variations in
$G_{\mathbf{d}}$. Thus, the total time required to produce $G_{\mathbf{d}}$ is
$O(|\mathbf{d}|^{3}|G|)$.

$\blacktriangleright$ Proposition 4.5. For every functional extraction grammar
$G$ and every non-terminal $A$ of $G$ there is a set
$\mathbf{x}_{A}\subseteq\Gamma_{X}$ of variable operations such that for every
ref-word $\mathbf{r}$ where $A\Rightarrow^{*}\mathbf{r}$ the variable
operations that appear in $\mathbf{r}$ are exactly those in $\mathbf{x}_{A}$.
Computing all sets $\mathbf{x}_{A}$ can be done in $O(|G|)$.

######  Proof C.3.

Assume by contradiction that this is not the case. That is, there are
$\mathbf{r},\mathbf{s}$ such that $A\Rightarrow^{*}\mathbf{r}$ and
$A\Rightarrow^{*}\mathbf{s}$. Since $G$ does not contain any unreachable non-
terminal and since every non-terminal of $G$ is reachable from the initial
non-terminal there are the following leftmost derivations:

$S\Rightarrow^{*}\mathbf{r}^{\prime}A\gamma\Rightarrow^{*}\mathbf{r}^{\prime}\mathbf{r}\mathbf{r}^{\prime\prime}$

and

$S\Rightarrow^{*}\mathbf{s}^{\prime}A\delta\Rightarrow^{*}\mathbf{s}^{\prime}\mathbf{s}\mathbf{s}^{\prime\prime}$

where
$\mathbf{r}^{\prime},\mathbf{s}^{\prime},\mathbf{r}^{\prime\prime},\mathbf{s}^{\prime\prime}\in(\Sigma\cup\Gamma_{X})^{*}$
and $\gamma,\delta\in(V\cup\Sigma\cup\Gamma_{X})^{*}$. Recall that both
$\mathbf{r}^{\prime}\mathbf{r}\mathbf{r}^{\prime\prime}$ and
$\mathbf{s}^{\prime}\mathbf{s}\mathbf{s}^{\prime\prime}$ are valid and thus if
the variable operations that occur in $\mathbf{r}$ and $\mathbf{s}$ are
different then so do the variable operations that appear in
$\mathbf{r}^{\prime}\mathbf{r}^{\prime\prime}$ and in
$\mathbf{s}^{\prime}\mathbf{s}^{\prime\prime}$. Thus, we can replace
$\mathbf{r}$ with $\mathbf{s}$ and obtain a ref-word that is not valid. This
contradicts the fact that $G$ is functional.

To compute the sets $\mathbf{x}_{A}$, we view the non-terminals as nodes and
the transitions as edges such that $A\rightarrow BC$ implies that there is an
edge from $A$ to $B$, and an edge from $A$ to $C$. We then run a BFS on this
graph and view the output sequence of non-terminals as a topological order. We
then iterate over the non-terminals in an inverse order and accumulate for
each the set of variable operations that consists of its descendants. This
whole process can be done in $O(|G|)$.

$\blacktriangleright$ Proposition 4.7. For every functional extraction grammar
$G$ in CNF and for every document $\mathbf{d}$, if $G$ is unambiguous then
$\text{\sc{decorGrmr}}({G}_{\mathbf{d}})$ is unambiguous.

######  Proof C.4.

It is straightforward that if $G$ is unambiguous then so is $G_{\mathbf{d}}$
for any document $\mathbf{d}$. Assume by contradiction that
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ is not unambiguous. That is, there is
a decorated word that has two parse-trees. By the definition of
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ it follows that if it is the case then
$G_{\mathbf{d}}$ has two different parse-trees to the same ref-words which
leads to the desired contradiction.

$\blacktriangleright$ Lemma 4.8. For every functional unambiguous extraction
grammar $G$ in CNF and for every document $\mathbf{d}$, every decorated word
produced by $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ is valid and

$\llbracket{G}\rrbracket(\mathbf{d})=\\{\mu^{w}\,\,\vline\,\,S\Rightarrow^{*}_{\text{\sc{decorGrmr}}(G_{\mathbf{d}})}w\\}.$

######  Proof C.5.

Let $w$ be a decorated word such that
$S\Rightarrow^{*}_{G}(\mathbf{x}_{1},1,\mathbf{y}_{1})\cdots(\mathbf{x}_{n},n,\mathbf{y}_{n})$.
Assume by contradiction that there is a variable $x$ such that $\mu^{w}(x)$ is
not well-defined. It follows from the construction of
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ that either the variable operation
$\vdash_{x}$ or $\dashv_{x}$ appears more than once in a ref-word produced by
$G$ or that the variable operation $\vdash_{x}$ occurs after $\dashv_{x}$ in a
ref-word produced by $G$. That is a contradiction to the fact that $G$ is
functional.

Before moving on to the second part of the theorem, we present some
definitions. We define a function $f$ from the possible parse-trees of
$G_{\mathbf{d}}$ to the possible parse-trees of
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ with
$\mathbf{d}:=\sigma_{1}\cdots\sigma_{n}$. We first define for every
$\sigma_{i}$ the non-terminal associated with it as the non-terminal that is
the root of the maximal subtree with leaf $\sigma_{i}$ and no other leaf from
$\Sigma$. The function $f$ replaces for every $i$ the subtree rooted in the
non-terminal $A_{i,i}$ associated with $\sigma_{i}$ with the subtree
$A_{i,i}^{\mathbf{x},\mathbf{y}}\rightarrow(\mathbf{x},i,\mathbf{y})$ where
$A_{i,i}\Rightarrow_{G_{\mathbf{d}}}^{*}x_{1}\cdots
x_{\ell}\sigma_{i}y_{1}\cdots y_{\ell^{\prime}}$ and
$\mathbf{x}=\\{x_{1},\cdots,x_{\ell}\\}$ and
$\mathbf{y}=\\{y_{1},\cdots,y_{\ell^{\prime}}\\}$. By a slight abuse of
notation and since we are dealing with unambiguous grammars we refer to parse-
trees as the word they produce and vice-versa. Note that

Claim 1. if $\mathbf{r}\in\mathcal{R}(G_{\mathbf{d}})$ then
$S\Rightarrow^{*}_{\text{\sc{decorGrmr}}(G_{\mathbf{d}})}f(\mathbf{r})$.

This claim can be showed by a simple induction using the definition of
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$.

Claim 2. if
$S\Rightarrow_{\text{\sc{decorGrmr}}(G_{\mathbf{d}})}^{*}(\mathbf{x}_{1},1,\mathbf{y}_{1})\cdots(\mathbf{x}_{n},n,\mathbf{y}_{n})$
with then there is a $\mathbf{r}$ such that
$\mathbf{r}\in\mathcal{R}(G_{\mathbf{d}})$ and the image under $f$ of the
parse-tree of $\mathbf{r}$ is $w$.

This claim can be proved by a simple induction using the definition of
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$.

Claim 3. For every $\mathbf{r}$ it holds that
$\mu^{\mathbf{r}}=\mu^{\mathbf{r}^{\prime}}$ where $\mathbf{r}^{\prime}$ is
the image under $f$ of the parse tree of $\mathbf{r}$.

This claim is a direct consequence of the definitions.

Moving back to the proof of the theorem, which is showing that

$\llbracket{G}\rrbracket(\mathbf{d})=\\{\mu^{w}\,\,\vline\,\,S\Rightarrow^{*}_{\text{\sc{decorGrmr}}(G_{\mathbf{d}})}w\\}.$

If $\mu\in\llbracket{G}\rrbracket(\mathbf{d})$ then there is a ref-word
$\mathbf{r}$ in $\mathcal{R}(G)$ such that $\mu=\mu^{\mathbf{r}}$. By claim 1,
$S\Rightarrow^{*}_{\text{\sc{decorGrmr}}(G_{\mathbf{d}})}f(\mathbf{r})$. Note
also that $\mathsf{clr}^{\text{\sc dec}}(f(\mathbf{r}))=\mathbf{d}$. Finally,
by Claim 3 we can conclude the claim.

If
$\mu\in\\{\mu^{w}\,\,\vline\,\,S\Rightarrow^{*}_{\text{\sc{decorGrmr}}(G_{\mathbf{d}})}w\\}$
then there is a decorated word $w$ such that $\mu=\mu^{w}$. Claim 2 implies
that there exists a $\mathbf{r}\in\mathcal{R}(G)$ such that $f(\mathbf{r})=w$.
Then, by claim 3 we conclude that $\mu^{\mathbf{r}}=\mu^{w}$ which completes
the proof.

$\blacktriangleright$ Proposition 4.10. For every functional unambiguous
extraction grammar $G$ in CNF and for every document $\mathbf{d}$,
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ can be constructed in
$O(|G_{\mathbf{d}}|\,5^{2k})=O({|\mathbf{d}|}^{3}|G|\,5^{2k})$ where $k$ is
the number of variables associated with $G$.

######  Proof C.6.

In Step 1 of the construction we create several copies of each production of
$G_{\mathbf{d}}$. Notice that there are $5^{2k}$ four pairwise disjoint
subsets of $\Gamma_{X}$ (which is equivalent to the number of mappings from
$\Gamma_{X}$ to a domain of size $5$ which indicates to which subset an
elements belong). The size of the grammar after step 1 is
$O(|G_{\mathbf{d}}|5^{2k})$ and that is also the time complexity required for
constructing it. Step 2 consists of several linear scans of the resulting
grammar and hence can be done in $O(|G_{\mathbf{d}}|5^{2k})$ time. Finally, in
step 3 we remove the unit productions. For this purpose we have to compute for
each non-terminal the set of its reachable non-terminal using only unit
productions. The naive solution would require a quadratic computation but here
we have the subscripts that give us extra information and it suffices to check
for a non-terminal $A_{i,j}$ only those non-terminals that have similar
subscript. Since for each $i,j$ there are at most $O(|G|3^{2k})$ unit
productions, we can do the computation in $O(|\mathbf{d}|^{2}|G|3^{2k})$.
Thus, we obtain the following complexity
$O(|G_{\mathbf{d}}|\,5^{2k})=O({|\mathbf{d}|}^{3}|G|\,5^{2k})$.

##  Appendix D Appendix for Section 5

$\blacktriangleright$ Lemma 5.2. For every functional extraction grammar $G$
in CNF and for every document $\mathbf{d}$, the set of stable non-terminals of
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ is computable in
$O(|G_{\mathbf{d}}|5^{2k})$ where $k$ is the number of variables $G$ is
associated with.

######  Proof D.1.

Recall that in Proposition 4.5 we showed that we can compute the sets
$\mathbf{x}_{A}$ for every non-terminal $A$ in $G$ in linear time in $|G|$. It
is straightforward that the stable non-terminals of
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ are exactly those of the form
$A_{i,j}^{\mathbf{x},\mathbf{y}}$. We can scan the non-terminals of
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ and for each such non-terminal
$A_{i,j}^{\mathbf{x},\mathbf{y}}$ check in $O(1)$ whether
$\mathbf{x}_{a}=\mathbf{x}\cup\mathbf{y}$. Therefore, the complexity of this
step is
$O(|G|)+O(|\text{\sc{decorGrmr}}(G_{\mathbf{d}})|)=O(|\mathbf{d}|^{3}|G|\,5^{2k})$.

$\blacktriangleright$ Lemma 5.5. For every functional unambiguous extraction
grammar $G$ in CNF and for every document $\mathbf{d}$, the jump function is
computable in $O(|\mathbf{d}|^{5}3^{4k}|G|^{2})$ where $k$ is the number of
variables $G$ is associated with.

######  Proof D.2.

We claim that Algorithm 1 computes the jump function. The algorithm has access
to the grammar $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ as well as to its
skippable productions (i.e., it can check in $O(1)$ whether a production is
skippable or not). The algorithm returns a 5 dimensional array such that at
the end of the run $\sf{jmp}[A,i,j,\mathbf{x},\mathbf{y}]$ will contain all of
the non-terminals that are in the result of applying the jump on
$A_{i,j}^{\mathbf{x},\mathbf{y}}$.

procedure _$\text{\sc{computeJump}}()$_

foreach  _non terminal $A_{i,j}^{\mathbf{x},\mathbf{y}}$ in
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$_ do

$\sf{reachable}[A,i,j,\mathbf{x},\mathbf{y}]:=\\{A_{i,j}^{\mathbf{x},\mathbf{y}}\\}$

foreach  _non terminal $A$ in $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$_ do

insert $A$ to $\sf{remove}$

foreach  _production rule $\rho$ in $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$_
do

if  _$\rho$ is non-skipabble with lefthand side
$A_{i,j}^{\mathbf{x},\mathbf{y}}$_ then

$\sf{remove}:=\sf{remove}\setminus\\{A_{i,j}^{\mathbf{x},\mathbf{y}}\\}$

foreach  _non-terminal $A_{i,j}^{\mathbf{x},\mathbf{y}}$ in
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$_ do

$\sf{jmp}[A,i,j,\mathbf{x},\mathbf{y}]:=\\{A_{i,j}^{\mathbf{x},\mathbf{y}}\\}\setminus\sf{remove}$

initialize _ perform a topological sort on non-terminals;_

foreach  _skippable $\rho:=A_{i,j}^{\mathbf{x},\mathbf{y}}\rightarrow
B_{i,\ell}^{\mathbf{x},\emptyset}C_{\ell+1,j}^{\emptyset,\mathbf{y}}$ in
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ in reverse order to topological sort_
do

if  _ $B_{i,\ell}^{\mathbf{x},\emptyset}$ is non-stable_ then

$\sf{reachable}{[A,i,j,\mathbf{x},\mathbf{y}]}:=\sf{reachable}[A,i,j,\mathbf{x},\mathbf{y}]\cup\sf{reachable}[B,i,\ell,\mathbf{x},\emptyset]$;

$\sf{jmp}{[A,i,j,\mathbf{x},\mathbf{y}]}:=\sf{reachable}[A,i,j,\mathbf{x},\mathbf{y}]\setminus\sf{remove}$;

if  _$C_{\ell+1,j}^{\emptyset,\mathbf{y}}$ is non-stable_ then

$\sf{reachable}[A,i,j,\mathbf{x},\mathbf{y}]:=\sf{reachable}[A,i,j,\mathbf{x},\mathbf{y}]\cup\sf{reachable}[C,\ell+1,j,\emptyset,\mathbf{y}]$
$\sf{jmp}{[A,i,j,\mathbf{x},\mathbf{y}]}:=\sf{reachable}[A,i,j,\mathbf{x},\mathbf{y}]\setminus\sf{remove}$;

output _$\sf{jmp}$_

Algorithm 1 Compute The Jump

The algorithm uses an auxiliary array $\sf{reachable}$ and an auxiliary set
$\sf{remove}$. The correctness of the algorithm is based on the following
claims:

Claim 1: The array $\sf{reachable}$ stores in cell
$\sf{reachable}[A,i,j,\mathbf{x},\mathbf{y}]$ all of the non-terminals $B$
such that there is a sequence of skippable productions
$\rho_{1},\cdots,\rho_{m}$ such that:

  * •

$\rho_{\iota}$ follows $\rho_{\iota-1}$ for every $\iota$,

  * •

the left-hand side of $\rho_{1}$ is $A_{i,j}^{\mathbf{x},\mathbf{y}}$,

  * •

the non-stable non-terminal in the right-hand side of $\rho_{m}$ is $B$

Claim 2: The set $\sf{remove}$ contains all of the non-terminals $B$ for which
there is no non-skippable production with $B$ in the left-hand side. That is,
all of the productions that have $B$ in their left-hand side are skippable.

This two claims allows us to conclude the following. Since both
$B\in\sf{reachable}[A,i,j,\mathbf{x},\mathbf{y}]$ and $B\not\in\sf{remove}$,
there is a sequence of skippable productions $\rho_{1},\cdots,\rho_{m}$ such
that:

  * •

$\rho_{\iota}$ follows $\rho_{\iota-1}$ for every $\iota$,

  * •

the left-hand side of $\rho_{1}$ is $A_{i,j}^{\mathbf{x},\mathbf{y}}$,

  * •

the non-stable non-terminal in the right-hand side of $\rho_{m}$ is $B$,

  * •

there is _no_ production rule that is not skippable whose left-hand side is
$B$.

This, in turn, completes the proof of correctness of the algorithm.

We shall now explain why both claims hold. While Claim 2 is derived directly
from the way we initialize $\sf{remove}$, the proof of Claim 1 is more
involved as we now explain. Since $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$
produces only terminal decorated words of fixed length $|\mathbf{d}|$ (see
Lemma 4.8) and since it is in CNF, we can conclude that the longest derivation
sequence of $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ is of length
$O(|\mathbf{d}|)$. Therefore, the correctness of the claim is obtained from
the fact that we iterate over the skippable derivation in a reverse order to
the topological order.

Complexity. We assume that we can check in $O(1)$ whether a non-terminal is
stable. To do so, we can run the algorithm described in the proof of Lemma 5.2
and store the data in a lookup table with the non-terminals as keys and the
value is either ‘stable’ or ‘non-stable’. The runtime of this procedure is
$O(|G_{\mathbf{d}}|5^{2k})$.

We also assume that we can check in $O(1)$ whether a rule in
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ is skippable. To do so, we can use the
above look-up table and for each rule check whether all of the conditions in
the definition hold in $O(1)$. We can store this information in a lookup table
with the rules as keys and the value is either ‘skippable’ or ‘non-skippable’.
The runtime of this procedure is also $O(|G_{\mathbf{d}}|5^{2k})$.

The four first for each loops are used for initializations and require
$O(|G_{\mathbf{d}}|5^{2k})=O(|\mathbf{d}|^{3}|G|5^{2k})$ as the iterate
through all production rules of $\text{\sc{decorGrmr}}(G_{\mathbf{d}})$. We
then preform a topological sort on the production rules in
$O(|\mathbf{d}|^{3}|G|5^{2k})$.

The last for each loop iterates through all of the skippable rules of
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ ordered by their head in a reverse
order to that we have obtained in the topological sort we performed. There are
at most $O(|\mathbf{d}|^{3}|G|3^{2k})$ such rules (since we their form is
$A_{i,j}^{\mathbf{x},\mathbf{y}}\rightarrow
B_{i,\ell}^{\mathbf{x},\emptyset}C_{\ell+1,j}^{\emptyset,\mathbf{y}}$). In
each such iteration, we compute set unions and set difference. The size of the
set is bounded by $O(|{\mathbf{d}}|^{2}3^{2k}|G|)$. Thus, the total time
complexity of the second for loop is $O(|{\mathbf{d}}|^{5}3^{4k}|G|^{2})$. And
finally, the total complexity of the jump is
$O(|{\mathbf{d}}|^{5}3^{4k}|G|^{2})$.

###  D.1 Proof of Theorem 5.7

$\blacktriangleright$ Theorem 5.7. For every functional unambiguous extraction
grammar $G$ in CNF and for every document $\mathbf{d}$, the main enumerating
algorithm described above enumerates the mappings in
$\llbracket{G}\rrbracket(\mathbf{d})$ (without repetitions) with delay of
$O(k)$ between each two consecutive mappings where $k$ is the number of
variables $G$ is associated with.

In what follows, we present each $(X,\mathbf{d})$-mapping $\mu$ as the set
$\\{(\vdash_{x},i),(\dashv_{x},j)\,\vline\,\mu(x):=[i,j\rangle\\}$ of pairs.
Before proving the theorem itself we prove some lemmas.

We say that a mapping $A$ is compatible with a set $B$ of pairs of the form
$(\tau,i)$ with $\tau\in\Gamma_{X}$ and $1\leq i\leq n$ if $B\subseteq A$.

######  Lemma D.3.

The procedure
$\text{\sc{enumerate}}(S_{1,n}^{\mathbf{x},\mathbf{y}},\mathsf{map})$ where
$\mathsf{map}=\\{(x,1)\,\,\vline\,\,x\in\mathbf{x}\\}\cup\\{(y,n+1)\,\,\vline\,\,y\in\mathbf{y}\\}$
outputs every mapping $\mu^{w}$ that corresponds with a decorated word $w$
produced by $\text{\sc{decorGrmr}}(G,\mathbf{d})$ and that is compatible with
$\mathsf{map}$.

######  Proof D.4.

Let $w$ be a decorated word such that
$\gamma_{1}\Rightarrow\cdots\Rightarrow\gamma_{m}\Rightarrow w$ in a leftmost
derivation where every $\gamma_{i}\neq\gamma_{j}$ and
$\gamma_{1}=S_{1,n}^{\mathbf{x},\mathbf{y}}$. We recursively define
$\mu^{w,j}$ as follows: $\mu^{w,m}$ is $\mathsf{map}$. We denote the
production rule applied in $\gamma_{\ell}\Rightarrow\gamma_{\ell+1}$ by
$A_{i,j}^{\mathbf{x},\mathbf{y}}\rightarrow
B_{i,i^{\prime}}^{\mathbf{x},\mathbf{z}}C_{i^{\prime}+1,j}^{\mathbf{w},\mathbf{y}}$
and $\mu^{w,\ell}$ is the union of $\mu^{w,\ell+1}$ with
$\\{(\tau,{i^{\prime}+1})|\tau\in\mathbf{z}\cup\mathbf{w}\\}$. We say that
$A_{i,j}^{\mathbf{x},\mathbf{y}}\rightarrow
B_{i,i^{\prime}}^{\mathbf{x},\mathbf{z}}C_{i^{\prime}+1,j}^{\mathbf{w},\mathbf{y}}$
is _productive_ if $\mu^{w,\ell}$ strictly contains $\mu^{w,\ell+1}$. We
define the morphism nonStable that maps stable non-terminal and non-terminals
into $\epsilon$ and acts as the identity on the non-stable non-terminals.

We prove that if $\gamma_{\ell}\Rightarrow^{*}w$ where $\gamma_{\ell}$ is a
sequence over the non-terminals and terminals then
$\text{\sc{enumerate}}(\text{\sc{nonStable}}({\gamma_{\ell}}),\emptyset)$
returns the mapping $\mu^{w,\ell}$. The proof is done by a nested induction:
on $\ell-i$ for $i=0,\cdots\ell-1$ and an inner induction on the number of
productive productions applied throughout $\gamma_{\ell}\Rightarrow^{*}w$. If
there were no productive productions applied then $\mu^{w,\ell}=\emptyset$
and, in addition, this implies that
$\text{\sc{nonStable}}(\gamma_{\ell})=\epsilon$. Indeed
$\text{\sc{enumerate}}(\epsilon,\emptyset)$ returns $\emptyset$ which
completes the induction basis. For the induction step: Let us assume that
there is one or more productive production applied in
$\gamma_{\ell}\Rightarrow^{*}w$. This implies that there is at least one non-
stable non-terminal in $\gamma_{\ell}$. Let us find the left most non-stable
non-terminal $A_{i,j}^{\mathbf{x},\mathbf{y}}$ in $\gamma_{\ell}$ and denote
$\gamma_{\ell}=\alpha A\beta$. We can write

$\alpha
A\beta\Rightarrow^{*}\alpha^{\prime}A_{i,j}^{\mathbf{x},\mathbf{y}}\beta^{\prime}\Rightarrow\alpha^{\prime}B_{i,i^{\prime}}^{\mathbf{x},\mathbf{z}}C_{i^{\prime}+1,j}^{\mathbf{w},\mathbf{y}}\beta^{\prime}\Rightarrow^{*}w$

where no productive production was applied here $\alpha
A\beta\Rightarrow^{*}\alpha^{\prime}A_{i,j}^{\mathbf{x},\mathbf{y}}\beta^{\prime}$
and $A_{i,j}^{\mathbf{x},\mathbf{y}}\rightarrow
B_{i,i^{\prime}}^{\mathbf{x},\mathbf{z}}C_{i^{\prime}+1,j}^{\mathbf{w},\mathbf{y}}$
is a productive production. We then denote $\gamma_{\ell}=\alpha A\beta$,
$\gamma_{\ell^{\prime}}=\alpha^{\prime}A_{i,j}^{\mathbf{x},\mathbf{y}}\beta^{\prime}$,
and
$\gamma_{\ell^{\prime}+1}=\alpha^{\prime}B_{i,i^{\prime}}^{\mathbf{x},\mathbf{z}}C_{i^{\prime}+1,j}^{\mathbf{w},\mathbf{y}}\beta^{\prime}$.
We distinguish between two cases:

  * •

If $A$ is a non-stable non-terminal then it holds that
$A_{i,j}^{\mathbf{x},\mathbf{y}}\in\text{\sc{jump}}(A)$ and then we consider
the run $\text{\sc{enumerate}}(\text{\sc{nonStable}}(\alpha
A\beta),\emptyset)$ in which we enter the outer for loop with
$A_{i,j}^{\mathbf{x},\mathbf{y}}$ and choose from the output of applyProd the
pair $(\beta^{\prime},\mathsf{map}^{\prime})$ that corresponds with the
iteration in applyProd that matches
$A_{i,j}^{\mathbf{x},\mathbf{y}}\rightarrow
B_{i,i^{\prime}}^{\mathbf{x},\mathbf{z}}C_{i^{\prime}+1,j}^{\mathbf{w},\mathbf{y}}$.
Note that in this case $\mathsf{map}^{\prime}$ is the union
$\\{(\tau,{i^{\prime}+1})|x\in\mathbf{z}\cup\mathbf{w}\\}$. We then continue
with calling
$\text{\sc{enumerate}}(\text{\sc{nonStable}}(\gamma_{\ell^{\prime}}+1),\mathsf{map}^{\prime})$.
By induction hypothesis and by the definition of enumerate (and in particular
the fact that it accumulates the output mapping throughout the run), it holds
that $\text{\sc{enumerate}}(\text{\sc{nonStable}}(\alpha A\beta),\emptyset)$
returns $\mu^{w,\ell}$.

  * •

If $A$ is a stable non-terminal then it holds that
$A_{i,j}^{\mathbf{x},\mathbf{y}}\in\text{\sc{jump}}(A^{\prime})$ where
$A^{\prime}$ is the first non-stable non-terminal to the right of $A$. In this
case, the proof continues similarly.

We can finally conclude the desired claim.

######  Lemma D.5.

The procedure $\text{\sc{enumerate}}(S_{1,n}^{\mathbf{x},\mathbf{y}})$ outputs
every mapping $\mu^{w}$ that corresponds with a decorated word $w$ produced by
$\text{\sc{decorGrmr}}(G,\mathbf{d})$ exactly once.

######  Proof D.6.

Assume to the contrary that there is a mapping $\mu$ that is outputted twice.
Let us consider the two different call stacks of the procedure enumerate and
let us examine the first point where they differ. That is, in one stack
$\text{\sc{enumerate}}(\alpha,\mathsf{map})$ has called
$\text{\sc{enumerate}}(\alpha^{\prime},\mathsf{map}^{\prime})$ and in the
other stack $\text{\sc{enumerate}}(\alpha,\mathsf{map})$ has called the
procedure
$\text{\sc{enumerate}}(\alpha^{\prime\prime},\mathsf{map}^{\prime\prime})$.
This, in turn, implies that the applyProd returned two pairs
$(\beta,\mathsf{map})$ and $(\beta^{\prime},\mathsf{map}^{\prime})$ that are
different. Note that for any two pairs $(\beta,\mathsf{map})$ and
$(\beta^{\prime},\mathsf{map}^{\prime})$ in the output of applyProd it holds
that both $\mathsf{map}\neq\emptyset$ and
$\mathsf{map}^{\prime}\neq\emptyset$, and
$\mathsf{map}\neq\mathsf{map}^{\prime}$ since
$\text{\sc{decorGrmr}}(G_{\mathbf{d}})$ is unambiguous. This, combined with
the fact that enumerate accumulates its output mapping throughout the run, we
conclude that the mappings in both runs would be different. That is a
contradiction.

######  Proposition D.7.

The procedure applyProd is always called by enumerate with a non-terminal $A$
that is non-stable and appears in the lefthand side of some non-skippable
production.

######  Proof D.8.

This is straightforward from the definition of jump and the fact that
applyProd is called on a non-terminal in the image of jump. Note that jump
never maps a non-terminal into the empty set.

######  Proposition D.9.

The following hold:

  * •

The procedure applyProd always returns at least one pair
$(\beta,\mathsf{map})$ with $\mathsf{map}\neq\emptyset$.

  * •

For every pair $(\beta,\mathsf{map})$ that is in the output of applyProd it
holds that $\mathsf{map}\neq\emptyset$.

######  Proof D.10.

  * •

Straightforward from Proposition D.7.

  * •

If applyProd is called with $A_{i,j}^{\mathbf{x},\mathbf{y}}$ then by
Proposition D.7, it appears in the lefthand side of a non-skippable rule
$A_{i,j}^{\mathbf{x},\mathbf{y}}\rightarrow
B_{i,\ell}^{\mathbf{x},\mathbf{z}}C_{\ell+1,j}^{\mathbf{w},\mathbf{y}}$. Since
the rule is not skippable it holds that
$\mathbf{z}\cup\mathbf{w}\neq\emptyset$ which concludes the desired claim.

This concludes the proof.

######  Lemma D.11.

The procedure $\text{\sc{enumerate}}(S_{1,n}^{\mathbf{x},\mathbf{y}})$ outputs
with $O(k)$ delay between two consecutive mappings.

######  Proof D.12.

The size of each mapping that is outputted by enumerate is $O(k)$. Due to
Proposition D.9, before each recursive call to enumerate the mapping grows in
at least one pair. Therefore the stack call of enumerate is at most $k+1$.
Note that when the stack call of enum is of depth $i$ then in the last call to
enumerate (the top of the stack) the first element passed to it contains at
most $k-i$ non-stable non-terminals (since the mappings are always of fixed
size $k$).

procedure _$\text{\sc{applyProd}}(A_{i,j}^{\mathbf{x},\mathbf{y}})$_

initialize $\mathsf{map}=\emptyset$;

foreach  _non-skippable production of the form
$A_{i,j}^{\mathbf{x},\mathbf{y}}\rightarrow
B^{\mathbf{x},\mathbf{z}}_{i,\ell}C^{\mathbf{w},\mathbf{y}}_{\ell+1,j}$ _ do

$\mathsf{map}=\emptyset$;

foreach  _ $x\in\mathbf{z}\cup\mathbf{w}$_ do

$\mathsf{map}=\mathsf{map}\cup\\{(x,{\ell+1})\\}$

if  _ $B^{\mathbf{x},\mathbf{z}}_{i,\ell}$ and
$C^{\mathbf{w},\mathbf{y}}_{\ell+1,j}$ are non-stable_ then

$\beta=B^{\mathbf{x},\mathbf{z}}_{i,\ell}C^{\mathbf{w},\mathbf{y}}_{\ell+1,j}$

if  _ $B^{\mathbf{x},\mathbf{z}}_{i,\ell}$ is non-stable and
$C^{\mathbf{w},\mathbf{y}}_{\ell+1,j}$ is stable_ then

$\beta=B^{\mathbf{x},\mathbf{z}}_{i,\ell}$

if  _ $B^{\mathbf{x},\mathbf{z}}_{i,\ell}$ is stable and
$C^{\mathbf{w},\mathbf{y}}_{\ell+1,j}$ is non-stable_ then

$\beta=C^{\mathbf{w},\mathbf{y}}_{\ell+1,j}$

if  _ $B^{\mathbf{x},\mathbf{z}}_{i,\ell}$ and
$C^{\mathbf{w},\mathbf{y}}_{\ell+1,j}$ are stable_ then

$\beta=\epsilon$

output $(\beta,\mathsf{map})$

Algorithm 2 Apply Production Algorithm