Fast Datalog on Text

Datalog is a recursive query language for relational databases. FC-Datalog is a recursive query language for text, based on word equations and finite model theory. This talk is based on fragments of FC-Datalog with fast evaluation. We first show the connection FC-Datalog has to the logic programming language Hereditary Elementary Formal Systems (HEFS) by showing that they have equivalent expressive power and that there are efficient transformations between the two models. Taking inspiration from the literature on HEFS, we define Linear FC-Datalog, and show this captures the complexity class NLOGSPACE. We then use the special features of FC, namely its word equations, to go one step further where we define the fragment One Letter Lookahead Linear FC-Datalog, and show this captures the complexity class LOGSPACE.