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 metadatas

https://hal.inria.fr/hal-03104159
Contributor : Liat Peterfreund <>
Submitted on : Friday, January 8, 2021 - 4:34:08 PM
Last modification on : Wednesday, January 13, 2021 - 3:35:13 AM

File

1912.06110.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03104159, version 1

Collections

Citation

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

Share

Metrics

Record views

14

Files downloads

45