This article fits in the area of research that investigates the application of topological duality methods to problems that appear in theoretical computer science. One of the eventual goals of this approach is to derive results in computational complexity theory by studying appropriate topological objects which characterize them. The link which relates these two seemingly separated fields is logic, more precisely a subdomain of finite model theory known as logic on words. It allows for a description of complexity classes as certain families of languages, possibly non-regular, on a finite alphabet. Very few is known about the duality theory relative to fragments of first-order logic on words which lie outside of the scope of regular languages. The contribution of our work is a detailed study of such a fragment. Fixing an integer $k \geq 1$, we consider the Boolean algebra $\mathcal{B}\Sigma_1[\mathcal{N}^{u}_k]$. It corresponds to the fragment of logic on words consisting in Boolean combinations of sentences defined by using a block of at most $k$ existential quantifiers, letter predicates and uniform numerical predicates of arity $l \in \{1,...,k\}$. We give a detailed study of the dual space of this Boolean algebra, for any $k \geq 1$, and provide several characterizations of its points. In the particular case where $k=1$, we are able to construct a family of ultrafilter equations which characterize the Boolean algebra $\mathcal{B} \Sigma_1[\mathcal{N}^{u}_1]$. We use topological methods in order to prove that these equations are sound and complete with respect to the Boolean algebra we mentioned.


翻译:此文章适用于研究领域, 研究对理论计算机科学中出现的问题应用上层双重性方法 。 此方法的最终目的之一是通过研究适当的表层对象来得出计算复杂性理论的结果。 与这两个表面上似乎分离的字段相关的链接是逻辑, 更准确地说, 是一个称为文字逻辑的有限模型理论的子域。 它允许描述复杂等级, 可能是非常规的, 使用一个限定的字母。 很少有人知道与位于常规语言范围之外的单词上的一阶逻辑碎片[一阶逻辑的碎片] 的双重性理论。 我们的工作贡献是对这种碎片进行详细研究。 固定整数 $k\ geq 1, 我们考虑Bole argebra $\ $\ 的亚值值值值值值值 。 在布尔里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里加里。

0
下载
关闭预览

相关内容

CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点,具有清晰的数学轮廓和严格的数学格式。官网链接:https://link.springer.com/journal/37
专知会员服务
52+阅读 · 2020年9月7日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
【ICIG2021】Latest News & Announcements of the Plenary Talk2
中国图象图形学学会CSIG
0+阅读 · 2021年11月2日
【ICIG2021】Latest News & Announcements of the Plenary Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年11月1日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年4月20日
Arxiv
0+阅读 · 2022年4月18日
Risk and optimal policies in bandit experiments
Arxiv
0+阅读 · 2022年4月18日
Arxiv
0+阅读 · 2022年4月17日
Arxiv
64+阅读 · 2021年6月18日
VIP会员
相关资讯
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
【ICIG2021】Latest News & Announcements of the Plenary Talk2
中国图象图形学学会CSIG
0+阅读 · 2021年11月2日
【ICIG2021】Latest News & Announcements of the Plenary Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年11月1日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员