Loughborough University
Browse

Languages generated by conjunctive query fragments of FC[REG]

Download (354.13 kB)
conference contribution
posted on 2023-06-08, 14:23 authored by Sam ThompsonSam Thompson, Dominik FreydenbergerDominik Freydenberger

FC is a finite-model variant on the theory of concatenation, FC[REG] extends FC with regular constraints. This paper considers the languages generated by their conjunctive query fragments, FC-CQ and FC[REG]-CQ. We compare the expressive power of FC[REG]-CQ to that of various related language generators, such as regular expressions, patterns, and typed patterns.We then consider decision problems for FC-CQ and FC[REG]-CQ, and show that certain static analysis problems (such as equivalence and regularity) are undecidable. While this paper defines FC-CQ based on the logic FC, they can equally be understood as synchronized intersections of pattern languages, or as systems of restricted word equations.

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

Developments in Language Theory: DLT 2023

Volume

13911

Pages

233 - 245

Source

Developments in Language Theory 2023

Publisher

Springer

Version

  • AM (Accepted Manuscript)

Rights holder

© The Author(s), under exclusive license to Springer Nature Switzerland AG

Publisher statement

This version of the contribution has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/978-3-031-33264-7_19. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms

Publication date

2023-05-19

Copyright date

2023

ISBN

9783031332630; 9783031332647

Book series

Lecture Notes in Computer Science

Language

  • en

Editor(s)

Frank Drewes; Mikhail Volkov

Location

Umeå, Sweden

Event dates

12th June 2023 - 16th June 2023

Depositor

Sam Thompson. Deposit date: 7 June 2023

Usage metrics

    Loughborough Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC