paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Polishness of some topologies related to word or tree automata

与词或树自动机相关的一些拓扑的 Polish 性
LMCS vol.Volume 15, Issue 22019匹配度 1/10 · 该论文研究自动机相关拓扑的 Polish 性质,属于逻辑与自动机理论,与用户关注的 PL/AI、静态分析、Agentic 程序、浮点程序分析、贝叶斯程序分析及 LLM 交叉方向均无直接关联。引用 0 inbox
Olivier Finkel, Olivier Carton, Dominique Lecomte
crossref: 2026-09-10

AI 速览

一句话:证明 Büchi 拓扑与 automatic 拓扑是 Polish 的,并证明在无限标记二叉树空间上 Büchi 与 Muller 拓扑不是 Polish 的。

本文研究由词自动机与树自动机自然诱导的若干拓扑空间,关注其是否为 Polish 空间。作者证明在词的情形下,Büchi 拓扑与 automatic 拓扑都是 Polish 的;这一正面结果不能完全推广到无限标记二叉树空间:在该空间中 Büchi 拓扑与 Muller 拓扑均不是 Polish 的。论文是 CSL 2017 会议论文的扩展版,主要新增对树空间上 Büchi 拓扑与 Muller 拓扑的研究(第 4 节)。关键贡献在于精确刻画了自动机相关拓扑的可度量化/完备性边界,揭示了词与树情形之间的本质差异。

问题
判断词/树自动机所诱导的 Büchi、automatic、Muller 等拓扑空间是否具有 Polish 性(即是否可度量化、可分且完备)。
方法
使用描述集合论与拓扑方法,分别分析词自动机空间和无限标记二叉树空间上的拓扑性质,并给出相应的数学证明。
评估
通过数学证明(定理)确认词上的 Büchi/automatic 拓扑为 Polish,并证明树上的 Büchi/Muller 拓扑非 Polish;扩展版补充了树情形的完整分析。
原文摘要(Abstract)

We prove that the B\"uchi topology and the automatic topology are Polish. We also show that this cannot be fully extended to the case of a space of infinite labelled binary trees; in particular the B\"uchi and the Muller topologies are not Polish in this case.Comment: This paper is an extended version of a paper which appeared in the proceedings of the 26th EACSL Annual Conference on Computer Science and Logic, CSL 2017. The main addition with regard to the conference paper consists in the study of the B\"uchi topology and of the Muller topology in the case of a space of trees, which now forms Section 4

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot797,
  title = {Polishness of some topologies related to word or tree automata},
  author = {Olivier Finkel and Olivier Carton and Dominique Lecomte},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 2},
  year = {2019},
  doi = {10.23638/lmcs-15(2:9)2019}
}