Generalized Core Spanner Inexpressibility via Ehrenfeucht-Fraisse Games for FC

Document Spanners are a way to query text documents analogously to how one queries a relational database. Despite considerable research on document spanners, little is known about the expressive power of a particular class known as generalized core spanners.

For first-order logic, one of the fundamental tools for inexpressibility are Ehrenfeucht-Fraïssé Games. To use Ehrenfeucht-Fraïssé games in order to yield inexpressibility results for generalized core spanners, we need a suitable logic. For this task, we use FC; a finite-model variant of the theory of concatenation.

We use Ehrenfeucht-Fraïssé games to obtain general inexpressibility lemmas for the logic FC. Applying these lemmas give inexpressibility results for FC that we lift to generalized core spanners. In particular, we give several queries that cannot be selected by generalized core spanners.