Efficient Algorithms for Games Played on Trees with Back-edges

• Autorzy: Gandhi A. , Khoussainov B. , Liu J.
• Języki publikacji: EN

Abstrakty

EN

This paper studies algorithms for deciding the winners of two-player games played on directed graphs. We focus on the case when the underlying graphs are trees with back-edges and provide both theoretical and experimental analysis of this class of games. In particular, we present an algorithm that solves Büchi games played on trees with back-edges in time O(min{r źm, l+m}) where m is the number of edges, l is the sum of the distances from the root to all leaves and the parameter r is bounded by the height of the tree. We also show that parity games played on trees with back-edges can be solved in time O(l + m).

Słowa kluczowe

EN

Büchi games; trees with back-edges; snares; parity games; experiment

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 111, nr 4
• Strony: 391--412
• Opis fizyczny: Bibliogr. 16 poz., tab., wykr.

Twórcy

autor

Gandhi A.

autor

Khoussainov B.

autor

Liu J.

• Department of Computer Science, University of Auckland, Auckland, New Zealand,

Bibliografia

• [1] Berwanger, D., Grädel, E.: Entanglement - a measure for the complexity of directed graphs with applications to logic and games. In: Proceedings of LPAR'04, pp. 209-223, 2004.
• [2] Berwanger, D., Grädel, E., Lenzi, G.: The variable hierarchy of the μ calculus is strict, In: Theory of Computing Systems 40, no. 4, 2007, 437-466.
• [3] Chatterjee, K., Henzinger, T., Jurdzinski, M.: Mean-Payoff Parity Games. In: Proc. of LICS'05, pp.178-187, 2005.
• [4] Chatterjee, K., Henzinger, T., Piterman, N.: Algorithms for B¨uchi games. In: Proc. of the 3rd Workshop of Games in Design and Verification (GDV'06), 2006.
• [5] Chatterjee, K., Jurdzi´nski, M., Henzinger, T.: Simple stochastic parity games. In: Proc. of CSL'03. LNCS 2803:100-113. Springer, 2003.
• [6] Clarke, E., Lu, Y., Veith, H., Jha, S.: Tree-Like counterexamples in model checking. In: Proc. of LICS'02, pp.19-29, IEEE Computer Society, 2002.
• [7] Grädel, E., Thomas,W.,Wilke, T. (Eds.): Automata, Logics, and InfiniteGames: A Guide to Current Research. LNCS 2500. Springer, 2002.
• [8] Immerman, N.: Number of quantifiers is better than number of tape cells. In: Journal of Computer and System Sciences, 22, 1981, 384-406.
• [9] Martin, D.: Borel determinacy, Ann. Math. 102, No. 2(Sep., 1975), pp. 363-371.
• [10] Murawski, A.: Reachability games and game semantics: Comparing nondeterministic programs. In: Proc. Of LICS'08, pp. 353-363. 2008.
• [11] Obdrˇzálek, J.: Algorithmic Analysis of Parity Games, PhD thesis, Univ. of Edinburgh, 2006.
• [12] Thomas, W.: Infinite games and verification. In: Proc. of the International Conference on Computer Aided Verification (CAV'02), LNCS 2404:58-64, 2002.
• [13] Cho, M., Kim, D., Seo S., and Shin, H.: Colored Pr¨ufer Codes for k−Edge Colored Trees, Electron. J. Combin. 11 no. 1, #N10, 2004.
• [14] Arnold, D.B., and Sleep, M.R.: Uniform random generation of balanced parenthesis strings, ACM Trans. Program. Lang. Syst. 2. 1980, 122-128.
• [15] Fischer, J., and Heun, V.: A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array, Lecture Notes in Computer Science, vol 4614, pp. 459-470, Springer-Verlag, 2007.
• [16] Sage open source mathematical software, http://www.sagemath.org/. Copyright of Fundamenta Informaticae is the property of IOS Press and its c