Thomas Place ; Marc Zeitoun - The Covering Problem

lmcs:3906 - Logical Methods in Computer Science, July 20, 2018, Volume 14, Issue 3 - https://doi.org/10.23638/LMCS-14(3:1)2018
The Covering ProblemArticle

Authors: Thomas Place ; Marc Zeitoun

    An important endeavor in computer science is to understand the expressive power of logical formalisms over discrete structures, such as words. Naturally, "understanding" is not a mathematical notion. This investigation requires therefore a concrete objective to capture this understanding. In the literature, the standard choice for this objective is the membership problem, whose aim is to find a procedure deciding whether an input regular language can be defined in the logic under investigation. This approach was cemented as the right one by the seminal work of Schützenberger, McNaughton and Papert on first-order logic and has been in use since then. However, membership questions are hard: for several important fragments, researchers have failed in this endeavor despite decades of investigation. In view of recent results on one of the most famous open questions, namely the quantifier alternation hierarchy of first-order logic, an explanation may be that membership is too restrictive as a setting. These new results were indeed obtained by considering more general problems than membership, taking advantage of the increased flexibility of the enriched mathematical setting. This opens a promising research avenue and efforts have been devoted at identifying and solving such problems for natural fragments. Until now however, these problems have been ad hoc, most fragments relying on a specific one. A unique new problem replacing membership as the right one is still missing. The main contribution of this paper is a suitable candidate to play this role: the Covering Problem. We motivate this problem with 3 arguments. First, it admits an elementary set theoretic formulation, similar to membership. Second, we are able to reexplain or generalize all known results with this problem. Third, we develop a mathematical framework and a methodology tailored to the investigation of this problem.


    Volume: Volume 14, Issue 3
    Published on: July 20, 2018
    Accepted on: July 13, 2018
    Submitted on: September 6, 2017
    Keywords: Computer Science - Logic in Computer Science
    Funding:
      Source : OpenAIRE Graph
    • Challenges for Logic, Transducers and Automata; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0007

    1 Document citing this article

    Consultation statistics

    This page has been seen 1185 times.
    This article's PDF has been downloaded 396 times.