DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2009.2310

Covering of ordinals

Authors: Laurent Braud

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

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.

Cite as

Laurent Braud. Covering of ordinals. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 97-108, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{braud:LIPIcs.FSTTCS.2009.2310,
  author =	{Braud, Laurent},
  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 =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.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}
}

Search Results

Documents authored by Braud, Laurent

Covering of ordinals

Abstract

Cite as

Thanks for your feedback!

Could not send message