Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Infinite labeled trees: From rational to Sturmian trees
 
research article

Infinite labeled trees: From rational to Sturmian trees

Gast, Nicolas Gabriel  
•
Gaujal, Bruno
2010
Theoretical Computer Science

This paper studies infinite unordered d-ary trees with nodes labeled by {0,1}. We introduce the notions of rational and Sturmian trees along with the definitions of (strongly) balanced trees and mechanical trees, and study the relations among them. In particular, we show that (strongly) balanced trees exist and coincide with mechanical trees in the irrational case, providing an effective construction. Such trees also have a minimal factor complexity, hence are Sturmian. We also give several examples illustrating the inclusion relations between these classes of trees.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

tcs-GastGaujal.pdf

Access type

openaccess

Size

455.23 KB

Format

Adobe PDF

Checksum (MD5)

9eb97c4393cdb25c3de881ee0a03c639

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés