The theory of concatenation over finite models - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

The theory of concatenation over finite models

Résumé

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.
Fichier principal
Vignette du fichier
1912.06110.pdf (972.82 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03104159 , version 1 (08-01-2021)

Identifiants

  • HAL Id : hal-03104159 , version 1

Citer

Dominik D Freydenberger, Liat Peterfreund. The theory of concatenation over finite models. 2021. ⟨hal-03104159⟩
37 Consultations
138 Téléchargements

Partager

Gmail Facebook X LinkedIn More