Thomas Place ; Varun Ramanathan ; Pascal Weil - Covering and separation for logical fragments with modular predicates

lmcs:4501 - Logical Methods in Computer Science, May 8, 2019, Volume 15, Issue 2 - https://doi.org/10.23638/LMCS-15(2:11)2019
Covering and separation for logical fragments with modular predicatesArticle

Authors: Thomas Place ; Varun Ramanathan ; Pascal Weil

    For every class $\mathscr{C}$ of word languages, one may associate a decision problem called $\mathscr{C}$-separation. Given two regular languages, it asks whether there exists a third language in $\mathscr{C}$ containing the first language, while being disjoint from the second one. Usually, finding an algorithm deciding $\mathscr{C}$-separation yields a deep insight on $\mathscr{C}$. We consider classes defined by fragments of first-order logic. Given such a fragment, one may often build a larger class by adding more predicates to its signature. In the paper, we investigate the operation of enriching signatures with modular predicates. Our main theorem is a generic transfer result for this construction. Informally, we show that when a logical fragment is equipped with a signature containing the successor predicate, separation for the stronger logic enriched with modular predicates reduces to separation for the original logic. This result actually applies to a more general decision problem, called the covering problem.


    Volume: Volume 15, Issue 2
    Published on: May 8, 2019
    Accepted on: May 7, 2019
    Submitted on: May 15, 2018
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory
    Funding:
      Source : OpenAIRE Graph
    • Challenges for Logic, Transducers and Automata; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0007

    Consultation statistics

    This page has been seen 1627 times.
    This article's PDF has been downloaded 294 times.