Counting branches in trees using games

DOI10.1016/J.IC.2016.11.005zbMATH Open1357.68101arXiv1505.03852OpenAlexW2198382712MaRDI QIDQ729823FDOQ729823

Arnaud Carayol, Olivier Serre

Publication date: 22 December 2016

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Borel determinacy
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Banach-Mazur Games on Graphs
• CONCUR 2005 – Concurrency Theory
• Automata on infinite trees with counting constraints
• Randomization in Automata on Infinite Trees
• Emptiness Of Alternating Tree Automata Using Games With Imperfect Information
• Expressing Cardinality Quantifiers in Monadic Second-Order Logic over Trees
• Baire Category Quantifier in Monadic Second Order Logic
• Fair Adversaries and Randomization in Two-Player Games
• How Good Is a Strategy in a Game with Nature?
• Defining Fairness in Reactive and Concurrent Systems

Cited In (4)

• Title not available (Why is that?)
• Monadic Second Order Logic with Measure and Category Quantifiers
• The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
• Trees and Ehrenfeucht-Fraïssé games

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)