LIPIcs-ICALP-2021-130.pdf (810.42 kB)

The theory of concatenation over finite models

Download (810.42 kB)
conference contribution
posted on 05.07.2021, 14:58 by Dominik FreydenbergerDominik Freydenberger, Liat Peterfreund
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.

Funding

Foundations of the Finite Model Theory of Concatenation

Engineering and Physical Sciences Research Council

Find out more...

Fondation des Sciences Mathématiques de Paris (FSMP)

History

School

  • Science

Department

  • Computer Science

Published in

Leibniz International Proceedings in Informatics

Volume

198

Pages

130:1–130:17

Source

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Publisher

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Version

VoR (Version of Record)

Rights holder

© The Authors

Publisher statement

This is an Open Access Article. It is published by Schloss Dagstuhl - Leibniz-Zentrum für Informatik under the Creative Commons Attribution 4.0 International Licence (CC BY 4.0). Full details of this licence are available at: https://creativecommons.org/licenses/by/4.0/

Acceptance date

08/05/2021

Publication date

2021-07-02

Copyright date

2021

ISSN

1868-8969

Language

en

Editor(s)

Nikhil Bansal; Emanuela Merelli; James Worrell

Location

Glasgow, Scotland (Virtual Conference)

Event dates

12th July 2021 - 16th July 2021

Depositor

Dr Dominik Freydenberger. Deposit date: 10 May 2021

Article number

130

Usage metrics

Read the paper on the publisher website

Categories

Licence

Exports