References

  1. A. Bès (2008): An Application of the Feferman-Vaught Theorem to Automata and Logics for Words over an Infinite Alphabet. Logical Methods in Computer Science 4, pp. 1–23, doi:10.2168/LMCS-4(1:8)2008.
  2. M. Bojanczyk, A. Muscholl, T. Schwentick, L. Segoufin & C. David (2006): Two-variable logic on words with data. In: Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS '06). IEEE Computer Society, pp. 7–16, doi:10.1109/LICS.2006.51.
  3. J.R. Büchi (1962): On a decision method in restricted second order arithmetic. In: Logic, Methodology and Philosophy of Science: Proceedings of the 1960 International Congress. Stanford Univ. Press, pp. 1–11.
  4. C. Choffrut & S. Grigorieff (2009): Finite n-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al. Theor. Comput. Sci. 410(1), pp. 16–34, doi:10.1016/j.tcs.2008.07.018.
  5. H.-D. Ebbinghaus, J. Flum & W. Thomas (2007): Einführung in die mathematische Logik, 5 edition. Spektrum Akademischer Verlag, Heidelberg.
  6. D. Kuske & M. Lohrey (2006): Monadic chain logic over iterations and applications to pushdown systems. In: Logic in Computer Science, 2006. IEEE Computer Society, pp. 91–100, doi:10.1109/LICS.2006.35.
  7. M. Minsky (1967): Computation: finite and infinite machines. Prentice-Hall.
  8. F. Neven, T. Schwentick & V. Vianu (2004): Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Log. 5(3), pp. 403–435, doi:10.1145/1013560.1013562.
  9. A. Potthoff & W. Thomas (1993): Regular tree languages without unary symbols are star-free. In: Proceedings of Fundamentals of Computation Theory, FCT '93, LNCS 710. Springer, pp. 396–405, doi:10.1007/3-540-57163-9_34.
  10. M.O. Rabin (1969): Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc 141(1), pp. 1–35, doi:10.2307/1995086.
  11. F.P. Ramsey (1930): On a problem of formal logic. Proceedings of the London Mathematical Society 2(1), pp. 264, doi:10.1112/plms/s2-30.1.264.
  12. A.L. Semenov (1984): Decidability of monadic theories. In: Proceedings of Mathematical Foundations of Computer Science, MFCS '84, LNCS 176. Springer, pp. 162–175, doi:10.1007/BFb0030296.
  13. S. Shelah (1975): The monadic theory of order. Annals of Mathematics 102, pp. 379–419, doi:10.2307/1971037.
  14. J. Stupp (1975): The lattice-model is recursive in the original model. Technical Report. Institute of Mathematics, The Hebrew University, Jerusalem.
  15. W. Thomas (1990): Automata on Infinite Objects. In: J. van Leeuwen: Handbook of Theoretical Computer Science: Formal Models and Sematics B. Elsevier and MIT Press, pp. 133–192.
  16. W. Thomas (1990): Infinite trees and automaton definable relations over omega-words. In: Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science, STACS '90. Springer, pp. 263–277, doi:10.1007/3-540-52282-4_49.
  17. W. Thomas (1997): Languages, automata, and logic. In: G. Rozenberg & A. Salomaa: Handbook of formal languages 3. Springer, New York, pp. 389–455, doi:10.1007/978-3-642-59126-6_7.
  18. W. Thomas (2009): Path logics with synchronization. In: K. Lodaya, M. Mukund & R. Ramanujam: Perspectives in Concurrency Theory, IARCS-Universities. Universities Press, pp. 469–481.
  19. I. Walukiewicz (2002): Monadic second-order logic on tree-like structures. Theoretical Computer Science 275(1-2), pp. 311–346, doi:10.1016/S0304-3975(01)00185-2.

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