References

  1. André Arnold (1999): The μ-calculus alternation-depth hierarchy is strict on binary trees. ITA 33(4/5), pp. 329–340. Available at http://dx.doi.org/10.1051/ita:1999121.
  2. André Arnold & Damian Niwiński (1992): Fixed point characterization of weak monadic logic definable sets of trees. In: Tree Automata and Languages, pp. 159–188.
  3. Marcin Bilkowski (2010). personal communication.
  4. Mikołaj Bojańczyk (2011): Weak MSO with the Unbounding Quantifier. Theory Comput. Syst. 48(3), pp. 554–576. Available at http://dx.doi.org/10.1007/s00224-010-9279-2.
  5. Mikolaj Bojańczyk & Thomas Colcombet (2006): Bounds in ω-Regularity. In: LICS, pp. 285–296. Available at http://doi.ieeecomputersociety.org/10.1109/LICS.2006.17.
  6. Julian C. Bradfield (1999): Fixpoint alternation: Arithmetic, transition systems, and the binary tree. ITA 33(4/5), pp. 341–356. Available at http://dx.doi.org/10.1051/ita:1999122.
  7. Arnaud Carayol & Christof Löding (2007): MSO on the Infinite Binary Tree: Choice and Order. In: CSL, pp. 161–176. Available at http://dx.doi.org/10.1007/978-3-540-74915-8_15.
  8. Arnaud Carayol, Christof Löding, Damian Niwiński & Igor Walukiewicz (2010): Choice functions and well-orderings over the infinite binary tree. Central European Journal of Mathematics 8, pp. 662–682. Available at http://dx.doi.org/10.2478/s11533-010-0046-z.
  9. Thomas Colcombet (2012): Forms of Determinism for Automata (Invited Talk). In: STACS, pp. 1–23. Available at http://dx.doi.org/10.4230/LIPIcs.STACS.2012.1.
  10. Olivier Finkel & Pierre Simonnet (2009): On Recognizable Tree Languages Beyond the Borel Hierarchy. Fundamenta Informaticae 95(2-3), pp. 287–303. Available at http://dx.doi.org/10.3233/FI-2009-151.
  11. Szczepan Hummel & MichałSkrzypczak (2012): The Topological Complexity of MSO+U and Related Automata Models. Fundamenta Informaticae 119(1), pp. 87–111.
  12. Alexander S. Kechris (1995): Classical Descriptive Set Theory. Graduate Texts in Mathematics 156. Springer-Verlag.
  13. Yiannis N. Moschovakis (2009): Descriptive Set Theory: Second Edition. Mathematical Surveys and Monographs 155. American Mathematical Society.
  14. Damian Niwiński (1986): On Fixed-Point Clones (Extended Abstract). In: ICALP, pp. 464–473. Available at http://dx.doi.org/10.1007/3-540-16761-7_96.
  15. Damian Niwiński & Igor Walukiewicz (1996): Ambiguity problem for automata on infinite trees. Unpublished note.
  16. Damian Niwiński & Igor Walukiewicz (2003): A gap property of deterministic tree languages. Theor. Comput. Sci. 1(303), pp. 215–231. Available at http://dx.doi.org/10.1016/S0304-3975(02)00452-8.
  17. Michael O. Rabin (1969): Decidability of Second-Order Theories and Automata on Infinite Trees. Transactions of the AMS 141, pp. 1–23.
  18. Michael O. Rabin (1970): Weakly Definable Relations and Special Automata. Mathematical Logic and Foundations of Set Theory, pp. 1–23.

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org