Level Two of the Quantifier Alternation Hierarchy Over Infinite Words
Level Two of the Quantifier Alternation Hierarchy Over Infinite Words
复制标题
无限单词上的量词交替层次结构的第二级
DOI：
10.1007/s00224-017-9801-x
复制
发表时间：
2018
影响因子：
0.5
通讯作者：
T. Walter
中科院分区：
文献类型：
--
作者：
M. Kufleitner;T. Walter
逻辑片段的各种决策问题的研究在计算机科学中有着悠久的历史。本文研究无限词上的一阶逻辑片段的隶属问题，该隶属问题要求给定的语言是否在某个固定片段中可定义。字母拓扑结构被引入作为对无限词上的片段E22的有效表征的一部分。在这里，R22由一阶公式和两个量词块组成，从一个存在量词开始。它的布尔闭包是。我们的第一个主要结果是对字母拓扑的布尔闭包的一个有效刻画，即给定一个ω-正则语言L，L是否是字母拓扑中开集的布尔组合是可判定的。然后，这是用于转移的地方和Zeitoun最近的可判定性结果从有限到无限的话。
The study of various decision problems for logic fragments has a long history in computer science. This paper is on the membership problem for a fragment of first-order logic over infinite words; the membership problem asks for a given language whether it is definable in some fixed fragment. The alphabetic topology was introduced as part of an effective characterization of the fragment Σ2over infinite words. Here, Σ2consists of the first-order formulas with two blocks of quantifiers, starting with an existential quantifier. Its Boolean closure is. Our first main result is an effective characterization of the Boolean closure of the alphabetic topology, that is, given anω-regular languageL, it is decidable whetherLis a Boolean combination of open sets in the alphabetic topology. This is then used for transferring Place and Zeitoun’s recent decidability result forfrom finite to infinite words.
登录
查看更多内容
DOI：
10.1007/978-3-662-49630-5_14
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
Théo Pierron;Thomas Place;M. Zeitoun
通讯作者：
M. Zeitoun
用符号逻辑对常规事件进行分类
DOI：
--
发表时间：
1982
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
W. Thomas
通讯作者：
W. Thomas
拓扑自动理论和自由特性拓扑分类调节器福尔根门根
DOI：
--
发表时间：
1974
期刊：
Journal of Information Processing and Cybernetics
影响因子：
--
作者：
Ludwig Staiger;K. W. Wagner
通讯作者：
K. W. Wagner
具有模块化谓词的一阶逻辑中的一个量词交替
DOI：
--
发表时间：
2013
期刊：
RAIRO - Theoretical Informatics and Applications
影响因子：
--
作者：
Manfred Kufleitner;Tobias Walter
通讯作者：
Tobias Walter
句法半群
DOI：
10.1007/978-3-642-59136-5_10
发表时间：
1997
期刊：
2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)
影响因子：
--
作者：
J. Pin
通讯作者：
J. Pin