Showing cs.LOShow all
3 papers · 1 filter
cs.LO2025
Characterization and Decidability of FC-Definable Regular Languages
Sam M. Thompson, Nicole Schweikardt, Dominik D. Freydenberger
FC is a first-order logic that reasons over all factors of a finite word using concatenation, and can define non-regular languages like that of all squares (ww). In this paper, we…
cs.LO2023
Generalized Core Spanner Inexpressibility via Ehrenfeucht-Fraïssé Games for FC
Sam M. Thompson, Dominik D. Freydenberger
Despite considerable research on document spanners, little is known about the expressive power of generalized core spanners. In this paper, we use Ehrenfeucht-Fraïssé games to obta…
cs.LO2019
Dynamic Complexity of Document Spanners
Dominik D. Freydenberger, Sam M. Thompson
The present paper investigates the dynamic complexity of document spanners, a formal framework for information extraction introduced by Fagin, Kimelfeld, Reiss, and Vansummeren (JA…