Gurevich-Harrington's games defined by finite automata

DOI10.1016/0168-0072(93)90239-AMaRDI QIDQ685082zbMATH OpenFDO

Authors Alexander Yakhnis, Vladimir Yakhnis

Publication date 22 September 1993

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

Full work available at URL https://doi.org/10.1016/0168-0072(93)90239-A

zbMATH Keywords

alphabet of possible movesconcurrent programfinite automaton model

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Learning and adaptive systems in artificial intelligence (68T05) 2-person games (91A05)

Review text

The paper considers 2-player games in extended form described by an alphabet of possible moves and the subset of the winning plays of the players (where a play is a sequence -- finite or infinite -- of moves chosen alternately by the players). The finite automaton model used for the analysis of such games allows to study their properties and effectively find the winning player. The components of the game are transformed in a transition table of the automaton representing the game, and processing that transmission table leads to the derivation of general conditions determining the winner.

Recommendations

• Infinite games played on finite graphs
• Finite automata play a repeated extensive game
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• scientific article; zbMATH DE number 4045161
• scientific article; zbMATH DE number 5954365

Cites work

• A starvation-free solution to the mutual exclusion problem
• An Approach to a Unified Theory of Automata
• Elementary induction on abstract structures
• Extension of Gurevich-Harrington's restricted memory determinacy theorem: A criterion for the winning player and an explicit class of winning strategies
• scientific article; zbMATH DE number 3848584 (Why is no real title available?)
• scientific article; zbMATH DE number 65755 (Why is no real title available?)
• scientific article; zbMATH DE number 3572126 (Why is no real title available?)
• scientific article; zbMATH DE number 4126676 (Why is no real title available?)
• scientific article; zbMATH DE number 3993574 (Why is no real title available?)
• scientific article; zbMATH DE number 3215740 (Why is no real title available?)
• scientific article; zbMATH DE number 3078993 (Why is no real title available?)
• On some games which are relevant to the theory of recursively enumerable sets
• Solving Sequential Conditions by Finite-State Strategies
• State-strategies for games in F_σδ ∩ G_δσ
• The strict determinateness of certain infinite games
• Unforgettable Forgetful Determinacy

Cited in

(14)

• Behavior of finite and infinite automata in game situations
• On the inference of strategies
• Infinite games played on finite graphs
• Finite automata capturing winning sequences for all possible variants of the \(PQ\) penny flip game
• McNaughton games and extracting strategies for concurrent programs
• The ground tree transducer game with identical tree automata
• Finitely repeated games with finite automata
• scientific article; zbMATH DE number 4035147 (Why is no real title available?)
• scientific article; zbMATH DE number 1192316 (Why is no real title available?)
• Variations on a game of Gale (I): Coding strategies
• Games with Unknown Past
• scientific article; zbMATH DE number 1944403 (Why is no real title available?)
• Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
• Extension of Gurevich-Harrington's restricted memory determinacy theorem: A criterion for the winning player and an explicit class of winning strategies

This page was built for publication: Gurevich-Harrington's games defined by finite automata

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