FC-Datalog as a Framework for Efficient String Querying

Bell, Owen M.; Day, Joel D.; Freydenberger, Dominik D.

doi:10.4230/LIPIcs.ICDT.2025.29

FC-Datalog as a Framework for Efficient String Querying

Owen M. Bell

Loughborough University, UK Joel D. Day

Loughborough University, UK Dominik D. Freydenberger

Loughborough University, UK

Abstract

Core spanners are a class of document spanners that capture the core functionality of IBM’s AQL. $\mathsf{FC}$ is a logic on strings built around word equations that when extended with constraints for regular languages can be seen as a logic for core spanners. The recently introduced $\mathsf{FC}$ - $\mathsf{Datalog}$ extends $\mathsf{FC}$ with recursion, which allows us to define recursive relations for core spanners. Additionally, as $\mathsf{FC}$ - $\mathsf{Datalog}$ captures $\mathsf{P}$ , it is also a tractable version of $\mathsf{Datalog}$ on strings. This presents an opportunity for optimization.

We propose a series of $\mathsf{FC}$ - $\mathsf{Datalog}$ fragments with desirable properties in terms of complexity of model checking, expressive power, and efficiency of checking membership in the fragment. This leads to a range of fragments that all capture $\mathsf{LOGSPACE}$ , which we further restrict to obtain linear combined complexity. This gives us a framework to tailor fragments for particular applications. To showcase this, we simulate deterministic regex in a tailored fragment of $\mathsf{FC}$ - $\mathsf{Datalog}$ .

Keywords and phrases:

Information extraction, word equations, datalog, document spanners, regex

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Logic and databases

Related Version:

Full Version: https://arxiv.org/abs/2501.10344

Acknowledgements:

The authors would like to thank the anonymous reviewers of the current and previous versions for their detailed and helpful feedback.

Funding:

This work was supported by EPSRC grant EP/T033762/1.

Supplementary Material:

Data Accessibility: No data was generated or analyzed during this study.

DOI:

10.4230/LIPIcs.ICDT.2025.29

Event:

28th International Conference on Database Theory (ICDT 2025)

Editors:

Sudeepa Roy and Ahmet Kara

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

As a vast amount of valuable information is stored in unstructured textual data, the operation of extracting structured information from such data is crucial. This operation is the classical task known as Information Extraction (IE), and has applications from healthcare (see e.g. [39]) to social media analytics (see e.g. [5]). A popular approach to this task is the rule-based technique, which can be understood as querying a text as one queries a relational database. Document spanners are a framework for rule-based information extraction. We consider a recursive model connected to document spanners called $\mathsf{FC}$ - $\mathsf{Datalog}$ , which is based on the logic on strings $\mathsf{FC}$ and the query language $\mathsf{Datalog}$ . Thus, we first discuss the latter two, and the connection to document spanners, before moving to the former.

FC.

The theory of concatenation (short: $\mathsf{C}$ ) is a logic on strings with the infinite universe $\Upsigma^{\ast}$ . Introduced by Freydenberger and Peterfreund [16], $\mathsf{FC}$ is a finite model version of $\mathsf{C}$ which has a finite universe, a single word and all of its factors (contiguous subwords). As a result of this restriction, $\mathsf{FC}$ has decidable model checking and evaluation (see [16]). $\mathsf{FC}$ is built on word equations, equations of the form $xx\doteq yyy$ , where variables $x$ and $y$ represent words over a finite alphabet $\Upsigma$ . As a result, in $\mathsf{FC}$ we can reason directly over factors rather than intervals of positions as is the case for other logics on strings such as monadic second order logic ( $\mathsf{MSO}$ ) over a linear order. Furthermore, in $\mathsf{FC}$ we can compare factors of unbounded length, something which is not possible in $\mathsf{MSO}$ (see [16] for details). Word equations themselves are a natural way of expressing many typical properties of a string such as containing a square or being imprimitive (see e.g. [24]), and have previously been used for data management in other areas such as graph databases (see [6]).

Document Spanners and FC.

Introduced by Fagin, Kimelfeld, Reiss and Vansummeren [12], document spanners (or spanners) are a rule-based framework for Information Extraction. Spanners were introduced to capture the core functionality of AQL, a query language used for IBM’s SystemT. Informally, spanners are functions that take a text document as input and output a relation over intervals (called spans) from the document. Intuitively, primitive extractors (which are commonly regular expressions with capture variables called regex formulas) extract relations of spans, and these are then combined using relational algebra.

Many works on spanners, particularly in the area of enumeration (see e.g. [3, 13, 35]), have been concerned with the subclass of regular spanners, which are regex formulas extended with projection ( $\pi$ ), union ( $\cup$ ) and natural join ( $\Bowtie$ ). However, [12] showed that this subclass cannot express more than recognizable relations. The full class of spanners introduced by Fagin et al. [12] are called the core spanners as these achieve the original motivation of capturing the core functionality of AQL. Core spanners extend the regular spanners with string equality (denoted $\zeta^{=}$ ), an operation necessary to perform fundamental tasks such as reading multiple occurrences of a string. This added expressibility comes at the cost of reduced efficiency (see e.g. [14, 15]). Further extending the core spanners with set difference gives the class of generalized core spanners.

The logic $\mathsf{FC}$ has a tight connection to core spanners. In particular, the extension $\mathsf{FC[REG]}$ , which extends $\mathsf{FC}$ with constraints that decide membership of regular languages, captures the expressive power of generalized core spanners, and the existential-positive fragment $\mathsf{EP}$ - $\mathsf{FC[REG]}$ captures the expressive power of core spanners. Furthermore, there are polynomial time conversions between $\mathsf{FC[REG]}$ and generalized core spanners, and $\mathsf{EP}$ - $\mathsf{FC[REG]}$ and core spanners (see Section 5.2 of [16]). While spanners reason over intervals of positions, $\mathsf{FC}$ reasons directly over factors. When dealing with factors, unlike with intervals of positions, the default is not to distinguish between duplicates. However, simulating different intervals containing the same factor is easily done: we can simply store in addition to the factor, the prefix preceding it. On the other hand, eliminating duplicates when working with intervals, such as in spanners, is not so easily achieved. Due to the connection between the two models, we can use $\mathsf{FC}$ to gain insights into spanners; previous examples of work on $\mathsf{FC}$ that has produced results for spanners are [18] for tractability and [38] for inexpressibility.

Datalog.

A query language for relational databases, $\mathsf{Datalog}$ was introduced to perform operations that were not possible in earlier database languages such as graph transitive closure (see e.g. [1]). A $\mathsf{Datalog}$ program has a database of prepopulated extensional relations and a set of recursive rules that define new intensional relations. Semi-positive $\mathsf{Datalog}$ , which allows negation for atoms with extensional relation symbols, captures $\mathsf{P}$ on ordered structures (see e.g. [28]). Linear $\mathsf{Datalog}$ permits at most one atom with an intensional relation symbol in the body of every rule, and semi-positive linear $\mathsf{FC}$ - $\mathsf{Datalog}$ captures $\mathsf{NLOGSPACE}$ on ordered structures (see e.g. [20]). A more general definition of linear $\mathsf{Datalog}$ permits, in the body of every rule, at most one atom with an intensional relation symbol mutually recursive with the head relation symbol (see e.g [1]). We can evaluate body atoms that have other intensional relation symbols as subroutines, and so this extended definition does not affect the complexity. Linear $\mathsf{Datalog}$ also captures how recursion is done in SQL (see [30]).

The combined complexity of model checking $\mathsf{Datalog}$ is $\mathsf{EXP}$ -complete, even if the input database is empty, the universe is made up of only two elements, and the program has only a single rule (see [10, 20]). For linear $\mathsf{Datalog}$ it is $\mathsf{PSPACE}$ -complete, again even with an empty input database, a two-element universe, and a single rule (see [20]).

An earlier approach to adapting $\mathsf{Datalog}$ for querying strings is Sequence $\mathsf{Datalog}$ (see [7]), but this has an undecidable model checking problem. Furthermore, in the spanner setting Peterfreund, ten Cate, Fagin and Kimelfeld [33] introduced $\mathsf{RGXlog}$ , $\mathsf{Datalog}$ over regex formulas. $\mathsf{RGXlog}$ was motivated by the SystemT developers’ interest in recursion (for example, to implement context free grammars for natural language processing), and captures the complexity class $\mathsf{P}$ . As introduced in [32], $\mathsf{Spannerlog}\langle\mathsf{RGX}\rangle$ generalizes the spanner and relational model and has recently been implemented in [29]. $\mathsf{Spannerlog}\langle\mathsf{RGX}\rangle$ with stratified negation and restricted to string extensional relations also captures $\mathsf{P}$ (see Section 6 of [33]).

FC-Datalog.

Together with $\mathsf{FC}$ , Freydenberger and Peterfreund [16] also introduced $\mathsf{FC}$ - $\mathsf{Datalog}$ , which extends existential-positive $\mathsf{FC}$ ( $\mathsf{EP}$ - $\mathsf{FC}$ ) with recursion analogously to how $\mathsf{Datalog}$ extends existential-positive $\mathsf{FO}$ . It is worth pointing out that $\mathsf{EP}$ - $\mathsf{FC}$ is able to express the inequality of two strings (see e.g. Example 5.3 in [14]). As in $\mathsf{FC}$ , we have the finite universe of a single word and all of its factors. $\mathsf{FC}$ - $\mathsf{Datalog}$ has word equations instead of extensional relations. That is, $\mathsf{FC}$ - $\mathsf{Datalog}$ atoms are word equations or relations. In $\mathsf{FC}$ - $\mathsf{Datalog}$ we adopt the fixed point $\mathsf{Datalog}$ semantics.

Example 1.1.

The rules of an $\mathsf{FC}$ - $\mathsf{Datalog}$ program $P$ :

	$\displaystyle\text{Ans}()$	$\displaystyle\shortleftarrow\mathfrak{u}\doteq yz,\hskip 5.0ptE(y,z);$
	$\displaystyle E(x,y)$	$\displaystyle\shortleftarrow x\doteq\upvarepsilon,\hskip 5.0pty\doteq\upvarepsilon;$
	$\displaystyle E(x,y)$	$\displaystyle\shortleftarrow x\doteq\mathsf{a}u,\hskip 5.0pty\doteq\mathsf{b}v% ,\hskip 5.0ptE(u,v).$

$P$ defines the language $\mathcal{L}(P)\coloneqq\{\mathsf{a}^{n}\mathsf{b}^{n}\mid n\in\mathbb{N}\}$ . See Definition 2.1 for the semantics.

From Theorem 4.11 of [16], $\mathsf{FC}$ - $\mathsf{Datalog}$ captures the complexity class $\mathsf{P}$ . When considering efficiency, we are primarily interested in model checking, which relates practically to deciding if a tuple is in a relation. We can see $\mathsf{FC}$ - $\mathsf{Datalog}$ as a language for expressing relations that can be used in spanner selections. Because spanners reason over intervals of positions, expressing relations can become cumbersome as a relation holds such intervals, including all those that represent the same factor. In contrast, we can neatly express relations in $\mathsf{FC}$ - $\mathsf{Datalog}$ as we reason directly over factors and so a relation holds the factors themselves.

Example 1.2.

In $\mathsf{FC}$ - $\mathsf{Datalog}$ , we would express a relation that contains all factors that are squares with $R(x)\shortleftarrow x\doteq yy$ . In core spanners, we would express a relation that contains the positions of all factors that are squares with $\pi_{x}(\zeta^{=}_{y_{1},y_{2}}(\Upsigma^{\ast}x\{y_{1}\{\Upsigma^{\ast}\}y_{2% }\{\Upsigma^{\ast}\}\}\Upsigma^{\ast}))$ . See [12] for the full definition of core spanners.

Parallel to this, where model checking Sequence $\mathsf{Datalog}$ is undecidable, the same problem for $\mathsf{FC}$ - $\mathsf{Datalog}$ is in $\mathsf{P}$ , and so we can also see $\mathsf{FC}$ - $\mathsf{Datalog}$ as a tractable recursive query language for strings, independent of the connection to spanners. We aim to identify techniques that make recursion less expensive. We thus look to define restrictions that lead to more efficient fragments of $\mathsf{FC}$ - $\mathsf{Datalog}$ which also retain other desirable properties.

