Abstract
Parity word automata and their determinisation play an important role in automata and game theory. We discuss a determinisation procedure for nondeterministic parity automata through deterministic Rabin to deterministic parity automata. We prove that the intermediate determinisation to Rabin automata is optimal. We show that the resulting determinisation to parity automata is optimal up to a small constant. Moreover, the lower bound refers to the more liberal Streett acceptance. We thus show that determinisation to Streett would not lead to better bounds than determinisation to parity. As a side-result, this optimality extends to the determinisation of Büchi automata.
A full version with proofs is available at http://arxiv.org/abs/1401.5394.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Boker, U., Kupferman, O.: Co-ing Büchi made tight and useful. In: Proc. of LICS, pp. 245–254 (2009)
Cai, Y., Zhang, T.: Tight upper bounds for Streett and parity complementation. In: Proc. of CSL, pp. 112–128 (2011)
Colcombet, T., Zdanowski, K.: A tight lower bound for determinization of Büchi automata. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol. 5556, pp. 151–162. Springer, Heidelberg (2009)
Duret-Lutz, A.: LTL translation improvements in SPOT. In: VECoS, pp. 72–83. BCS (2011)
Finkbeiner, B., Schewe, S.: Uniform distributed synthesis. In: Proc. of LICS 2005, pp. 321–330 (2005)
Finkbeiner, B., Schewe, S.: Bounded synthesis. International Journal on Software Tools for Technology Transfer, online-first: 1–12 (2012)
Kupferman, O., Vardi, M.Y.: Synthesizing distributed systems. In: Proc. of LICS 2001, pp. 389–398 (2001)
Kupferman, O., Vardi, M.Y.: Safraless decision procedures. In: Proc. of FOCS 2005, pp. 531–540 (2005)
Piterman, N.: From nondeterministic Büchi and Streett automata to deterministic parity automata. Journal of LMCS 3(3:5) (2007)
Pnueli, A., Rosner, R.: Distributed reactive systems are hard to synthesize. In: Proc. of FOCS 1990, pp. 746–757 (1990)
Rabin, M.O.: Decidability of second order theories and automata on infinite trees. Transaction of the AMS 141, 1–35 (1969)
Safra, S.: On the complexity of ω-automata. In: Proc. of FOCS 1988, pp. 319–327 (1988)
Safra, S.: Exponential determinization for omega-automata with strong-fairness acceptance condition. In: Proc. of STOC 1992, pp. 275–282 (1992)
Schewe, S.: Büchi complementation made tight. In: Proc. of STACS 2009, pp. 661–672 (2009)
Schewe, S.: Tighter bounds for the determinisation of büchi automata. In: de Alfaro, L. (ed.) FOSSACS 2009. LNCS, vol. 5504, pp. 167–181. Springer, Heidelberg (2009)
Schewe, S., Finkbeiner, B.: Satisfiability and finite model property for the alternating-time μ-calculus. In: Ésik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 591–605. Springer, Heidelberg (2006)
Schewe, S., Finkbeiner, B.: Synthesis of asynchronous systems. In: Puebla, G. (ed.) LOPSTR 2006. LNCS, vol. 4407, pp. 127–142. Springer, Heidelberg (2007)
Schewe, S., Varghese, T.: Tight bounds for the determinisation and complementation of generalised büchi automata. In: Chakraborty, S., Mukund, M. (eds.) ATVA 2012. LNCS, vol. 7561, pp. 42–56. Springer, Heidelberg (2012)
Vardi, M.Y.: The Büchi complementation saga. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 12–22. Springer, Heidelberg (2007)
Wilke, T.: Alternating tree automata, parity games, and modal μ-calculus. Bull. Soc. Math. Belg. 8(2) (May 2001)
Yan, Q.: Lower bounds for complementation of omega-automata via the full automata technique. Journal of LMCS, 4(1:5) (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag GmbH Berlin Heidelberg
About this paper
Cite this paper
Schewe, S., Varghese, T. (2014). Determinising Parity Automata. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds) Mathematical Foundations of Computer Science 2014. MFCS 2014. Lecture Notes in Computer Science, vol 8634. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44522-8_41
Download citation
DOI: https://doi.org/10.1007/978-3-662-44522-8_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44521-1
Online ISBN: 978-3-662-44522-8
eBook Packages: Computer ScienceComputer Science (R0)