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