We focus on the model checking problem primarily through two different lenses: data complexity and combined complexity. In many cases for query languages it is reasonable to use data complexity as the queries are often significantly smaller than the data. In text-based settings on the other hand, features such as regular expressions can make queries large. Consequently, combined complexity remains an important consideration.

Deterministic Regex.

As the regular languages are often not enough to express what is required in practice, almost all modern programming languages (such as e.g. PERL, Python, and Java) do not implement only classical regular expressions, as introduced by Kleene [26], but regex, regular expressions extended with back-references. These are operators that match a repetition of a previously matched string, and whilst they do increase expressibility, they also lead to intractability of membership (see [2]). Freydenberger and Schmid [17] combined regex with the notion of determinism to define $\mathsf{DRX}$ , the class of deterministic regex, to obtain a tractable class of regex with more expressive power than deterministic regular expressions.

Other Related Models.

As well as $\mathsf{FC}$ - $\mathsf{Datalog}$ , there also exist other related models that capture $\mathsf{P}$ . These include positive Range Concatenation Grammars ( $\mathsf{PRCG}$ ) (see e.g. [8]), and Hereditary Elementary Formal Systems ( $\mathsf{HEFS}$ ) (see e.g. [31]), which do not have finite model semantics. The key difference of these models to $\mathsf{FC}$ - $\mathsf{Datalog}$ is in $\mathsf{FC}$ - $\mathsf{Datalog}$ ’s use of word equations, which are not present in other formalisms and are crucial for our restrictions that lead to efficient fragments.

Contributions of this Paper.

