Extension of Gurevich-Harrington's restricted memory determinacy theorem: A criterion for the winning player and an explicit class of winning strategies

DOI10.1016/0168-0072(90)90024-VzbMath0716.03036MaRDI QIDQ752703

Vladimir Yakhnis, Alexander Yakhnis

Publication date: 1990

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

treeautomataprogram specificationconcurrent programsdeterministic strategyDeterminacy with Restraints ProblemGurevich- Harrington's Restricted Memory Determinacy Theoreminfinite games with perfect informationmodularity of a winning strategynondeterministic strategypriority automatastrategies with restricted memory

Mathematics Subject Classification ID

2-person games (91A05) Applications of game theory (91A80) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60) Decidability of theories and sets of sentences (03B25) Determinacy principles (03E60)

Related Items (7)

Progress measures, immediate determinacy, and a subset construction for tree automata ⋮ McNaughton games and extracting strategies for concurrent programs ⋮ Game characterizations of logic program properties ⋮ Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra ⋮ Gurevich-Harrington's games defined by finite automata ⋮ Infinite games on finitely coloured graphs with applications to automata on infinite trees ⋮ Infinite games played on finite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Gurevich-Harrington's games defined by finite automata
• Elementary induction on abstract structures
• A starvation-free solution to the mutual exclusion problem
• On some games which are relevant to the theory of recursively enumerable sets
• State-strategies for games in F_σδ ∩ G_δσ
• Solving Sequential Conditions by Finite-State Strategies

This page was built for publication: Extension of Gurevich-Harrington's restricted memory determinacy theorem: A criterion for the winning player and an explicit class of winning strategies