Loughborough University
Browse

Generalized core spanner inexpressibility via Ehrenfeucht-Fraïssé games for FC

Download (638.02 kB)
conference contribution
posted on 2024-05-15, 16:02 authored by Sam ThompsonSam Thompson, Dominik FreydenbergerDominik Freydenberger

Despite considerable research on document spanners, little is known about the expressive power of generalized core spanners. In this paper, we use Ehrenfeucht-Fraïssé games to obtain general inexpressibility lemmas for the logic FC (a finite model variant of the theory of concatenation). Applying these lemmas give inexpressibility results for FC that we lift to generalized core spanners. In particular, we give several relations that cannot be selected by generalized core spanners, thus demonstrating the effectiveness of the inexpressibility lemmas. As an immediate consequence, we also gain new insights into the expressive power of core spanners.

Funding

Foundations of the Finite Model Theory of Concatenation

Engineering and Physical Sciences Research Council

Find out more...

History

School

  • Science

Department

  • Computer Science

Published in

Proceedings of the ACM on Management of Data

Volume

2

Issue

2

Source

Symposium on Principles of Database Systems 2024

Publisher

ACM

Version

  • VoR (Version of Record)

Rights holder

© Copyright held by the owner/author(s).

Publisher statement

This work is licensed under a Creative Commons Attribution International 4.0 License - https://creativecommons.org/licenses/by/4.0/.

Acceptance date

2024-03-27

Publication date

2024-05-14

Copyright date

2024

eISSN

2836-6573

Language

  • en

Editor(s)

Divyakant Agrawal

Location

Santiago, Chile

Event dates

9th June 2024 - 14th June 2024

Depositor

Sam Thompson. Deposit date: 1 May 2024

Article number

80

Usage metrics

    Loughborough Publications

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC