Counting Branches in Trees Using GamesReportar como inadecuado

Counting Branches in Trees Using Games - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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

Autor: Arnaud Carayol - Olivier Serre -



Documentos relacionados