Algebraic Ordinals

• Autorzy: Bloom S.L. , Ésik Z.
• Języki publikacji: EN

Abstrakty

EN

An algebraic tree T is one determined by a finite system of fixed point equations. The frontier Fr(T ) of an algebraic tree T is linearly ordered by the lexicographic order

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 99, nr 4
• Strony: 383--407
• Opis fizyczny: Bibliogr. 30 poz.

Twórcy

autor

Bloom S.L.

autor

Ésik Z.

• Department of Computer Science, Stevens Institute of Technology, Hoboken, NJ, USA,

Bibliografia

• [1] S.L. Bloom and C. Choffrut. Long words: the theory of concatenation and ω-power. Theoretical Computer Science, 259(2001), 533-548.
• [2] S.L. Bloom and Z. ésik. Deciding whether the frontier of a regular tree is scattered. Fundamenta Informaticae, XI(2004) 1-22.
• [3] S.L. Bloom and Z. ésik. Regular and algebraic words and ordinals. CALCO 2007, Bergen, LNCS 4624, Springer, 2007, 1-15.
• [4] S. L. Bloom and Z. ésik. A Mezei-Wright theorem for categorical algebras. Theoretical Computer Science, 411(2010), 341-359
• [5] L. Braud. Unpublished paper. ENS-Lyon, MR2 Intern at IRISA, Rennes.
• [6] M. Brough, B. Khoussainov and P. Nelson. Sequential automatic algebras. CiE 2008, LNCS 5028, Springer, 2008, 84-93.
• [7] Th. Colcombet. Equational presentations of tree automatic structures. Workshop on Automata, Structures, and Logic, Auckland, 2004.
• [8] B. Courcelle. Frontiers of infinite trees. Theoretical Informatics and Applications, 12(1978), 319-337.
• [9] B. Courcelle. A representation of trees by languages, Theoretical Computer Science, 6(1978), 255-279 and 7(1978), 25-55.
• [10] B. Courcelle. Fundamental properties of infinite trees. Theoretical Computer Science, 25(1983), 95-169.
• [11] W. Damm. Higher type program schemes and their tree languages. Theoretical Computer Science (Third GI Conf., Darmstadt, 1977), LNCS 48, Springer, 1977, 51-72.
• [12] W. Damm. The IO and OI hierarchies. Theoretical Computer Science, 20(1982), 95-206.
• [13] M. Dauchet and S. Tison. The theory of ground rewrite systems is decidable. LICS 1990, IEEE, 1990, 242-248
• [14] Ch. Delhommé. Automaticity of ordinals and of homogeneous graphs. C. R. Math. Acad. Sci. Paris, 339(2004), 5-10 (in French).
• [15] J. Gallier. n-rational algebras. I. Basic properties and free algebras. SIAM J. Comput., 13(1984), 750-775.
• [16] J. A. Goguen, J. W. Thatcher, E. G. Wagner and J. B. Wright. Initial algebraic semantics and continuous algebras. J. ACM, 24(1977), 68-95.
• [17] I. Guessarian. Algebraic Semantics. LNCS, vol. 99, Springer-Verlag, 1981.
• [18] F. Gécseg and M. Steinby. Tree Automata. Akadémiai Kiad´o, Budapest, 1984.
• [19] S. Heilbrunner. An algorithm for the solution of fixed-point equations for infinite words. Theoretical Informatics and Applications, 14(1980), 131-141.
• [20] B.R. Hodgson. On direct products of automaton decidable theories. Theoretical Computer Science, 19(1982), 331-335.
• [21] M. Hague, A.S. Murawawski, C.-H Luke Ong, O. Serre. Collapsable pushdown automata and recursion schemes. 23rd Annual IEEE Symposium on Logic in Computer Science, LICS, IEEE, 2008, 452-461.
• [22] B. Khoussainov, A. Nerode. Automatic presentations of structures. Logic and Comput. Complex., LNCS 960, Springer, 1995, 367-392.
• [23] B. Khoussainov, S. Rubin and F. Stephan. On automatic partial orders. Eighteenth IEEE Symposium on Logic in Computer Science, LICS, IEEE 2003, 168-177.
• [24] C.-H Luke Ong. Hierarchies of infinite structures generated by pushdown automata and recursion schemes. MFCS 2007, LNCS 4708, Springer, 2007, 15-21.
• [25] M. Lothaire. Combinatorics on Words. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997.
• [26] J.Mezei and J.Wright. Algebraic automata and context-free sets. Information and Control, 11(1967), 3-29.
• [27] J. Roitman. Introduction to Modern Set Theory. Wiley, 1990.
• [28] J.B. Rosenstein. Linear Orderings. Academic Press, New York, 1982.
• [29] W. Sierpinski. Cardinal and Ordinal Numbers. Warsaw: PWN, 1958.
• [30] W. Thomas. On frontiers of regular trees. Theoretical Informatics and Applications, vol. 20, 1986, 371-381.