Algebraic Ordinals

Article type: Research Article

Authors: Bloom, Stephen L. | Ésik, Zoltan

Affiliations: Department of Computer Science, Stevens Institute of Technology, Hoboken, NJ, USA. E-mail: bloom@cs.stevens.edu | Department of Informatics, University of Szeged, Szeged, Hungary. E-mail: ze@inf.u-szeged.hu

Abstract: 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 <ℓ If (Fr(T) <ℓ) is well-ordered, its order type is an algebraic ordinal. We prove that the algebraic ordinals are exactly the ordinals less than ω^{&omega;}^{&omega;}.

DOI: 10.3233/FI-2010-255

Journal: Fundamenta Informaticae, vol. 99, no. 4, pp. 383-407, 2010