The order types of termination orderings on monadic terms, strings and monadic terms, strings and multisets
David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 62 (2):624-635 (1997)
We consider total well-founded orderings on monadic terms satisfying the replacement and full invariance properties. We show that any such ordering on monadic terms in one variable and two unary function symbols must have order type ω, ω 2 or ω ω . We show that a familiar construction gives rise to continuum many such orderings of order type ω. We construct a new family of such orderings of order type ω 2 , and show that there are continuum many of these. We show that there are only four such orderings of order type ω ω , the two familiar recursive path orderings and two closely related orderings. We consider also total well-founded orderings on N n which are preserved under vector addition. We show that any such ordering must have order type ω k for some 1 ≤ k ≤ n. We show that if $k there are continuum many such orderings, and if k = n there are only n!, the n! lexicographic orderings
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Ludwig von Auer (1999). Dynamic Choice Mechanisms. Theory and Decision 46 (3):295-312.
Shmuel Lifsches & Saharon Shelah (1998). Uniformization and Skolem Functions in the Class of Trees. Journal of Symbolic Logic 63 (1):103-127.
M. Marshall (2006). Local-Global Properties of Positive Primitive Formulas in the Theory of Spaces of Orderings. Journal of Symbolic Logic 71 (4):1097 - 1107.
Patrick Dehornoy (1990). A Coding of the Countable Linear Orderings. Studia Logica 49 (4):585 - 590.
Juha Kontinen & Jakub Szymanik (2011). Characterizing Definability of Second-Order Generalized Quantifiers. In L. Beklemishev & R. de Queiroz (eds.), Proceedings of the 18th Workshop on Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence 6642. Springer.
Shmuel Lifsches & Saharon Shelah (1997). Peano Arithmetic May Not Be Interpretable in the Monadic Theory of Linear Orders. Journal of Symbolic Logic 62 (3):848-872.
Juha Oikkonen (1992). A Recursion Principle for Linear Orderings. Journal of Symbolic Logic 57 (1):82-96.
C. J. Ash (1991). A Construction for Recursive Linear Orderings. Journal of Symbolic Logic 56 (2):673-683.
Added to index2009-01-28
Total downloads3 ( #290,439 of 1,098,981 )
Recent downloads (6 months)2 ( #175,054 of 1,098,981 )
How can I increase my downloads?