Counting branches in trees using games

DOI10.1016/J.IC.2016.11.005MaRDI QIDQ729823zbMATH OpenOpenAlexFDO

Authors Arnaud Carayol, Olivier Serre

Publication date 22 December 2016

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.03852

zbMATH Keywords

two-player gamecardinality constraintautomaton on infinite treestopologically large set

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Games involving graphs (91A43)

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: - it contains at most finitely (resp countably) many rejecting branches; - it contains infinitely (resp uncountably) many accepting branches; - 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 an old result of Beauquier and Niwinski.

Recommendations

• Automata on infinite trees with counting constraints
• Automata on infinite trees with counting constraints
• Randomization in automata on infinite trees
• THE EFFECT OF THE NUMBER OF SUCCESSFUL PATHS IN A BÜCHI TREE AUTOMATON
• Topological characterizations of infinite tree languages

Cites work

• scientific article; zbMATH DE number 5872401 (Why is no real title available?)
• scientific article; zbMATH DE number 5954365 (Why is no real title available?)
• scientific article; zbMATH DE number 3492660 (Why is no real title available?)
• scientific article; zbMATH DE number 3572126 (Why is no real title available?)
• scientific article; zbMATH DE number 1346522 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• scientific article; zbMATH DE number 3189696 (Why is no real title available?)
• Automata on infinite trees with counting constraints
• Baire category quantifier in monadic second order logic
• Banach-Mazur games on graphs
• Borel determinacy
• CONCUR 2005 – Concurrency Theory
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Defining fairness in reactive and concurrent systems
• Emptiness Of Alternating Tree Automata Using Games With Imperfect Information
• Expressing cardinality quantifiers in monadic second-order logic over trees
• Fair adversaries and randomization in two-player games
• How good is a strategy in a game with Nature?
• Randomization in automata on infinite trees

Cited in

(8)

• scientific article; zbMATH DE number 7362735 (Why is no real title available?)
• Automata on infinite trees with counting constraints
• The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
• Monadic Second Order Logic with Measure and Category Quantifiers
• Automata on infinite trees with counting constraints
• Randomization in automata on infinite trees
• Trees and Ehrenfeucht-Fraïssé games
• scientific article; zbMATH DE number 176157 (Why is no real title available?)

This page was built for publication: Counting branches in trees using games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q729823)