Ehrenfeucht games and ordinal addition

Annals of Pure and Applied Logic 89 (1):53-73 (1997)

Abstract
We show in this paper that the theory of ordinal addition of any fixed ordinal ωα, with α less than ωω, admits a quantifier elimination. This in particular gives a new proof for the decidability result first established in 1965 by R. Büchi using transfinite automata. Our proof is based on the Ehrenfeucht games, and we show that quantifier elimination go through generalized power.RésuméOn montre ici que, pour tout ordinal α inférieur à ωω, la théorie additive de ωα admet une élimination des quantificateurs. On obtient ainsi une nouvelle preuve de la décidabilité de ces théories . On utilise ici les jeux d'Ehrenfeucht, avec un formalisme à la Ferrante et Rackoff, et on montre que le fait d'admettre une élimination des quantificateurs se transmet par produit généralisé
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(97)00005-5
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 46,223
External links

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

Weak Second‐Order Arithmetic and Finite Automata.J. Richard Büchi - 1960 - Mathematical Logic Quarterly 6 (1-6):66-92.
Definability and Decision Problems in Arithmetic.Julia Robinson - 1949 - Journal of Symbolic Logic 14 (2):98-114.

View all 7 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

On Ehrenfeucht-Fraïssé Equivalence of Linear Orderings.Juha Oikkonen - 1990 - Journal of Symbolic Logic 55 (1):65-73.
Ordinal Preference Representations.Niall M. Fraser - 1994 - Theory and Decision 36 (1):45-67.
On Winning Ehrenfeucht Games and Monadic NP.Thomas Schwentick - 1996 - Annals of Pure and Applied Logic 79 (1):61-92.
On Complexity of Ehrenfeucht–Fraïssé Games.Bakhadyr Khoussainov & Jiamou Liu - 2009 - Annals of Pure and Applied Logic 161 (3):404-415.
Trees and Ehrenfeucht–Fraı̈ssé Games.Stevo Todorčević & Jouko Väänänen - 1999 - Annals of Pure and Applied Logic 100 (1-3):69-97.
Almost Free Groups and Long Ehrenfeucht–Fraı̈ssé Games.Pauli Väisänen - 2003 - Annals of Pure and Applied Logic 123 (1-3):101-134.
Normal Forms for Elementary Patterns.Timothy J. Carlson & Gunnar Wilken - 2012 - Journal of Symbolic Logic 77 (1):174-194.
A Taxonomy of All Ordinal 2 X 2 Games.D. Marc Kilgour - 1988 - Theory and Decision 24 (2):99.
Proof Theory and Ordinal Analysis.W. Pohlers - 1991 - Archive for Mathematical Logic 30 (5-6):311-376.

Analytics

Added to PP index
2014-01-16

Total views
10 ( #773,826 of 2,285,699 )

Recent downloads (6 months)
2 ( #573,699 of 2,285,699 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature