License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.562
URN: urn:nbn:de:0030-drops-39655
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3965/
Go to the corresponding LIPIcs Volume Portal

Bojanczyk, Mikolaj ; Idziaszek, Tomasz ; Skrzypczak, Michal

Regular languages of thin trees

pdf-format:
53.pdf (0.5 MB)

Abstract

An infinite tree is called thin if it contains only countably many infinite branches. Thin trees can be seen as intermediate structures between infinite words and infinite trees. In this work we investigate properties of regular languages of thin trees.

Our main tool is an algebra suitable for thin trees. Using this framework we characterize various classes of regular languages: commutative, open in the standard topology, closed under two variants of bisimulational equivalence, and definable in WMSO logic among all trees.

We also show that in various meanings thin trees are not as rich as all infinite trees. In particular we observe a parity index collapse to level (1,3) and a topological complexity collapse to co-analytic sets. Moreover, a gap property is shown: a regular language of thin trees is either WMSO-definable among all trees or co-analytic-complete.

BibTeX - Entry

@InProceedings{bojanczyk_et_al:LIPIcs:2013:3965,
  author =	{Mikolaj Bojanczyk and Tomasz Idziaszek and Michal Skrzypczak},
  title =	{{Regular languages of thin trees}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{562--573},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3965},
  URN =		{urn:nbn:de:0030-drops-39655},
  doi =		{10.4230/LIPIcs.STACS.2013.562},
  annote =	{Keywords: infinite trees, regular languages, effective characterizations, topological complexity}
}

Keywords: infinite trees, regular languages, effective characterizations, topological complexity
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI