Infinite games played on finite graphs. (English) Zbl 0798.90151

The concept of an infinite game played on a finite graph is perhaps novel in the context of a rather extensive recent literature in which infinite games are generally played on an infinite game tree. We claim two advances for our model, which is admittedly more restrictive. First, our games have a more apparent resemblance to ordinary parlor games in spite of their infinite duration. Second, by distinguishing those nodes of the graph that determines the winning and losing of the game (winning- condition nodes), we are able to offer a complexity analysis that is useful in computer science applications.


91A43 Games involving graphs
68Q25 Analysis of algorithms and problem complexity
91A05 2-person games
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Full Text: DOI


[1] Büchi, J.R., On a decision method in restricted second-order arithmetic, (), 1-11, Reprinted in [9] · Zbl 0147.25103
[2] Büchi, J.R.; Landweber, L.H., Solving sequential conditions by finite-state strategies, Trans. am. math. soc., 138, 295-311, (1969), Reprinted in [9] · Zbl 0182.02302
[3] Davis, M., Infinite games of perfect information, (), 85-101 · Zbl 0133.13104
[4] Gale, D.; Stewart, F.M., Infinite games with perfect information, (), 245-266
[5] Gurevich, Y., Monadic second-order theories, ()
[6] Gurevich, Y.; Harrington, L., Trees, automata and games, (), 60-65
[7] Landweber, L.H., A design algorithm for sequential machines and definability in monadic second-order arithmetic, Phd dissertation, (1967), Purdue Univ
[8] Landweber, L.H., Finite-state games—a solvability algorithm for restricted second-order arithmetic, Notices am. math. soc., 14, 129-130, (1967)
[9] ()
[10] Nerode, A.; Yakhnis, A.; Yakhnis, V., Concurrent programs as strategies in games, Technical report ’90-78, (1990), Mathematical Sciences Inst., Cornell Univ · Zbl 0746.68046
[11] Thomas, W., Automata on infinite objects, (), 135-191 · Zbl 0900.68316
[12] Yakhnis, A.; Yakhnis, V., Extension of guverich-Harrington’s restricted memory determinacy theorem: a criterion for the winning player and an explicit class of winning strategi es, Ann. pure appl. logic, 48, 277-297, (1990) · Zbl 0716.03036
[13] Yakhnis, A.; Yakhnis, V., Gurevich-Harrington’s games defined by finite automata, Ann. pure appl. logic, 62, 265-294, (1993) · Zbl 0778.03010
[14] S. Zeitman, Unforgettable forgetful determinacy, Logic and Computation, to appear. · Zbl 0860.03012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.