2026-07-26T01:27:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14199 2024-03-06T10:53:44Z ddc:004 open_access

The Theory of Concatenation over Finite Models Freydenberger, Dominik D. Peterfreund, Liat finite model theory word equations descriptive complexity model checking document spanners We propose FC, a new logic on words that combines finite model theory with the theory of concatenation - a first-order logic that is based on word equations. 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 factors. As a consequence of this, FC has many of the desirable properties of FO on finite models, while being far more expressive than FO[<]. Most noteworthy among these desirable properties are sufficient criteria for efficient model checking, and capturing various complexity classes by adding operators for transitive closures or fixed points. Not only does FC allow us to obtain new insights and techniques for expressive power and efficient evaluation of document spanners, but it also provides a general framework for logic on words that also has potential applications in other areas. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dominik D. Freydenberger and Liat Peterfreund 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.130 urn:nbn:de:0030-drops-141997 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.130 eng https://creativecommons.org/licenses/by/4.0/legalcode