Abstract
In this paper, we study the complexity of deciding which player has a winning strategy in certain types of McNaughton games. These graph games can be used as models for computational problems and processes of infinite duration. We consider the cases (1) where the first player wins when vertices in a specified set are visited infinitely often and vertices in another specified set are visited finitely often, (2) where the first player wins when exactly those vertices in one of a number of specified disjoint sets are visited infinitely often, and (3) a generalization of these first two cases. We give polynomial time algorithms to determine which player has a winning strategy in each of the games considered.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer. Alternation. Journal of the ACM, 28(1):114–133, January 1981.
M. J. Dinneen and B. Khoussainov. Update networks and their routing strategies. In Proceedings of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science, WG2000, volume 1928 of Lecture Notes on Computer Science, pages 127–136. Springer-Verlag, June 2000.
Y. Gurevich and L. Harrington. Trees, Automata, and Games, STOCS, 1982, pages 60–65.
J. F. Knight and B. Luense. Control Theory, Modal Logic, and Games, In Hybrid Systems IV. Panos J. Antsaklis, Wolf Kohn, Anil Nerode, Shankar Sastry (Eds.), volume 1273 of Lecture Notes in Computer Science, pages 160–173. Springer, 1997.
R. McNaughton. Infinite games played on finite graphs. Annals of Pure and Applied Logic, 65:149–184, 1993.
A. Nerode, J. Remmel, and A. Yakhnis. McNaughton games and extracting strategies for concurrent programs. Annals of Pure and Applied Logic, 78:203–242, 1996.
A. Nerode, A. Yakhnis, V. Yakhnis. Distributed concurrent programs as strategies in games. Logical methods(Ithaca, NY, 1992), pages 624–653, Progr. Comput. Sci. Appl. Logic, 12, Birkhauser Boston, Boston, MA, 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bodlaender, H.L., Dinneen, M.J., Khoussainov, B. (2001). On Game-Theoretic Models of Networks. In: Eades, P., Takaoka, T. (eds) Algorithms and Computation. ISAAC 2001. Lecture Notes in Computer Science, vol 2223. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45678-3_47
Download citation
DOI: https://doi.org/10.1007/3-540-45678-3_47
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42985-2
Online ISBN: 978-3-540-45678-0
eBook Packages: Springer Book Archive