Counting Branches in Trees Using GamesReport as inadecuate

Counting Branches in Trees Using Games - Download this document for free, or read online. Document in PDF available to download.

1 LIGM - Laboratoire d-Informatique Gaspard-Monge 2 IRIF - Institut de Recherche en Informatique Fondamentale

Abstract : 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 esp countably many rejecting branches;ii it contains infinitely esp 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 omega-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 Niwinski.

Keywords : Automata on Infinite Trees Two-Player Games Cardinality Constraints Topologically Large Sets

Author: Arnaud Carayol - Olivier Serre -



Related documents