Breadth-first serialisation of trees and rational languages

2014/04/03 by Victor Marsault, Marsault, Victor, Jacques Sakarovitch +1
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL

paper · pdf · doi:10.48550/arxiv.1404.0798

15 pages

arxiv created 2014/04/03 · arxiv updated 2014/04/04

Abstract

We present here the notion of breadth-first signature and its relationship with numeration system theory. It is the serialisation into an infinite word of an ordered infinite tree of finite degree. We study which class of languages corresponds to which class of words and,more specifically, using a known construction from numeration system theory, we prove that the signature of rational languages are substitutive sequences.

Related

• Rhythmic generation of infinite trees and languages
• Revisiting regular sequences in light of rational base numeration systems
• Languages recognised by finite semigroups, and their generalisations to objects such as trees and graphs, with an emphasis on definability in monadic second-order logic
• An Application of Rational Trees in a Logic Programming Interpreter for a Procedural Language
• The Uniform Measure of Simple Regular Sets of Infinite Trees