License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2310
URN: urn:nbn:de:0030-drops-23108
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2310/
Braud, Laurent
Covering of ordinals
Abstract
The paper focuses on the structure of fundamental sequences of
ordinals smaller than $\e$. A first result is the construction of a
monadic second-order formula identifying a given structure, whereas
such a formula cannot exist for ordinals themselves. The structures
are precisely classified in the pushdown hierarchy. Ordinals are also
located in the hierarchy, and a direct presentation is given.
BibTeX - Entry
@InProceedings{braud:LIPIcs:2009:2310,
author = {Laurent Braud},
title = {{Covering of ordinals}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {97--108},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-13-2},
ISSN = {1868-8969},
year = {2009},
volume = {4},
editor = {Ravi Kannan and K. Narayan Kumar},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2310},
URN = {urn:nbn:de:0030-drops-23108},
doi = {10.4230/LIPIcs.FSTTCS.2009.2310},
annote = {Keywords: Ordinal theory, pushdown hierarchy, fundamental sequence, monadic second-order logic, prefix-recognizable graphs}
}
Keywords: |
|
Ordinal theory, pushdown hierarchy, fundamental sequence, monadic second-order logic, prefix-recognizable graphs |
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
Issue Date: |
|
2009 |
Date of publication: |
|
14.12.2009 |