Counting branches in trees using games

详细信息    查看全文

• 作者：Arnaud Carayol^a ; ¹ ; ^{Arnaud.Carayol@univ-mlv.fr} ; Olivier Serre^b ; ² ; ^{Olivier.Serre@cnrs.fr}
• 关键词：Automaton on infinite trees ; Two-player game ; Cardinality constraint ; Topologically large set
• 刊名：Information and Computation
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：252
• 期：Complete
• 页码：221-242
• 全文大小：850 K
• 卷排序：252

文摘

We study finite automata running over infinite binary trees. A run of such an automaton is usually said to be accepting if all its branches are accepting. In this article, we relax the notion of accepting run by allowing a certain quantity of rejecting branches. More precisely we study the following criteria for a run to be accepting:(i)it contains at most finitely (resp. countably) many rejecting branches;(ii)it contains infinitely (resp. uncountably) many accepting branches;(iii)the set of accepting branches is topologically “big”. In all situations we provide a simple acceptance game that later permits to prove that the languages accepted by automata with cardinality constraints are always ω-regular. In the case (ii) where one counts accepting branches it leads to new proofs (without appealing to logic) of a result of Beauquier and Niwiński.