一句话:提出“覆盖问题”作为替代成员问题的统一框架,用于刻画正则语言的逻辑可定义性。
本文研究离散结构(如有限字)上逻辑形式系统的表达力。传统上以成员问题为核心:判定给定正则语言能否由某逻辑定义。然而成员问题对许多重要片段极其困难,数十年未决,尤其在一阶逻辑量词交替层级等著名问题上进展有限。作者认为成员问题作为设定过于受限,近期突破正是来自更一般的问题。本文提出“覆盖问题”(Covering Problem)作为替代成员问题的统一候选:它保持类似成员问题的初等集合论表述,同时具备更强灵活性;作者用该问题重新解释或推广所有已知结果,并发展了一套专门的数学框架与方法论来研究它。由此为逻辑可定义性与量词交替层级的后续研究提供新范式。
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\"utzenberger, 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.