Regular languages of thin trees

Authors Mikolaj Bojanczyk, Tomasz Idziaszek, Michal Skrzypczak



PDF
Thumbnail PDF

File

LIPIcs.STACS.2013.562.pdf
  • Filesize: 0.54 MB
  • 12 pages

Document Identifiers

Author Details

Mikolaj Bojanczyk
Tomasz Idziaszek
Michal Skrzypczak

Cite AsGet BibTex

Mikolaj Bojanczyk, Tomasz Idziaszek, and Michal Skrzypczak. Regular languages of thin trees. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 562-573, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
https://doi.org/10.4230/LIPIcs.STACS.2013.562

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.
Keywords
  • infinite trees
  • regular languages
  • effective characterizations
  • topological complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail