Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

The theory of concatenation over finite models

Abstract : We propose FC, a logic on words that combines the previous approaches of finite-model theory and the theory of concatenation. It has immediate applications to spanners, a formalism for extracting structured data from text that has recently received considerable attention in database theory. In fact, FC is designed to be to spanners what FO is to relational databases. Like the theory of concatenation, FC is built around word equations; in contrast to it, its semantics are defined to only allow finite models, by limiting the universe to a word and all its subwords. As a consequence of this, FC has many of the desirable properties of FO[<], while being far more expressive. Most noteworthy among these desirable properties are sufficient criteria for efficient model checking and capturing various complexity classes by extending the logic with appropriate closure or iteration operators. These results allow us to obtain new insights into and techniques for the expressive power and efficient evaluation of spanners. More importantly, FC provides us with a general framework for logic on words that has potential applications far beyond spanners.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Liat Peterfreund Connect in order to contact the contributor
Submitted on : Friday, January 8, 2021 - 4:34:08 PM
Last modification on : Tuesday, January 11, 2022 - 11:16:06 AM
Long-term archiving on: : Friday, April 9, 2021 - 7:24:41 PM


Files produced by the author(s)


  • HAL Id : hal-03104159, version 1



Dominik Freydenberger, Liat Peterfreund. The theory of concatenation over finite models. 2021. ⟨hal-03104159⟩



Les métriques sont temporairement indisponibles