EXACT COMPLEXITY-BOUNDS FOR ORDINAL ADDITION

Authors
MAURIN F
Citation
F. Maurin, EXACT COMPLEXITY-BOUNDS FOR ORDINAL ADDITION, Theoretical computer science, 165(2), 1996, pp. 247-273
Citations number
13
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
165
Issue
2
Year of publication
1996
Pages
247 - 273
Database
ISI
SICI code
0304-3975(1996)165:2<247:ECFOA>2.0.ZU;2-L
Abstract
We know that the weak second-order theory of any ordinal equipped with order is decidable (Buchi 1962). We give here an improved proof of th is result, with finite automata instead of the transfinite automata th at were used in the original proof. When analysing the decision algori thm, we give the exact complexity bound of the latter theory.