The only previously known complexity result for $\mathsf{FC}$ - $\mathsf{Datalog}$ is that it captures $\mathsf{P}$ . We first show that combined complexity of $\mathsf{FC}$ - $\mathsf{Datalog}$ is $\mathsf{EXP}$ -complete, and then perform an evaluation of different restrictions on $\mathsf{FC}$ - $\mathsf{Datalog}$ to identify fragments: with more efficient complexity of model checking, for both data and combined complexity; that do not overly sacrifice expressive power; and where membership in the fragment can be checked efficiently. As the semi-positive linear fragment of classical $\mathsf{Datalog}$ captures $\mathsf{NLOGSPACE}$ (on ordered structures), our first restriction is to adapt linearity to $\mathsf{FC}$ - $\mathsf{Datalog}$ . We show that linear $\mathsf{FC}$ - $\mathsf{Datalog}$ also captures $\mathsf{NLOGSPACE}$ and has $\mathsf{PSPACE}$ -complete combined complexity. Our second restriction is to remove nondeterminism. Here, we define deterministic linear $\mathsf{FC}$ - $\mathsf{Datalog}$ which captures $\mathsf{LOGSPACE}$ . But, checking whether a linear program is deterministic is as hard as satisfiability for word equations, a problem which is known to be $\mathsf{NP}$ -hard (see [4, 27]) and in nondeterministic linear space (see [23]). Therefore, we employ another restriction that we call one letter lookahead ( $\mathsf{OLLA}$ ) on the permitted word equations. Deterministic $\mathsf{OLLA}$ ( $\mathsf{DOLLA}$ ) $\mathsf{FC}$ - $\mathsf{Datalog}$ captures $\mathsf{LOGSPACE}$ and checking if an $\mathsf{OLLA}$ program is deterministic can be done in polynomial time, but its combined complexity is still $\mathsf{PSPACE}$ -complete. We thus make a final restriction that we call strictly decreasing ( $\mathsf{SD}$ ) and define $\mathsf{SD}$ - ${\mathsf{DOLLA}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ , which has linear combined complexity.

We therefore establish the endpoints of a range of fragments that all capture $\mathsf{LOGSPACE}$ ; at one end is deterministic linear $\mathsf{FC}$ - $\mathsf{Datalog}$ at at the other is $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ . We establish a trade-off in this range between how rich the fragment’s syntax is and how easy it is to check membership in the fragment, although fully mapping this range is left for future work. Furthermore, we show that we can obtain an $\mathsf{FC}$ - $\mathsf{Datalog}$ fragment with linear combined complexity, namely $\mathsf{SD}$ - ${\mathsf{DOLLA}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ . Consequently, we have paved the way to design tailored fragments for particular applications.

We then explain how we can view $\mathsf{FC}$ - $\mathsf{Datalog}$ programs from our range as generalized nondeterministic and deterministic multi-headed two-way finite automata, which are equivalent to nondeterministic and deterministic $\mathsf{LOGSPACE}$ Turing machines, respectively (see [25]). $\mathsf{FC}$ - $\mathsf{Datalog}$ fragments from our range allow for more flexibility than these automata models, for example $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ , tailored to simulate $\mathsf{DRX}$ , can be viewed as a generalization that permits performing nonregular string computations in the transitions.

Where in [17], to check if a regex matches a word we have to construct a technically involved automata model, we show that we can model this simply in $\mathsf{SD}$ - ${\mathsf{DOLLA+}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ . We also show how this tailored fragment allows us to conveniently and naturally write programs that are more concise. $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ permits additional deterministic components, but despite this maintains all of the desirable properties of $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ : it captures $\mathsf{LOGSPACE}$ , determinism can be checked in polynomial time, and its strictly decreasing variant $\mathsf{SD}$ - ${\mathsf{DOLLA+}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ has linear combined complexity. Finally, we show that as we can simulate $\mathsf{DRX}$ , another example of deterministic components that can be added to these tailored fragments are constraints that match $\mathsf{DRX}$ .

2 Preliminaries

Let $\mathbb{N}\coloneqq\{0,1,2,\ldots\}$ and $\mathbb{N}_{+}\coloneqq\{1,2,\ldots\}$ . We denote the empty set by $\emptyset$ and the cardinality of a set $S$ by $\absolutevalue{S}$ . Let $S\setminus S^{\prime}$ be the set difference of $S$ and $S^{\prime}$ , and let $\mathcal{P}(S)$ be the power set of $S$ . Let $A$ be some alphabet. For any two $u,v\in A^{\ast}$ , we use $u\cdot v$ , or simply $u v$ , for the concatenation of $u$ and $v$ . Let $\absolutevalue{u}$ denote the length of $u\in A^{\ast}$ . Let $\Upsigma$ be a finite alphabet that we call terminal symbols (or just terminals). We call any $w\in\Upsigma^{\ast}$ a word (or string). We use $\upvarepsilon$ to denote the empty word and let $\Upsigma^{+}=\Upsigma^{\ast}\setminus\{\upvarepsilon\}$ . A factor of a word $w$ is a word $t$ such that there exist $u,v\in\Upsigma^{\ast}$ with $w=u\cdot t\cdot v$ . In literature, a factor is sometimes called a contiguous subword.

For a tuple $\vec{t}$ , let its size $\absolutevalue{\vec{t}}$ be the number of components in $\vec{t}$ and $x\in\vec{t}$ denote that $x$ is a component of $\vec{t}$ . We refer to tuples where $\absolutevalue{\vec{t}}=1$ as singletons and omit the brackets in this case. A relation is a set of tuples of the same size, and is represented by a relation symbol.

Let $\Xi$ be a countably infinite set of variables where $\Upsigma\cap\Xi=\emptyset$ . A pattern is a word $\alpha\in(\Upsigma\cup\Xi)^{\ast}$ . We define $\text{Var}(\alpha$ ) as the set of variables in $\alpha$ . For two alphabets $A$ and $B$ , a homomorphism is a function $g:A^{\ast}\shortrightarrow B^{\ast}$ where $g(u)$ $\cdot$ $g(v)$ = $g(u\cdot v)$ holds for all $u,v\in A^{\ast}$ . A pattern substitution $\theta$ is a homomorphism $\theta:(\Upsigma\cup\Xi)^{\ast}\shortrightarrow(\Upsigma\cup\Xi)^{\ast}$ where $\theta(\mathsf{a})=\mathsf{a}$ for all $\mathsf{a}\in\Upsigma$ . We usually refer to a pattern substitution as simply a substitution. We denote the image of a pattern $\alpha$ under a substitution $\theta$ by $\theta(\alpha)$ . If $\theta(x)=\upvarepsilon$ for some variable $x$ , we say $\theta$ is erasing. For a tuple $\vec{t}=(\alpha_{1},\ldots,\alpha_{n})$ of patterns $\alpha_{1},\ldots,\alpha_{n}$ and a substitution $\theta$ , let $\theta(\vec{t})=(\theta(\alpha_{1}),\ldots,\theta(\alpha_{n}))$ .

For two patterns $\alpha,\beta\in(\Upsigma\cup\Xi)^{\ast}$ , an equation of the form $\alpha\doteq\beta$ is called a word equation. Under a substitution $\theta$ , the word equation $\upvarphi\coloneqq\alpha\doteq\beta$ holds if $\theta(\alpha)=\theta(\beta)$ , and we then say $\theta$ is a solution of $\upvarphi$ . If there exists a solution for $\upvarphi$ , then we say $\upvarphi$ is satisfiable. We say a conjunction of two word equations $\upvarphi_{1}\wedge\upvarphi_{2}$ is satisfiable if there exists a substitution $\theta$ that is a solution to both $\upvarphi_{1}$ and $\upvarphi_{2}$ . We say two word equations $\upvarphi_{1}$ and $\upvarphi_{2}$ contradict each other if their conjunction is not satisfiable. We say a pattern equation is a word equation of the form $x\doteq\alpha$ , where $x\in\Xi$ and $\alpha\in(\Upsigma\cup\Xi)^{\ast}$ . For every pattern equation $\upvarphi=x\doteq\alpha$ , we define $\text{Var}(\upvarphi)\coloneqq\{x\}\cup\text{Var}(\alpha)$ . The expressive power of conjunctions of pattern equations is the same as that for conjunctions of word equations as we can simulate a word equation $\alpha_{1}\doteq\alpha_{2}$ , for $\alpha_{1},\alpha_{2}\in(\Upsigma\cup\Xi)^{\ast}$ , using two pattern equations $x\doteq\alpha_{1}$ and $x\doteq\alpha_{2}$ for a new variable $x\in\Xi$ .

FC–Datalog.

An $\mathsf{FC}$ - $\mathsf{Datalog}$ atom is either a pattern equation, or a so-called relation atom of the form $R(y_{1},\ldots,y_{\text{ar}(R)})$ where $R$ is a relation symbol that has an arity $\text{ar}(R)\geq 0$ and $y_{1},\ldots,y_{\text{ar}(R)}\in\leavevmode\nobreak\ \Xi$ . Without loss of generality, we can assume that for every pattern equation atom $x\doteq\alpha$ , the variable $x$ does not occur in $\alpha$ because such equations reduce to trivial scenarios, as in Lemma 3.1 of [37]. For a relation atom $\upvarphi=R(y_{1},\ldots,y_{\text{ar}(R)})$ , we define $\text{Var}(\upvarphi$ ) = { $y_{1},\ldots,y_{\text{ar}(R)}$ }. For now, we assume each relation symbol $R$ has a corresponding relation $R$ . How relations are updated is specified in the following semantics.

Let $w\in\Upsigma^{\ast}$ be a word and let $\theta$ be a substitution. For a pattern equation atom $\upvarphi=x\doteq\alpha$ , we say $(w,\theta)\models\upvarphi$ if $\theta(x)=\theta(\alpha)$ and both $\theta(x)$ and $\theta(\alpha)$ are factors of $w$ . For a relation atom $\upvarphi=R(y_{1},\ldots,y_{\text{ar}(R)})$ , we say $(w,\theta)\models\upvarphi$ if $(\theta(y_{1}),\ldots,\theta(y_{\text{ar}(R)}))\in R$ and $\theta(y_{1}),\ldots,\theta(y_{\text{ar}(R)})$ are factors of $w$ . We represent the word $w$ that defines the universe with the distinguished universe variable $\mathfrak{u}$ , and use this as an input to an $\mathsf{FC}$ - $\mathsf{Datalog}$ program.

Let $\sigma$ be a relational vocabulary (see e.g. [11, 28] for a definition of $\mathsf{FO}$ and vocabularies). A conjunctive query is an $\mathsf{FO}[\sigma]$ formula of the form $\rho(\vec{x})\coloneqq\exists\vec{y}\colon\bigwedge_{i=1}^{n}\eta_{i}$ , where $\eta_{i}\coloneqq R_{i}(\vec{t}_{i})$ , each $R_{i}$ is a relation symbol in $\sigma$ , each $\vec{t}_{i}$ is a $\sigma$ -term, and $n\geq 1$ . We usually write this as $\rho\coloneqq\text{Ans}(\vec{x})\shortleftarrow\bigwedge_{i=1}^{n}\eta_{i}$ where $\vec{x}$ is the tuple of free variables. We call $\text{Ans}(\vec{x})$ the head of $\rho$ and $\bigwedge_{i=1}^{n}\eta_{i}$ the body of $\rho$ . If there are no free variables then $\rho$ is Boolean. We call the set of conjunctive queries $\mathsf{CQ}$ . We also use the output relation symbol Ans in $\mathsf{FC}$ - $\mathsf{Datalog}$ .

Definition 2.1.

An $\mathsf{FC}$ - $\mathsf{Datalog}$ program is a 3-tuple $P\coloneqq(\mathfrak{u}$ , $\mathcal{R}$ , $\Phi)$ , where:

$\blacksquare$

$\mathfrak{u}\in\Xi$ is the universe variable,
$\blacksquare$

$\mathcal{R}\supseteq\{\emph{\text{Ans}}\}$ is a finite set of relation symbols, where each $R\in\mathcal{R}$ has an arity $\text{ar}(R)\geq 0$ ,
$\blacksquare$

$\Phi$ is a finite set of rules of the form $R(x_{1},\ldots,x_{\text{ar}(R)})\shortleftarrow\upvarphi_{1},\ldots,\upvarphi_% {m}$ for some $m\geq 1$ , some $R\in\mathcal{R}$ , where for $1\leq i\leq m$ every $\upvarphi_{i}$ is an $\mathsf{FC}$ - $\mathsf{Datalog}$ atom, and for $0\leq j\leq\text{ar}(R)$ every $x_{j}$ occurs in some $\emph{\text{Var}}(\upvarphi_{i})$ .

Each element of $\Phi$ can be intuitively seen as a conjunctive query over $\mathsf{FC}$ - $\mathsf{Datalog}$ atoms and as for $\mathsf{CQ}$ , when $\text{ar}(\text{Ans})=0$ , the program is Boolean. For brevity, just $\Phi$ is used to represent the whole tuple if $\mathfrak{u}$ and $\mathcal{R}$ are clear from context. For a relation symbol $R\in\mathcal{R}$ , let $\Phi_{R}\subseteq\Phi$ be the subset of rules with head relation symbol $R$ . For an $\mathsf{FC}$ - $\mathsf{Datalog}$ rule $\rho$ we define $\mathsf{pe}(\rho)$ as the conjunction of all the pattern equations in $\rho$ .

Example 2.2.

For the $\mathsf{FC}$ - $\mathsf{Datalog}$ program $P=(\mathfrak{u},\{\text{Ans},E\},\Phi)$ where $\Phi$ are the rules defined in Example 1.1, we have the two subsets: $\Phi_{\text{Ans}}\coloneqq\{\text{Ans}()\shortleftarrow\mathfrak{u}\doteq yz,% \hskip 5.0ptE(y,z)\}$ and $\Phi_{E}\coloneqq\Phi\setminus\Phi_{\text{Ans}}$ . Let $\rho=E(x,y)\shortleftarrow x\doteq\mathsf{a}u,\hskip 3.00003pty\doteq\mathsf{b% }v,\hskip 3.00003ptE(u,v)$ . Then $\mathsf{pe}(\rho)=x\doteq\mathsf{a}u\wedge y\doteq\mathsf{b}v$ .

Let $\rho=R(x_{1},\ldots,x_{\text{ar}(R)}$ ) $\shortleftarrow\upvarphi_{1},\ldots,\upvarphi_{m}$ be an $\mathsf{FC}$ - $\mathsf{Datalog}$ rule and let $V\coloneqq\bigcup_{i=1}^{m}\text{Var}(\upvarphi_{i})$ . For a word $w\in\Upsigma^{\ast}$ , a $w$ -substitution is a substitution $\theta$ where $\theta(\mathfrak{u})=w$ and $\theta(x)$ is a factor of $w$ for each $x\in V$ . Using only $w$ -substitutions ensures that the universe is restricted to $w$ and its factors. For the rule $\rho$ and $w$ -substitution $\theta$ , we say $(w,\theta)\models\rho$ if for all $1\leq i\leq m$ we have $(w,\theta)\models\upvarphi_{i}$ . As we only consider the finite universe setting here, we are thus only considering $w$ -substitutions, and so refer to these as just substitutions for brevity.

We treat an $\mathsf{FC}$ - $\mathsf{Datalog}$ program $P=(\mathfrak{u},\mathcal{R},\Phi)$ as implicitly defining a vocabulary and define corresponding structures. An $\mathsf{FC}$ - $\mathsf{Datalog}$ structure $\mathfrak{A}_{P}$ consists of a fixed universe $w\in\Upsigma^{\ast}$ and all its factors, and an interpretation function $f^{\mathfrak{A}_{P}}$ that maps every relation symbol $R\in\mathcal{R}$ to an interpretation $R^{\mathfrak{A}_{P}}$ . For convenience, we also refer to $R^{\mathfrak{A}_{P}}$ as $R$ .

A program $P$ and a word $w$ define a structure $\llbracket P\rrbracket(w)$ incrementally. First, all $R\in\mathcal{R}$ are initialized to $\emptyset$ . Then, for each rule $R(x_{1},\ldots,x_{\text{ar}(R)}$ ) $\shortleftarrow\upvarphi_{1},\ldots,\upvarphi_{m}$ and $V\coloneqq\bigcup_{i=1}^{m}\text{Var}(\upvarphi_{i})$ , for every $w$ -substitution $\theta$ where $(w,\theta)\models\upvarphi_{i}$ , for all $1\leq i\leq m$ , add $(\theta(x_{1}),\ldots,\theta(x_{\text{ar}(R)}))$ to $R$ . We repeat this until all $R\in\mathcal{R}$ have stabilized. Then $\llbracket P\rrbracket(w)$ is the content of the Ans relation. This “filling up” of relations mirrors the fixed point semantics of classical $\mathsf{Datalog}$ .

The defined function $P$ that maps $w$ to $\text{ar}(\text{Ans})$ -ary tuples over factors of $w$ is well-defined (thus the fixed point is unique) and the “filling up” process terminates for every given $w$ . If $P$ is Boolean, $\llbracket P\rrbracket(w)$ is either $\emptyset$ or $\{()\}$ . We interpret these as $\mathsf{Reject}$ and $\mathsf{Accept}$ (resp.) and use this to define a language $\mathcal{L}(P)$ .

Example 2.3.

The $\mathsf{FC}$ - $\mathsf{Datalog}$ program $P=(\mathfrak{u},\{\text{Ans},R\},\Phi)$ where $\Phi$ is:

	$\displaystyle\text{Ans}()$	$\displaystyle\shortleftarrow\mathfrak{u}\doteq yy,\hskip 5.0ptR(y);$	$\displaystyle R(x)$	$\displaystyle\shortleftarrow x\doteq y\mathsf{a},\hskip 5.0ptR(y);$
	$\displaystyle R(x)$	$\displaystyle\shortleftarrow x\doteq\upvarepsilon;$	$\displaystyle R(x)$	$\displaystyle\shortleftarrow x\doteq y\mathsf{b},\hskip 5.0ptR(y).$

defines the language $\mathcal{L}(P)\coloneqq\{v\cdot v\mid v\in\{\mathsf{a},\mathsf{b}\}^{\ast}\}$ . Note that without the three rules that have $R$ in the head, we would define the language $\{v\cdot v\mid v\in\Upsigma^{\ast}\}$ .

We look at the model checking problem for $\mathsf{FC}$ - $\mathsf{Datalog}$ : given a Boolean $\mathsf{FC}$ - $\mathsf{Datalog}$ program $P$ and a word $w$ , is $w\in\mathcal{L}(P)$ ? We consider three perspectives: data complexity, where the program $P$ is fixed and only the word $w$ is considered input, expression complexity, where the word $w$ is fixed and only the program $P$ is considered input, and combined complexity, where both the word $w$ and program $P$ are considered input (for details, see [28]).

We call a subset of $\mathsf{FC}$ - $\mathsf{Datalog}$ programs a fragment. We say that a fragment $\mathcal{F}$ captures a complexity class $\mathbb{C}$ if $\mathbb{C}=\{\mathcal{L}(P)\mid P\in\mathcal{F}\}$ . Note that, following directly from the definitions, if $\mathcal{F}$ captures $\mathbb{C}$ , then the data complexity of $\mathcal{F}$ is $\mathbb{C}$ . The only complexity result that is known for $\mathsf{FC}$ - $\mathsf{Datalog}$ is that $\mathsf{FC}$ - $\mathsf{Datalog}$ captures $\mathsf{P}$ (see Theorem 4.11 of [16]), however, there are results for other versions of $\mathsf{FC}$ , such as those discussed in Section 1.

3 Efficient FC-Datalog

As $\mathsf{P}$ is often not considered efficient for data complexity, this presents an opportunity for optimization. We show that this is also the case for combined complexity.

Theorem 3.1.

Combined complexity of $\mathsf{FC}$ - $\mathsf{Datalog}$ is $\mathsf{EXP}$ -complete.

It is straightforward to see that as our universe is finite, the number of tuples we can add to the relations is exponential. We therefore have a naive evaluation algorithm of a loop with an exponential bound on the number of iterations, and an exponential number of steps in each iteration. We can also straightforwardly reduce classical $\mathsf{Datalog}$ evaluation to show $\mathsf{EXP}$ -hardness. Our main goal in this section is to identify fragments with lower data and combined complexity, and where membership in the fragment can be easily checked.

3.1 Linearity

There exists a fragment of classical $\mathsf{Datalog}$ that captures the complexity class $\mathsf{NLOGSPACE}$ on ordered structures (see e.g. [20]), namely the fragment of all semi-positive linear programs. As discussed in Section 1, there is a more general definition for linearity (see e.g. [1]) that does not affect complexity. Here we translate the more general linearity restriction from the relational setting to the text setting.

We define a relation $R\shortleftarrow R^{\prime}$ over relation symbols $R$ and $R^{\prime}$ if there exists a rule $\rho$ where $R$ is the head relation symbol and $R^{\prime}$ appears in the body. We denote the transitive closure of $\shortleftarrow$ by $\overset{+}{\shortleftarrow}$ , and two relation symbols $R$ and $R^{\prime}$ are mutually recursive if $R$ $\overset{+}{\shortleftarrow}$ $R^{\prime}$ and $R^{\prime}$ $\overset{+}{\shortleftarrow}$ $R$ .

Definition 3.2.

Let $P$ be an $\mathsf{FC}$ - $\mathsf{Datalog}$ program with rule set $\Phi$ . A rule $\rho\in\Phi$ is linear with respect to $P$ if at most one atom in the body of $\rho$ has a relation symbol with which the head relation symbol of $\rho$ is mutually recursive. If every $\rho\in\Phi$ is linear, then $P$ is linear.

Checking if a given $\mathsf{FC}$ - $\mathsf{Datalog}$ program is linear can be done in polynomial time with respect to the program’s number of rules, as it amounts to determining which pairs of relation symbols are mutually recursive, which is a syntactic criterion.

Example 3.3.

The $\mathsf{FC}$ - $\mathsf{Datalog}$ programs given in Example 1.1 and Example 2.3 are both linear $\mathsf{FC}$ - $\mathsf{Datalog}$ programs. An example $\mathsf{FC}$ - $\mathsf{Datalog}$ program that is not linear is the following program that retrieves all even length factors of the input word:

	$\displaystyle\text{Ans}(z)$	$\displaystyle\shortleftarrow z\doteq xy,\hskip 5.0pt\text{Ans}(x),\hskip 5.0pt% \text{Ans}(y);$
	$\displaystyle\text{Ans}(z)$	$\displaystyle\shortleftarrow z\doteq xy,\hskip 5.0ptL(x),\hskip 5.0ptL(y);$

and a rule $L(x)\shortleftarrow x\doteq\mathsf{a}$ for each $\mathsf{a}\in\Upsigma$ . This is not linear as Ans is mutually recursive with Ans, and the top rule has Ans in the head and two occurrences of Ans in the body.

While unrestricted $\mathsf{FC}$ - $\mathsf{Datalog}$ captures $\mathsf{P}$ , the restriction to linear $\mathsf{FC}$ - $\mathsf{Datalog}$ has substantially improved data complexity (Theorem 3.4) as well as combined complexity (Theorem 3.5).

Theorem 3.4.

Linear $\mathsf{FC}$ - $\mathsf{Datalog}$ captures $\mathsf{NLOGSPACE}$ .

We capture $\mathsf{NLOGSPACE}$ as we can simulate multi-headed two-way nondeterministic finite automata, which are equivalent to nondeterministic Turing machines with logarithmic space (see [25]). We will further discuss the connection to automata in Section 3.5.

Theorem 3.5.

Combined and expression complexity of linear $\mathsf{FC}$ - $\mathsf{Datalog}$ are $\mathsf{PSPACE}$ -complete.

On the other hand, we would like to lower both data complexity further than $\mathsf{NLOGSPACE}$ and combined complexity further than $\mathsf{PSPACE}$ . Furthermore, $\mathsf{PSPACE}$ -completeness occurs even on a single-character input. As such, we look for more efficient fragments.

3.2 Determinism

As linear $\mathsf{FC}$ - $\mathsf{Datalog}$ captures $\mathsf{NLOGSPACE}$ , it is natural to look at causes of nondeterminism and see if there is a corresponding fragment that captures $\mathsf{LOGSPACE}$ . For model checking, we evaluate $\mathsf{FC}$ - $\mathsf{Datalog}$ programs top-down.

Example 3.6.

We show a top-down evaluation of the program $P$ in Example 2.3 on the input word $w=\mathsf{abab}$ . The only rule we can apply first is $\text{Ans}()\shortleftarrow\mathfrak{u}\doteq yy,\hskip 5.0ptR(y)$ . As $\theta(\mathfrak{u})=w$ , we see that $\theta(y)=\mathsf{ab}$ , and we pass this into the relation $R$ . We can then only apply the rule $R(x)\shortleftarrow x\doteq y\mathsf{b},\hskip 5.0ptR(y)$ . As $\theta(x)=\mathsf{ab}$ , we have $\theta(y)=\mathsf{a}$ and we recurse on this value of $y$ . We then apply $R(x)\shortleftarrow x\doteq y\mathsf{a},\hskip 5.0ptR(y)$ and recurse on $\theta(y)=\upvarepsilon$ . We can then apply $R(x)\shortleftarrow x\doteq\upvarepsilon$ , and as this holds, we accept.

Based on this top-down evaluation model, we define two categories of variables.

Definition 3.7.

Let $\rho=R_{1}(x_{1},\ldots x_{m})\shortleftarrow R_{2}(y_{1},\ldots y_{n}),% \upvarphi_{1},\ldots,\upvarphi_{\ell}$ be a linear $\mathsf{FC}$ - $\mathsf{Datalog}$ rule where $R_{1}$ is mutually recursive with $R_{2}$ , and $\upvarphi_{i}$ is either a pattern equation or a relation atom with a relation symbol that is not mutually recursive with $R_{1}$ , for $1\leq i\leq\ell$ . We say $\rho$ ’s top variables $\mathsf{top}(\rho)$ are $(x_{1},\ldots,x_{m},\mathfrak{u})$ and $\rho$ ’s bottom variables $\mathsf{bottom}(\rho)$ are $(y_{1},\ldots,y_{n})$ .

In top-down evaluation, a rule’s top variables contain values that were passed down from a preceding rule’s evaluation, and its bottom variables contain the values that are passed down. A variable can be both a top and bottom variable.

Example 3.8.

Let $\rho$ be the linear $\mathsf{FC}$ - $\mathsf{Datalog}$ rule $R(x)\shortleftarrow x\doteq y\mathsf{a},\hskip 3.00003ptR(y)$ from Example 2.3. Then $\mathsf{top}(\rho)=(x,\mathfrak{u})$ and $\mathsf{bottom}(\rho)=(y)$ .

When evaluating a linear program, nondeterminism can occur in two ways: in choosing the values of the variables when processing a rule, which we call local nondeterminism, and in choosing which rule to process, which we call global nondeterminism. In order to remove all nondeterminism, we must ensure every program has both local and global determinism.

Let $w$ be the input word and let $\rho$ be a linear $\mathsf{FC}$ - $\mathsf{Datalog}$ rule. We define the relation $W_{\rho}$ to be all pairs $(\theta(\mathsf{top}(\rho)),\theta(\mathsf{bottom}(\rho)))$ , for all substitutions $\theta$ such that $(w,\theta)\leavevmode\nobreak\ \models\leavevmode\nobreak\ \mathsf{pe}(\rho)$ . For some $(\vec{t},\vec{t^{\prime}})\in W_{\rho}$ , we call $\vec{t}$ a top tuple and $\vec{t^{\prime}}$ a bottom tuple. Recall that as that we are working under finite model semantics, each value is a factor of the word $w$ . We define two criteria for determinism.

Definition 3.9.

A linear $\mathsf{FC}$ - $\mathsf{Datalog}$ program $P$ with rule set $\Phi$ is locally deterministic if for each $\rho\in\Phi$ , the relation $W_{\rho}$ is a partial function. $P$ is globally deterministic if for every relation symbol $R$ , for all pairs of distinct rules $\rho,\chi\in\Phi_{R}$ , there is no top tuple $\vec{t}$ such that $(\vec{t},\vec{t^{\prime}})$ in $W_{\rho}$ and $(\vec{t},\vec{t^{\prime\prime}})$ in $W_{\chi}$ , for some bottom tuples $t^{\prime}$ and $t^{\prime\prime}$ .

If $W_{\rho}$ is a partial function for some rule $\rho$ , then top-down evaluation of $\rho$ is locally deterministic as for every top tuple there is at most one bottom tuple. If a top tuple is a valid input for only one rule $\rho$ in $\Phi_{R}$ , for $\rho$ ’s head relation symbol $R$ , then we have global determinism as $\rho$ is the only rule we can process.

Definition 3.10.

Deterministic linear $\mathsf{FC}$ - $\mathsf{Datalog}$ is the set of linear $\mathsf{FC}$ - $\mathsf{Datalog}$ programs that are locally and globally deterministic.

Our condition is sufficiently strong as we precisely capture $\mathsf{LOGSPACE}$ .

Theorem 3.11.

Deterministic linear $\mathsf{FC}$ - $\mathsf{Datalog}$ captures $\mathsf{LOGSPACE}$ .

We capture $\mathsf{LOGSPACE}$ as we can simulate multi-headed two-way deterministic finite automata, which are equivalent to deterministic Turing machines with logarithmic space (see [25]). Unfortunately, where linearity for $\mathsf{FC}$ - $\mathsf{Datalog}$ can be checked in polynomial time, checking determinism for linear $\mathsf{FC}$ - $\mathsf{Datalog}$ is considerably more expensive, as the criteria we have to check is semantic rather than syntactic. A problem $p$ is word equations-hard if there exists a polynomial time reduction from word equation satisfiability to $p$ .

Proposition 3.12.

Checking local or global determinism of linear $\mathsf{FC}$ - $\mathsf{Datalog}$ is word equations-hard.

Word equation satisfiability is $\mathsf{NP}$ -hard [4, 27] and in nondeterministic linear space [23]. Closing this gap is a longstanding open problem. Thus, although we have reduced the complexity, we have lost efficient checking of membership in the fragment.

We now show that, in contrast to regular spanners, under standard complexity theoretic assumptions we cannot expect to have constant delay enumeration algorithms in our setting. A constant delay enumeration algorithm has a preprocessing phase, which often runs in linear time, and an enumeration phase that outputs solutions one by one, with constant time between any consecutive outputted solutions (see e.g. [36]).

Proposition 3.13.

If there exists a constant delay enumeration algorithm with polynomial preprocessing for deterministic linear $\mathsf{FC}$ - $\mathsf{Datalog}$ , then $\mathsf{P}=\mathsf{NP}$ .

As such, we do not look further into constant delay enumeration, and instead focus on identifying a fragment that has both reduced complexity and efficient membership checking, without compromising on expressive power.

3.3 One Letter Lookahead

In this subsection, we introduce a second fragment that captures $\mathsf{LOGSPACE}$ , but where we can check membership in the fragment in polynomial time. This fragment has a severely restricted syntax but can still simulate multi-headed two-way deterministic finite automata, demonstrating how little of $\mathsf{FC}$ - $\mathsf{Datalog}$ is required to retain this level of expressibility.

Definition 3.14.

Let $\rho$ be a linear $\mathsf{FC}$ - $\mathsf{Datalog}$ rule. Let $x,\in\mathsf{top}(\rho)$ , $y\in\mathsf{bottom}(\rho)$ , and $\mathsf{a}\in\Upsigma\cup\{\upvarepsilon\}$ . The rule $\rho$ is a one letter lookahead ( $\mathsf{OLLA}$ ) $\mathsf{FC}$ - $\mathsf{Datalog}$ rule if each pattern equation has either of the below forms:

$\blacksquare$

$x\doteq\upvarepsilon$ or $x\doteq x^{\prime}$ where $x^{\prime}\in\mathsf{top}(\rho)$ .
$\blacksquare$

$x\doteq y\mathsf{a}$ or $x\doteq\mathsf{a}y$ (deleting a letter from a top variable).
$\blacksquare$

$y\doteq x\mathsf{a}$ or $y\doteq\mathsf{a}x$ (adding a letter to a top variable).
$\blacksquare$

$\mathfrak{u}\doteq x\mathsf{a}z$ for $z\in\Xi$ where $z\notin\mathsf{top}(\rho)\cup\mathsf{bottom}(\rho)$ and $z$ does not occur elsewhere in $\rho$ (matching the next letter after a top variable in the input word).
$\blacksquare$

$\mathfrak{u}\doteq z\mathsf{a}x$ for $z\in\Xi$ where $z\notin\mathsf{top}(\rho)\cup\mathsf{bottom}(\rho)$ and $z$ does not occur elsewhere in $\rho$ (matching the first letter before a top variable in the input word).

We call an equation $x\doteq\upvarepsilon$ or $x\doteq x^{\prime}$ or where $\mathsf{a}=\upvarepsilon$ an $\upvarepsilon$ - $\mathsf{OLLA}$ pattern equation. Otherwise, we call an equation where $\mathsf{a}$ is on the right side of $x$ or $y$ a right $\mathsf{OLLA}$ pattern equation, and an equation where $\mathsf{a}$ is on the left side of $x$ or $y$ a left $\mathsf{OLLA}$ pattern equation.

Definition 3.15.

Let $P$ be a linear $\mathsf{FC}$ - $\mathsf{Datalog}$ program with rule set $\Phi$ . We say $P$ is a one letter lookahead ( $\mathsf{OLLA}$ ) $\mathsf{FC}$ - $\mathsf{Datalog}$ program if all $\rho\in\Phi$ are $\mathsf{OLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ rules, and for every relation symbol $R$ , for every rule $\rho\in\Phi_{R}$ , every variable $x\in\mathsf{top}(\rho)\cup\mathsf{bottom}(\rho)$ is not used in both left $\mathsf{OLLA}$ and right $\mathsf{OLLA}$ pattern equations. An $\mathsf{OLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program is deterministic (a $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program) if it is both locally and globally deterministic.

As such, in $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ , for every rule $\rho\in\Phi_{R}$ we can only use equations of the form $x\doteq x^{\prime}$ for $x,x^{\prime}\in\mathsf{top}(\rho)$ if $\absolutevalue{\Phi_{R}}=1$ or there exists a equation of the form $x=\upvarepsilon$ or $x=\mathsf{a}y$ or $x=y\mathsf{a}$ in $\mathsf{pe}(\rho)$ , for $y\in\mathsf{bottom}(\rho)$ . We call such a program guarded.

Example 3.16.

The linear $\mathsf{FC}$ - $\mathsf{Datalog}$ program $P$ given in Example 2.3 is not a $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program as the rule $\text{Ans}()\shortleftarrow\mathfrak{u}\doteq yy,\hskip 3.00003ptR(y)$ contains $\mathfrak{u}\doteq yy$ , which does not fit any of the permitted forms of pattern equations for an $\mathsf{OLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program.

The simplest $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program the authors could find that models the language of squares given in Example 2.3 is the one that models the multi-headed two-way DFA; this program first identifies the middle of the string and processes the two halves letter by letter. We now see that despite restricting the programs substantially, our new fragment $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ retains the expressive power of deterministic linear $\mathsf{FC}$ - $\mathsf{Datalog}$ .

Theorem 3.17.

$\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ captures $\mathsf{LOGSPACE}$ .

To check if a program is an $\mathsf{OLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program is straightforward. Checking if an $\mathsf{OLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program is deterministic is easier than in the general case, as the pattern equations are restricted to only match one letter at a time. When checking both local and global determinism, we only need to consider the case where rules do not contain contradicting pattern equations; if we have a rule with two pattern equations $\upvarphi_{1}$ and $\upvarphi_{2}$ that contradict each other, then as there are no solutions to $\upvarphi_{1}\wedge\upvarphi_{2}$ , this rule can never be applied. To check if a program is locally deterministic, we check that for every rule $\rho$ without pattern equations that contradict each other, every $x\in\mathsf{top}(\rho)$ appears in some pattern equation in $\mathsf{pe}(\rho)$ or $x\in\mathsf{bottom}(\rho)$ , and every $y\in\mathsf{bottom}(\rho)$ appears in some pattern equation in $\mathsf{pe}(\rho)$ or $y\in\mathsf{top}(\rho)$ . If so, then $W_{\rho}$ is a partial function. To check if a program is globally deterministic, we use profiles for its rules.

Definition 3.18.

Let $\rho$ be an $\mathsf{OLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ rule without pattern equations that contradict each other. We define a profile for $\rho$ as a function $pro_{\rho}\colon\mathsf{top}(\rho)\shortrightarrow\Upsigma\cup\{{\color[rgb]{% 0,0,0}\upvarepsilon,\bot}\}$ where:

pro_{\rho}(x)=\begin{cases}\mathsf{a}\text{ if there exists a pattern equation% $x\doteq y\mathsf{a}$ or $x\doteq\mathsf{a}y$}\text{, for $\mathsf{a}\in% \Upsigma$},\\ \upvarepsilon\text{ if there exists a pattern equation $x\doteq{\color[rgb]{% 0,0,0}\upvarepsilon}$,}\\ \bot\text{ otherwise.}\end{cases}

For $p,p^{\prime}\in\Upsigma\cup\{\upvarepsilon,\bot\}$ , we say $p$ and $p^{\prime}$ are in conflict if $p\neq\bot$ and $p^{\prime}\neq\bot$ , and $p\neq p^{\prime}$ . Let $\rho$ and $\chi$ be linear $\mathsf{FC}$ - $\mathsf{Datalog}$ rules with the same head relation symbol, with respective profiles $pro_{\rho}$ and $pro_{\chi}$ . Let $\mathsf{top}(\rho)=(x_{1},\ldots,x_{k})$ . Note that $\mathsf{top}(\rho)=\mathsf{top}(\chi)$ . We say $pro_{\rho}$ and $pro_{\chi}$ are in conflict if there exists some $x\in\mathsf{top}(\rho)$ where $pro_{\rho}(x)$ is in conflict with $pro_{\chi}(x)$ .

The function $pro_{\rho}$ represents how each $x\in\mathsf{top}(\rho)$ is processed in $\rho$ . In $\mathsf{OLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ , all we need to consider is the leftmost or rightmost letter of each $x$ , depending on whether $x$ is used in left or right $\mathsf{OLLA}$ pattern equations for rules with this head relation symbol.

Lemma 3.19.

A guarded $\mathsf{OLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program $P$ is globally deterministic if and only if for every relation symbol $R$ , for every pair of distinct rules $\rho,\chi\in\Phi_{R}$ , we have that $pro_{\rho}$ is in conflict with $pro_{\chi}$ .

This allows us to check if a given program is deterministic efficiently.

Proposition 3.20.

Local and global determinism for $\mathsf{OLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ can be decided in polynomial time.

We thus have a fragment where we have reduced data complexity to $\mathsf{LOGSPACE}$ , and without losing efficient checking of membership in the fragment. However, the combined complexity for $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ is the same as for linear $\mathsf{FC}$ - $\mathsf{Datalog}$ .

Theorem 3.21.

Combined complexity of $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ is $\mathsf{PSPACE}$ -complete.

3.4 Strictly Decreasing

Our next goal is more efficient combined complexity. We introduce a further restriction called strictly decreasing, and show that this leads to linear combined complexity.

Definition 3.22.

Let $P$ be a $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program with rule set $\Phi$ , and let $\Phi^{\prime}\subseteq\Phi$ be the rules containing both an atom with a relation symbol mutually recursive with the head relation symbol, and at least one pattern equation. Let $w$ be the input word. We say $P$ is strictly decreasing ( $\mathsf{SD}$ ) if for every rule $\rho\in\Phi^{\prime}$ that has head relation symbol $R$ :

1.

there exist $x\in\mathsf{top}(\rho)$ and $y\in\mathsf{bottom}(\rho)$ such that $y$ occurs in a pattern equation with $x$ and for all substitutions $\theta$ such that $(w,\theta)\models\rho$ we have $\absolutevalue{\theta(y)}<\absolutevalue{\theta(x)}$ , and
2.

if there exists a relation symbol $R^{\prime}$ in the body of $\rho$ that is mutually recursive with $R$ , for every rule $\chi\in\Phi^{\prime}$ with head relation symbol $R^{\prime}$ , condition 1 holds for some $x^{\prime}\in\mathsf{top}(\chi)$ and some $y^{\prime}\in\mathsf{bottom}(\chi)$ , and $\theta(y)=\theta^{\prime}(x^{\prime})$ for all substitutions $\theta$ such that $(w,\theta)\models\rho$ and all substitutions $\theta^{\prime}$ such that $(w,\theta^{\prime})\models\chi$ .

We now see that this restriction significantly improves the combined complexity. In fact, if the maximum relation symbol arity $k$ is fixed (or assumed to be much smaller than $\absolutevalue{w}$ ), then this is linear. Furthermore, the preprocessing is not dependent on the word $w$ .

Theorem 3.23.

Given a word $w$ and an $\mathsf{SD}$ - ${\mathsf{DOLLA}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program $P$ with $n$ relation symbols and maximum relation symbol arity $k$ , we can decide $w\in\mathcal{L}(P)$ in $\mathcal{O}(\absolutevalue{w}k)$ time after $\mathcal{O}(n\absolutevalue{\Upsigma})$ preprocessing.

In this section, we have defined the endpoints of an infinite range of fragments that all capture $\mathsf{LOGSPACE}$ . At one end, $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ has just enough syntax to simulate multi-headed two-way deterministic finite automata, but has easy checking of determinism. At the other end, deterministic linear $\mathsf{FC}$ - $\mathsf{Datalog}$ has a richer syntax but has more difficult checking of determinism. From this range, there is therefore the opportunity to extend $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ to make writing programs more natural and convenient. We will demonstrate such a situation in Section 4 when designing an appropriate fragment to model deterministic regex. Furthermore, although the fragments in this range do not reduce combined complexity any more than is the case for linear $\mathsf{FC}$ - $\mathsf{Datalog}$ , when we add the extra dimension of strictly decreasing, we can reduce the combined complexity to linear time.

3.5 FC-Datalog as Generalized Automata

As $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ , by design, permits just enough to simulate multi-headed two-way deterministic finite automata, we can naturally see a $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program as a generalization of such an automaton: every relation acts as a state, every rule acts as a transition, and every string variable acts a head which can be moved, added and deleted (as the number of heads can change per state). In each transition we read one letter and move, add, or delete the heads accordingly.

The fragments of $\mathsf{FC}$ - $\mathsf{Datalog}$ discussed in this paper can be seen as further generalizations. As the syntax grows, the connection to automata becomes less natural and checking determinism becomes harder. For example, Section 4 introduces $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ which allows word equations such as $x\doteq yy$ . Instead of just moving a head by one letter, this is an operation that either splits a memory in half or doubles it. We can then see a $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program as an generalized multi-headed two-way DFA where heads can read words rather than letters and that can perform nonregular string computations in the transitions.

We can also see an $\mathsf{OLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program as a generalized multi-headed two-way NFA, and a linear $\mathsf{FC}$ - $\mathsf{Datalog}$ program as a further generalization. There, reading letters at head positions is replaced with a declarative programming language that checks if the rule applies and computes the operations. The increasing gap to traditional automata is reflected in the fact that determinism is now expensive to verify. Finally, for $\mathsf{FC}$ - $\mathsf{Datalog}$ , we can understand every relation symbol in the body of a rule as a call of a subroutine, which splits the automaton into parallel copies, each of which must terminate. At this general level, however, the gap to traditional automata is so large the connection is no longer natural.

4 Applying the Framework: Simulating DRX

In this section, we tailor a fragment from our range to a specific application. We apply our model to simulate deterministic regex, introduced by Freydenberger and Schmid [17].

We define regular expressions as usual (see e.g. [1]) and extend these with back-references to define regex. For $x\in\Xi$ and a regular expression $\delta$ , we thus add the expressions $x$ and $\langle x\colon\delta\rangle$ to our syntax. The expression $\langle x\colon\delta\rangle$ matches $\delta$ and saves the string that is matched by $\delta$ in the memory $x$ . All further occurrences of $x$ are recalls of memory $x$ , which we match using the content of the variable that was saved earlier. For readability, we use $\cdot$ for concatenation.

Example 4.1.

Let $\gamma\coloneqq\langle x\colon(\mathsf{a}\vee\mathsf{b})^{+}\rangle\cdot% \mathsf{d}\cdot x$ . Then $\gamma$ matches all words $u\mathsf{d}u$ where $u\in\{\mathsf{a},\mathsf{b}\}^{+}$ .

Every regular expression can be converted into a finite automaton using the classical construction from Glushkov [19]. If the result of this construction is deterministic then the regular expression is deterministic. Deterministic regular expressions define a strict subclass of the regular languages, and have a more efficient membership problem than general regular expressions. For a deterministic regular expression $\gamma$ and a word $w$ , we can decide membership in $\mathcal{O}(\absolutevalue{\Upsigma}\absolutevalue{\gamma}+\absolutevalue{w}$ ) (see [9, 34]) or $\mathcal{O}(\absolutevalue{\gamma}+\absolutevalue{w}\log\log\absolutevalue{% \gamma})$ (see [21]).

Freydenberger and Schmid [17] combined regex and deterministic regular expressions to define deterministic regex, which can define nonregular languages, and have an efficient membership problem; this can be decided in $\mathcal{O}(\absolutevalue{\Upsigma}\absolutevalue{\gamma}n+k\absolutevalue{w})$ for a word $w$ and a deterministic regex $\gamma$ with $k$ distinct variables and $n$ total occurrences of terminal symbols or variable references (see Theorem 5 of [17]). Similarly to the Glushkov [19] construction, every regex $\gamma$ has a corresponding memory finite automaton with trap state ( $\mathsf{DTMFA}$ ) $M_{\gamma}$ (where the trap state handles memory recall failures), and $\gamma$ is deterministic if $M_{\gamma}$ is deterministic (see [17] for details). We call the class of all deterministic regex $\mathsf{DRX}$ .

Example 4.2.

Let $\gamma$ be the regex defined in Example 4.1, and let $\gamma^{\prime}\coloneqq\langle x\colon(\mathsf{a}\vee\mathsf{b})^{\ast}% \rangle\cdot x$ . Then $\mathcal{L}(\gamma)\coloneqq\{u\mathsf{d}u\mid u\in\{\mathsf{a},\mathsf{b}\}^{% \ast}\}$ and $\mathcal{L}(\gamma^{\prime})\coloneqq\{uu\mid u\in\{\mathsf{a},\mathsf{b}\}^{% \ast}\}$ . Then $\gamma\in\mathsf{DRX}$ and $\gamma^{\prime}\notin\mathsf{DRX}$ , as $M_{\gamma}$ is deterministic and $M_{\gamma^{\prime}}$ is not deterministic. Intuitively, this is because $\gamma$ has only one choice of when to stop matching the first $u$ , whereas $\gamma^{\prime}$ does not.

As in [17], we can assume w. l. o. g. that a regex does not recall empty memories, does not start to save into a memory that is already being saved to, and does not reset a memory to its initial value. We first show that for any $\gamma\in\mathsf{DRX}$ , we can express $\mathcal{L}(\gamma)$ in $\mathsf{SD}$ - ${\mathsf{DOLLA}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ , but with a large number of rules. We can parameterize such a program using the number of memories, terminal symbols and memory recalls in $\gamma$ . Here we use $\upvarepsilon$ -semantics¹¹1In $\upvarepsilon$ -semantics we treat everything not initialized as $\upvarepsilon$ (see e.g. Section 8.2.1 in [17])..

Theorem 4.3.

Let $\gamma\in\mathsf{DRX}$ have $k$ memories. Let the total number of terminal symbols and memory recalls in $\gamma$ be $n$ . We can express $\mathcal{L}(\gamma)$ with an $\mathsf{SD}$ - ${\mathsf{DOLLA}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program $P$ that has at most $k+n+2$ relation symbols and at most $k(\absolutevalue{\Upsigma}+1)+n(n+{\color[rgb]{0,0,0}3})+1$ rules.

The program $P$ that is the result of our construction requires a rule for each pair $(\mathsf{a},\ell)$ , for $\mathsf{a}\in\Upsigma$ and $0\leq\ell\leq k-1$ . This is because the syntax permits matching only one letter at a time, and so the program requires many rules to read memories letter by letter. We can achieve this with a much more concise program if we relax the syntax slightly, to what we call $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ . This sits between $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ and deterministic linear $\mathsf{FC}$ - $\mathsf{Datalog}$ , and it retains the polynomial time checking of determinism. To define this, we introduce the concept of a symbol being uniquely defined for top-down evaluation.

Definition 4.4.

Let $\rho$ be an $\mathsf{FC}$ - $\mathsf{Datalog}$ rule. We inductively define uniquely defined symbols: As base rules, the universe variable $\mathfrak{u}$ , every $\mathsf{a}\in\Upsigma$ and every $x\in\mathsf{top}(\rho)$ are uniquely defined. Then, if we have some pattern equation $\upvarphi$ where $\emph{\text{Var}}(\upvarphi)=\{x_{1},\ldots x_{k}\}$ and exactly one variable $x_{i}$ is not uniquely defined, then $x_{i}$ becomes uniquely defined.

Example 3.6 illustrates how top variables are uniquely defined for top-down evaluation.

Example 4.5.

Let $\rho=R_{1}(x_{1},x_{2})\shortleftarrow\upvarphi_{1},\upvarphi_{2},R_{2}(y_{1},% y_{2})$ be a linear $\mathsf{FC}$ - $\mathsf{Datalog}$ rule where $\upvarphi_{1}=x_{1}\doteq x_{2}y_{1}$ and $\upvarphi_{2}=y_{1}\doteq y_{2}y_{2}$ . From the base rules, $x_{1}$ and $x_{2}$ are uniquely defined. In the first iteration, as all $z\in\text{Var}(\upvarphi_{1})\setminus\{y_{1}\}$ are uniquely defined, $y_{1}$ is uniquely defined. In the second iteration, as all $z\in\text{Var}(\upvarphi_{2})\setminus\{y_{2}\}$ are uniquely defined, $y_{2}$ is uniquely defined.

In deterministic linear and $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ , by Definition 3.9, we ensure local determinism by requiring the relation $W_{\rho}$ to be a partial function for every rule $\rho$ , implicitly requiring every variable to be uniquely defined. We ensure local determinism in $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ by reasoning directly over uniquely defined variables.

Definition 4.6.

Let $P$ be a linear $\mathsf{FC}$ - $\mathsf{Datalog}$ program with rule set $\Phi$ . We say $P$ is a $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program if it is globally deterministic and for every rule $\rho\in\Phi$ , every variable that occurs in $\rho$ is uniquely defined.

Example 4.7.

The $\mathsf{FC}$ - $\mathsf{Datalog}$ program $P$ given in Example 2.3 that is not a $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program (see Example 3.16) is in fact a $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program.

We define $\mathsf{SD}$ for $\mathsf{DOLLA+}$ the same way as for $\mathsf{DOLLA}$ (Definition 3.22). $\mathsf{SD}$ - ${\mathsf{DOLLA+}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ generalizes $\mathsf{SD}$ - ${\mathsf{DOLLA}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ . We now show that despite being extensions, $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ retains the low data complexity (Theorem 4.8) and the efficient checking of determinism (Proposition 4.9) of $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ , and $\mathsf{SD}$ - ${\mathsf{DOLLA+}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ retains the low combined complexity of $\mathsf{SD}$ - ${\mathsf{DOLLA}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ (Theorem 4.8).

Theorem 4.8.

$\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ captures $\mathsf{LOGSPACE}$ , and given a word $w$ and an $\mathsf{SD}$ - ${\mathsf{DOLLA+}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program $P$ with $n$ relation symbols and maximum relation symbol arity $k$ , we can decide $w\in\mathcal{L}(P)$ in $\mathcal{O}(\absolutevalue{w}k)$ time after $\mathcal{O}(n\absolutevalue{\Upsigma})$ preprocessing.

Proposition 4.9.

Membership of $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ can be decided in polynomial time.

Where a $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program is required to match letter-by-letter, this is no longer the case for $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ , and a consequence of this is that we can simulate a deterministic regex with a much more concise $\mathsf{SD}$ - ${\mathsf{DOLLA+}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program.

Theorem 4.10.

Let $\gamma\in\mathsf{DRX}$ have $k$ memories. Let the total number of terminal symbols and memory recalls in $\gamma$ be $n$ . We can express $\mathcal{L}(\gamma)$ with an $\mathsf{SD}$ - ${\mathsf{DOLLA+}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program $P$ that has at most $n+2$ relation symbols and at most $n(n+{\color[rgb]{0,0,0}3})+1$ rules.

As the following example shows, the extra flexibility permitted in the syntax of $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ allows us to write programs much more conveniently than for $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ .

Example 4.11.

In $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ , we can process a memory $x^{\prime}_{n}$ , with a rule:

\displaystyle Q^{\prime}(u,x^{\prime}_{1},\ldots,x^{\prime}_{k})% \shortleftarrow Q(v,x_{1},\ldots,x_{k}),\hskip 5.0ptu\doteq x^{\prime}_{n}v,% \hskip 5.0ptx_{1}\doteq x^{\prime}_{1}x^{\prime}_{n},\hskip 5.0pt\ldots,\hskip 5% .0ptx_{k}\doteq x^{\prime}_{k}x^{\prime}_{n}.

In $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ , to process a memory $x^{\prime}_{n}$ , we use a new relation symbol $R_{\ell}$ and rules:

	$\displaystyle Q^{\prime}(u,x^{\prime}_{1},\ldots,x^{\prime}_{k})$	$\displaystyle\shortleftarrow Q(v,x_{1},\ldots,x_{k}),\hskip 5.0ptR_{\ell}(u,v,% x_{n},x^{\prime}_{1},x_{1},\ldots,x^{\prime}{\ell},x_{\ell});$
	$\displaystyle R_{\ell}(u,v,x^{\prime}_{1},x_{1},\ldots,x^{\prime}_{\ell},x_{% \ell})$	$\displaystyle\shortleftarrow x_{n}\doteq\upvarepsilon,\hskip 5.0ptu\doteq v,% \hskip 5.0ptx^{\prime}_{1}\doteq x_{1},\hskip 5.0pt\ldots,\hskip 5.0ptx^{% \prime}_{\ell}\doteq x_{\ell};$

and for every $\mathsf{a}\in\Upsigma$ a rule:

R_{\ell}(u,v,x_{n},x^{\prime}_{1},x_{1},\ldots,x^{\prime}_{\ell},x_{\ell})% \shortleftarrow x_{n}\doteq\mathsf{a}x^{\prime}_{n},\hskip 5.0ptu\doteq\mathsf% {a}u^{\prime},\hskip 5.0pt\\ x^{\prime\prime}_{1}\doteq x^{\prime}_{1}{\mathsf{a}},\hskip 5.0pt\ldots,% \hskip 5.0ptx^{\prime\prime}_{\ell}\doteq x^{\prime}_{\ell}\mathsf{a},\hskip 5% .0ptR_{\ell}(u^{\prime},v,x^{\prime}_{n},x^{\prime\prime}_{1},x_{1},\ldots,x^{% \prime\prime}_{\ell},x_{\ell}).

We have thus demonstrated the design of a tailored fragment in our range spanned by $\mathsf{DOLLA}$ and deterministic linear $\mathsf{FC}$ - $\mathsf{Datalog}$ , in this case by adding word equations with uniquely defined variables. The $\mathsf{DOLLA+}$ and $\mathsf{SD}$ - ${\mathsf{DOLLA+}}$ fragments retain the desirable properties of the restrictive $\mathsf{DOLLA}$ and $\mathsf{SD}$ - ${\mathsf{DOLLA}}$ fragments. As discussed in Section 3.5, we can see $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ as a generalization of multi-headed DFAs which is then not restricted to left-to-right parsing. As the next example shows, it can express context-free languages which cannot be recognized by a DPDA (see e.g [22]).

Example 4.12.

The palindrome language can be expressed deterministically by the $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program with the rules $\text{Ans}()\shortleftarrow R(\mathfrak{u})$ ; $R(x)\shortleftarrow x\doteq\upvarepsilon$ and the rules $R(x)\shortleftarrow x\doteq\mathsf{a}y\mathsf{a},\hskip 3.00003ptR(y)$ ; $R(x)\shortleftarrow x\doteq\mathsf{a}$ for each $\mathsf{a}\in\Upsigma$ . This evaluates in $\lceil\absolutevalue{w}/2\rceil+1$ steps, which is linear.

Furthermore, as we can simulate $\mathsf{DRX}$ , another feature that can be added to these tailored fragments are atoms that match $\mathsf{DRX}$ , which we can solve as a subroutine. We say a $\mathsf{DRX}$ -constraint is an expression $(x\dot{\in}\gamma)$ for $x\in\Xi$ and a deterministic regex $\gamma$ , that denotes $x$ is mapped to an element $u\in\mathcal{L}(\gamma)$ and $u$ is a factor of the input word $w$ .

To stay in $\mathsf{LOGSPACE}$ , we must ensure programs remain locally and globally deterministic. As $\mathsf{DRX}$ -constrains only check if a variable matches a deterministic regex, we can decide local determinism as we would without the $\mathsf{DRX}$ -constraints. To retain global determinism (Definition 3.9), if using deterministic regexes $\gamma_{1},\ldots,\gamma_{n}$ in multiple rules with the same head relation symbol, we must ensure that always at most one rule can accept. We thus need to decide if $\bigcap_{i=1}^{n}\mathcal{L}(\gamma_{i})=\emptyset$ . Unfortunately, intersection-emptiness for $\mathsf{DRX}$ is undecidable (see Theorem 9 of [17]). We say $\gamma\ \in\mathsf{DRX}$ is variable-star-free if each of its sub-regexes under a Kleene-star or Kleene-plus do not contain any variable operations. Intersection-emptiness for variable-star-free $\mathsf{DRX}$ is at least word equations-hard (see Proposition 8 of [17]). Thus, adding $\mathsf{DRX}$ -constraints means we lose efficient checking of determinism, another example of the trade-off between richer syntax and efficient determinism checking.

We can keep efficient determinism checking if we limit where we include $\mathsf{DRX}$ -constraints. If $\absolutevalue{\Phi_{R}}=1$ for some relation symbol $R$ , global determinism for $\Phi_{R}$ is inherent. If we limit inclusions of $\mathsf{DRX}$ -constraints to rules $\rho\in\Phi_{R}$ where $\absolutevalue{\Phi_{R}}=1$ , we can verify determinism by verifying every $\mathsf{DRX}$ -constraint is in such rules. We can decide this in polynomial time. Combining this with Proposition 4.9, we can check the whole program’s determinism in polynomial time.

Example 4.13.

The $\mathsf{FC}$ - $\mathsf{Datalog}$ program $P$ :

	$\displaystyle\text{Ans}()$	$\displaystyle\shortleftarrow R_{1}(\mathfrak{u});$	$\displaystyle R_{1}(x)$	$\displaystyle\shortleftarrow x\doteq\mathsf{a}y\mathsf{c},\hskip 5.0ptR_{1}(y);$
	$\displaystyle R_{2}(x)$	$\displaystyle\shortleftarrow(x\dot{\in}\langle y\colon(\mathsf{c}\vee\mathsf{d% })^{+}\rangle\cdot\mathsf{a}\cdot y);$	$\displaystyle R_{1}(x)$	$\displaystyle\shortleftarrow x\doteq\mathsf{b}y\mathsf{b},\hskip 5.0ptR_{2}(y).$

defines the language $\{\mathsf{a}^{z}\mathsf{b}w\mathsf{a}w\mathsf{b}\mathsf{c}^{z}\mid z\in\mathbb% {N}\wedge w\in\{\mathsf{c},\mathsf{d}\}^{\ast}\}$ , and $\absolutevalue{\Phi_{R_{2}}}=1$ , where $R_{2}$ is the only head relation symbol that has rules containing $\mathsf{DRX}$ -constraints.

$\blacktriangleright$ Remark 4.14.

Another extension of $\mathsf{FC}$ is $\mathsf{FC[REG]}$ , which captures the expressive power of generalized core spanners and also has $\mathsf{LOGSPACE}$ date complexity. However, $\mathsf{FC[REG]}$ does not capture $\mathsf{LOGSPACE}$ , as it cannot express the language $\{a^{n}b^{n}\mid n\in\mathbb{N}\}$ (see [16]). We can naturally express this language in $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ :

Example 4.15.

We can express $\{a^{n}b^{n}\mid n\in\mathbb{N}\}$ with the $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ program that has the rules: $\text{Ans}()\shortleftarrow R(\mathfrak{u});$ $R(x)\shortleftarrow x\doteq\upvarepsilon;$ and $R(x)\shortleftarrow x\doteq\mathsf{a}y\mathsf{b},\hskip 3.00003ptR(y)$ .

5 Conclusions and Future Work

Freydenberger and Peterfreund [16] recently proposed $\mathsf{FC}$ - $\mathsf{Datalog}$ as an extension of the logic $\mathsf{FC}$ with recursion. $\mathsf{FC}$ - $\mathsf{Datalog}$ captures the complexity class $\mathsf{P}$ and can be seen as a language for expressing relations that can be used in spanner selections. Furthermore, independent of the spanner connection, $\mathsf{FC}$ - $\mathsf{Datalog}$ can also be seen as a version of $\mathsf{Datalog}$ on strings with a decidable model checking problem, where the same problem for a previous approach towards $\mathsf{Datalog}$ on strings is undecidable. We first showed that combined complexity of $\mathsf{FC}$ - $\mathsf{Datalog}$ is $\mathsf{EXP}$ -complete, presenting an opportunity for optimization of model checking. In this paper, we identified fragments of $\mathsf{FC}$ - $\mathsf{Datalog}$ with an efficient model checking problem for both data and combined complexity by performing an analysis of four restrictions: linearity, determinism, one letter lookahead and strictly decreasing.

In Section 3.1 we proposed linear $\mathsf{FC}$ - $\mathsf{Datalog}$ , a fragment that captures $\mathsf{NLOGSPACE}$ . In Section 3.2 we identified and removed nondeterminism. Thus, deterministic linear $\mathsf{FC}$ - $\mathsf{Datalog}$ captures $\mathsf{LOGSPACE}$ . However, this restriction cannot be checked efficiently.

In Section 3.3 we imposed the one letter lookahead restriction on a program’s word equations to obtain deterministic $\mathsf{OLLA}$ ( $\mathsf{DOLLA}$ ) $\mathsf{FC}$ - $\mathsf{Datalog}$ that has both desirable properties: it captures $\mathsf{LOGSPACE}$ and determinism can be checked in polynomial time. We also showed that the combined complexity of model checking for both linear $\mathsf{FC}$ - $\mathsf{Datalog}$ and $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ is $\mathsf{PSPACE}$ -complete. Therefore, we added the further restriction of strictly decreasing ( $\mathsf{SD}$ ), and showed that $\mathsf{SD}$ - ${\mathsf{DOLLA}}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ has linear combined complexity. We thus established the endpoints of a range of $\mathsf{FC}$ - $\mathsf{Datalog}$ fragments that all capture $\mathsf{LOGSPACE}$ , and showed how we can restrict this further to reduce combined complexity to linear time. Hence, we have paved the way to construct further fragments which can be tailored for particular applications.

We illustrated tailoring a fragment in Section 4, where we constructed $\mathsf{DOLLA+}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ . This allows us to straightforwardly model deterministic regex without the need for a technically involved automata model. Yet, as for $\mathsf{DOLLA}$ $\mathsf{FC}$ - $\mathsf{Datalog}$ : we capture $\mathsf{LOGSPACE}$ , determinism can be checked in polynomial time, and strictly decreasing programs have linear combined complexity. We then showed how deterministic regex can be used as atoms, and how we can restrict where they are used so as to not compromise on these desirable properties.

As $\mathsf{LOGSPACE}$ is closed under complement, we can add stratified negation without affecting the combined complexity. Other convenient additions could include predicates that express properties of a string such as “is a letter”, and functions that build on these to express properties such as “is the first/last letter”. We could also add regular constraints: atoms that work in the same way as $\mathsf{DRX}$ -constraints, but match a classical regular expression rather than a deterministic regex, as in $\mathsf{FC[REG]}$ . Using these or other syntactic additions, we could further map the range between $\mathsf{DOLLA}$ and deterministic linear $\mathsf{FC}$ - $\mathsf{Datalog}$ , and investigate how these additions affect checking membership in the fragment. Furthermore, we could also look to find sufficient conditions to ensure membership can be easily checked.

There are structure criteria for conjunctive queries in $\mathsf{FC}$ ( $\mathsf{FC}$ - $\mathsf{CQ}$ ) that improve efficiency such as acyclicity, as demonstrated by Freydenberger and Thompson [18]. Every $\mathsf{FC}$ - $\mathsf{Datalog}$ rule can be seen as a conjunctive query in $\mathsf{FC}$ . We could therefore add such structure criteria to $\mathsf{FC}$ - $\mathsf{Datalog}$ rules and examine how this improves the complexity of $\mathsf{FC}$ - $\mathsf{Datalog}$ fragments further. Another direction for research is to look at inexpressibility for these fragments. However, even for $\mathsf{FC}$ (as opposed to $\mathsf{FC}$ - $\mathsf{Datalog}$ ), finding inexpressibility results is challenging (see [38]). Another logical next step is to use our restrictions for $\mathsf{FC}$ - $\mathsf{Datalog}$ to identify natural fragments in the spanner setting with desirable properties.

Finally, as we can also see $\mathsf{FC}$ - $\mathsf{Datalog}$ as a generalization of range concatenation grammars ( $\mathsf{RCG}$ ) (see [16]), parsing techniques for these grammars such as the algorithm in Boullier [8] could be adapted to $\mathsf{FC}$ - $\mathsf{Datalog}$ .

References

[1] Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/.
[2] Alfred V. Aho. Algorithms for Finding Patterns in Strings, pages 255–300. MIT Press, 1991.
[3] Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth. Constant-Delay Enumeration for Nondeterministic Document Spanners. SIGMOD Rec., 49(1):25–32, 2020. doi:10.1145/3422648.3422655.
[4] Dana Angluin. Finding Patterns Common to a Set of Strings. J. Comput. Syst. Sci., 21(1):46–62, 1980. doi:10.1016/0022-0000(80)90041-0.
[5] Mena Badieh Habib Morgan and Maurice van Keulen. Information Extraction for Social Media. In Proc. SWAIE, pages 9–16, 2014. doi:10.3115/v1/W14-6202.
[6] Pablo Barceló and Pablo Muñoz. Graph Logics with Rational Relations: The Role of Word Combinatorics. ACM Trans. Comput. Logic, 18(2), 2017. doi:10.1145/3070822.
[7] Anthony J. Bonner and Giansalvatore Mecca. Sequences, Datalog, and Transducers. J. Comput. Syst. Sci., 57(3):234–259, 1998. doi:10.1006/jcss.1998.1562.
[8] Pierre Boullier. Range Concatenation Grammars, pages 269–289. New Developments in Parsing Technology. Springer, 2004. doi:10.1007/1-4020-2295-6_13.
[9] Anne Brüggemann-Klein. Regular expressions into finite automata. Theoretical Computer Science, 120(2):197–213, 1993. doi:10.1016/0304-3975(93)90287-4.
[10] Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov. Complexity and Expressive Power of Logic Programming. ACM Computing Surveys, 33(3):374–425, 2001. doi:10.1145/502807.502810.
[11] Heinz-Dieter Ebbinghaus and Jörg Flum. Finite Model Theory. Springer Monographs in Mathematics, 2nd edition, 1999.
[12] Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. Document Spanners: A Formal Approach to Information Extraction. J. ACM, 62(2), 2015. doi:10.1145/2699442.
[13] Fernando Florenzano, Cristian Riveros, Martín Ugarte, Stijn Vansummeren, and Domagoj Vrgoč. Efficient Enumeration Algorithms for Regular Document Spanners. ACM Trans. Database Syst., 45(1), 2020. doi:10.1145/3351451.
[14] Dominik D. Freydenberger. A Logic for Document Spanners. Theory of Computing Systems, 63(7):1679–1754, 2019. doi:10.1007/s00224-018-9874-1.
[15] Dominik D. Freydenberger and Mario Holldack. Document Spanners: From Expressive Power to Decision Problems. Theory Comput. Syst., 62(4):854–898, 2018. doi:10.1007/S00224-017-9770-0.
[16] Dominik D. Freydenberger and Liat Peterfreund. The Theory of Concatenation over Finite Models. In Proc. ICALP 2021, pages 130:1–130:17, 2021. doi:10.4230/LIPIcs.ICALP.2021.130.
[17] Dominik D. Freydenberger and Markus L. Schmid. Deterministic regular expressions with back-references. J. Comput. Syst. Sci., 105:1–39, 2019. doi:10.1016/J.JCSS.2019.04.001.
[18] Dominik D. Freydenberger and Sam M. Thompson. Splitting Spanner Atoms: A Tool for Acyclic Core Spanners. In Proc. ICDT 2022, pages 10:1–10:18, 2022. doi:10.4230/LIPIcs.ICDT.2022.10.
[19] V M Glushkov. The Absract Theory of Automata. Russian Mathematical Surveys, 16(5), 1961. doi:10.1070/RM1961v016n05ABEH004112.
[20] Georg Gottlob and Christos Papadimitriou. On the complexity of single-rule datalog queries. Information and Computation, 183(1):104–122, 2003. doi:10.1016/S0890-5401(03)00012-9.
[21] B. Groz and S. Maneth. Efficient testing and matching of deterministic regular expressions. J. Comp. Syst. Sci., 89:372–399, 2017. doi:10.1016/j.jcss.2017.05.013.
[22] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 3rd edition, 2007.
[23] Artur Jez. Word Equations in Nondeterministic Linear Space. In Proc. ICALP 2017, pages 95:1–95:13, 2017. doi:10.4230/LIPIcs.ICALP.2017.95.
[24] Juhani Karhumäki, Filippo Mignosi, and Wojciech Plandowski. The expressibility of languages and relations by word equations. J. ACM, 47(3):483–505, 2000. doi:10.1145/337244.337255.
[25] K. N. King. Alternating Multihead Finite Automata. Theoretical Computer Science, 61(2):149–174, 1988. doi:10.1016/0304-3975(88)90122-3.
[26] S. C. Kleene. Representation of Events in Nerve Nets and Finite Automata, pages 3–42. Princeton University Press, 1956. doi:10.1515/9781400882618-002.
[27] Antoni Koscielski and Leszek Pacholski. Complexity of Makanin’s algorithm. J. ACM, 43(4):670–684, 1996. doi:10.1145/234533.234543.
[28] Leonid Libkin. Complexity of First-Order Logic, pages 87–111. Elements of Finite Model Theory. Springer, 2004. doi:10.1007/978-3-662-07003-1_6.
[29] Dean Light, Ahmad Aiashi, Mahmoud Diab, Daniel Nachmias, Stijn Vansummeren, and Benny Kimelfeld. SpannerLib: Embedding Declarative Information Extraction in an Imperative Workflow. Proc. VLDB Endow., 17(12):4281–4284, 2024. doi:10.14778/3685800.3685855.
[30] Carsten Lutz and Leif Sabellek. Ontology-Mediated Querying with the Description Logic EL: Trichotomy and Linear Datalog Rewritability. In IJCAI 2017, pages 1181–1187, 2017. doi:10.24963/ijcai.2017/164.
[31] S. Miyano, A. Shinohara, and T. Shinohara. Which classes of Elementary Formal Systems are polynomial-time learnable? In Proc. ALT 1992, pages 139–150, 1992.
[32] Yoav Nahshon, Liat Peterfreund, and Stijn Vansummeren. Incorporating information extraction in the relational database model. In Proc. WebDB 2016, 2016. doi:10.1145/2932194.2932200.
[33] Liat Peterfreund, Balder ten Cate, Ronald Fagin, and Benny Kimelfeld. Recursive Programs for Document Spanners. In Proc. ICDT 2019, pages 13:1–13:18, 2019. doi:10.4230/LIPIcs.ICDT.2019.13.
[34] J. L. Ponty, D. Ziadi, and J. M. Champarnaud. A new quadratic algorithm to convert a regular expression into an automaton. In Automata Implementation, pages 109–119. Springer, 1997.
[35] Markus L. Schmid and Nicole Schweikardt. Spanner Evaluation over SLP-Compressed Documents. In Proc. PODS 2021, pages 153–165, 2021. doi:10.1145/3452021.3458325.
[36] Luc Segoufin. Enumerating with constant delay the answers to a query. In Proc. ICDT 2013, pages 10–20, 2013. doi:10.1145/2448496.2448498.
[37] Sam M. Thompson and Dominik D. Freydenberger. Languages Generated by Conjunctive Query Fragments of FC[REG]. In Proc. DLT 2023, pages 233–245, 2023. doi:10.1007/978-3-031-33264-7_19.
[38] Sam M. Thompson and Dominik D. Freydenberger. Generalized Core Spanner Inexpressibility via Ehrenfeucht-Fraïssé Games for FC. Proc. ACM Manag. Data, 2(2), 2024. doi:10.1145/3651143.
[39] Yanshan Wang, Liwei Wang, Majid Rastegar-Mojarad, Sungrim Moon, Feichen Shen, Naveed Afzal, Sijia Liu, Yuqun Zeng, Saeed Mehrabi, Sunghwan Sohn, and Hongfang Liu. Clinical information extraction applications: A literature review. Journal of Biomedical Informatics, 77:34–49, 2018. doi:10.1016/j.jbi.2017.11.011.

[bib.bib1] [1] Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/.

[bib.bib2] [2] Alfred V. Aho. Algorithms for Finding Patterns in Strings, pages 255–300. MIT Press, 1991.

[bib.bib3] [3] Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth. Constant-Delay Enumeration for Nondeterministic Document Spanners. SIGMOD Rec., 49(1):25–32, 2020. doi:10.1145/3422648.3422655.

[bib.bib4] [4] Dana Angluin. Finding Patterns Common to a Set of Strings. J. Comput. Syst. Sci., 21(1):46–62, 1980. doi:10.1016/0022-0000(80)90041-0.

[bib.bib5] [5] Mena Badieh Habib Morgan and Maurice van Keulen. Information Extraction for Social Media. In Proc. SWAIE, pages 9–16, 2014. doi:10.3115/v1/W14-6202.

[bib.bib6] [6] Pablo Barceló and Pablo Muñoz. Graph Logics with Rational Relations: The Role of Word Combinatorics. ACM Trans. Comput. Logic, 18(2), 2017. doi:10.1145/3070822.

[bib.bib7] [7] Anthony J. Bonner and Giansalvatore Mecca. Sequences, Datalog, and Transducers. J. Comput. Syst. Sci., 57(3):234–259, 1998. doi:10.1006/jcss.1998.1562.

[bib.bib8] [8] Pierre Boullier. Range Concatenation Grammars, pages 269–289. New Developments in Parsing Technology. Springer, 2004. doi:10.1007/1-4020-2295-6_13.

[bib.bib9] [9] Anne Brüggemann-Klein. Regular expressions into finite automata. Theoretical Computer Science, 120(2):197–213, 1993. doi:10.1016/0304-3975(93)90287-4.

[bib.bib10] [10] Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov. Complexity and Expressive Power of Logic Programming. ACM Computing Surveys, 33(3):374–425, 2001. doi:10.1145/502807.502810.

[bib.bib11] [11] Heinz-Dieter Ebbinghaus and Jörg Flum. Finite Model Theory. Springer Monographs in Mathematics, 2nd edition, 1999.

[bib.bib12] [12] Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. Document Spanners: A Formal Approach to Information Extraction. J. ACM, 62(2), 2015. doi:10.1145/2699442.

[bib.bib13] [13] Fernando Florenzano, Cristian Riveros, Martín Ugarte, Stijn Vansummeren, and Domagoj Vrgoč. Efficient Enumeration Algorithms for Regular Document Spanners. ACM Trans. Database Syst., 45(1), 2020. doi:10.1145/3351451.

[bib.bib14] [14] Dominik D. Freydenberger. A Logic for Document Spanners. Theory of Computing Systems, 63(7):1679–1754, 2019. doi:10.1007/s00224-018-9874-1.

[bib.bib15] [15] Dominik D. Freydenberger and Mario Holldack. Document Spanners: From Expressive Power to Decision Problems. Theory Comput. Syst., 62(4):854–898, 2018. doi:10.1007/S00224-017-9770-0.

[bib.bib16] [16] Dominik D. Freydenberger and Liat Peterfreund. The Theory of Concatenation over Finite Models. In Proc. ICALP 2021, pages 130:1–130:17, 2021. doi:10.4230/LIPIcs.ICALP.2021.130.

[bib.bib17] [17] Dominik D. Freydenberger and Markus L. Schmid. Deterministic regular expressions with back-references. J. Comput. Syst. Sci., 105:1–39, 2019. doi:10.1016/J.JCSS.2019.04.001.

[bib.bib18] [18] Dominik D. Freydenberger and Sam M. Thompson. Splitting Spanner Atoms: A Tool for Acyclic Core Spanners. In Proc. ICDT 2022, pages 10:1–10:18, 2022. doi:10.4230/LIPIcs.ICDT.2022.10.

[bib.bib19] [19] V M Glushkov. The Absract Theory of Automata. Russian Mathematical Surveys, 16(5), 1961. doi:10.1070/RM1961v016n05ABEH004112.

[bib.bib20] [20] Georg Gottlob and Christos Papadimitriou. On the complexity of single-rule datalog queries. Information and Computation, 183(1):104–122, 2003. doi:10.1016/S0890-5401(03)00012-9.

[bib.bib21] [21] B. Groz and S. Maneth. Efficient testing and matching of deterministic regular expressions. J. Comp. Syst. Sci., 89:372–399, 2017. doi:10.1016/j.jcss.2017.05.013.

[bib.bib22] [22] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 3rd edition, 2007.

[bib.bib23] [23] Artur Jez. Word Equations in Nondeterministic Linear Space. In Proc. ICALP 2017, pages 95:1–95:13, 2017. doi:10.4230/LIPIcs.ICALP.2017.95.

[bib.bib24] [24] Juhani Karhumäki, Filippo Mignosi, and Wojciech Plandowski. The expressibility of languages and relations by word equations. J. ACM, 47(3):483–505, 2000. doi:10.1145/337244.337255.

[bib.bib25] [25] K. N. King. Alternating Multihead Finite Automata. Theoretical Computer Science, 61(2):149–174, 1988. doi:10.1016/0304-3975(88)90122-3.

[bib.bib26] [26] S. C. Kleene. Representation of Events in Nerve Nets and Finite Automata, pages 3–42. Princeton University Press, 1956. doi:10.1515/9781400882618-002.

[bib.bib27] [27] Antoni Koscielski and Leszek Pacholski. Complexity of Makanin’s algorithm. J. ACM, 43(4):670–684, 1996. doi:10.1145/234533.234543.

[bib.bib28] [28] Leonid Libkin. Complexity of First-Order Logic, pages 87–111. Elements of Finite Model Theory. Springer, 2004. doi:10.1007/978-3-662-07003-1_6.

[bib.bib29] [29] Dean Light, Ahmad Aiashi, Mahmoud Diab, Daniel Nachmias, Stijn Vansummeren, and Benny Kimelfeld. SpannerLib: Embedding Declarative Information Extraction in an Imperative Workflow. Proc. VLDB Endow., 17(12):4281–4284, 2024. doi:10.14778/3685800.3685855.

[bib.bib30] [30] Carsten Lutz and Leif Sabellek. Ontology-Mediated Querying with the Description Logic EL: Trichotomy and Linear Datalog Rewritability. In IJCAI 2017, pages 1181–1187, 2017. doi:10.24963/ijcai.2017/164.

[bib.bib31] [31] S. Miyano, A. Shinohara, and T. Shinohara. Which classes of Elementary Formal Systems are polynomial-time learnable? In Proc. ALT 1992, pages 139–150, 1992.

[bib.bib32] [32] Yoav Nahshon, Liat Peterfreund, and Stijn Vansummeren. Incorporating information extraction in the relational database model. In Proc. WebDB 2016, 2016. doi:10.1145/2932194.2932200.

[bib.bib33] [33] Liat Peterfreund, Balder ten Cate, Ronald Fagin, and Benny Kimelfeld. Recursive Programs for Document Spanners. In Proc. ICDT 2019, pages 13:1–13:18, 2019. doi:10.4230/LIPIcs.ICDT.2019.13.

[bib.bib34] [34] J. L. Ponty, D. Ziadi, and J. M. Champarnaud. A new quadratic algorithm to convert a regular expression into an automaton. In Automata Implementation, pages 109–119. Springer, 1997.

[bib.bib35] [35] Markus L. Schmid and Nicole Schweikardt. Spanner Evaluation over SLP-Compressed Documents. In Proc. PODS 2021, pages 153–165, 2021. doi:10.1145/3452021.3458325.

[bib.bib36] [36] Luc Segoufin. Enumerating with constant delay the answers to a query. In Proc. ICDT 2013, pages 10–20, 2013. doi:10.1145/2448496.2448498.

[bib.bib37] [37] Sam M. Thompson and Dominik D. Freydenberger. Languages Generated by Conjunctive Query Fragments of FC[REG]. In Proc. DLT 2023, pages 233–245, 2023. doi:10.1007/978-3-031-33264-7_19.

[bib.bib38] [38] Sam M. Thompson and Dominik D. Freydenberger. Generalized Core Spanner Inexpressibility via Ehrenfeucht-Fraïssé Games for FC. Proc. ACM Manag. Data, 2(2), 2024. doi:10.1145/3651143.

[bib.bib39] [39] Yanshan Wang, Liwei Wang, Majid Rastegar-Mojarad, Sungrim Moon, Feichen Shen, Naveed Afzal, Sijia Liu, Yuqun Zeng, Saeed Mehrabi, Sunghwan Sohn, and Hongfang Liu. Clinical information extraction applications: A literature review. Journal of Biomedical Informatics, 77:34–49, 2018. doi:10.1016/j.jbi.2017.11.011.

FC-Datalog as a Framework for Efficient String Querying

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

Supplementary Material:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

FC.

Document Spanners and FC.

Datalog.

FC-Datalog.

Example 1.1.

Example 1.2.

Deterministic Regex.

Other Related Models.

Contributions of this Paper.

2 Preliminaries

FC–Datalog.

Definition 2.1.

Example 2.2.

Example 2.3.

3 Efficient FC-Datalog

Theorem 3.1.

3.1 Linearity

Definition 3.2.

Example 3.3.

Theorem 3.4.

Theorem 3.5.

3.2 Determinism

Example 3.6.

Definition 3.7.

Example 3.8.

Definition 3.9.

Definition 3.10.

Theorem 3.11.

Proposition 3.12.

Proposition 3.13.

3.3 One Letter Lookahead

Definition 3.14.

Definition 3.15.

Example 3.16.

Theorem 3.17.

Definition 3.18.

Lemma 3.19.

Proposition 3.20.

Theorem 3.21.

3.4 Strictly Decreasing

Definition 3.22.

Theorem 3.23.

3.5 FC-Datalog as Generalized Automata

4 Applying the Framework: Simulating DRX

Example 4.1.

Example 4.2.

Theorem 4.3.

Definition 4.4.

Example 4.5.

Definition 4.6.

Example 4.7.

Theorem 4.8.

Proposition 4.9.

Theorem 4.10.

Example 4.11.

Example 4.12.

Example 4.13.

▶ Remark 4.14.

Example 4.15.

5 Conclusions and Future Work

References

$\blacktriangleright$ Remark 4.14.