Regular languages of thin trees

For a fixed alphabet \(A\), a \textit{forest} is a ``mapping from its set of nodes \(\mathrm{dom}(t)\subset\omega^+\) into \(A\). It is additionally assumed that ``a forest is finitely branching: for every \(w\in\omega^\ast\) there are only finitely many nodes of the form \(wn\) for \(n\in {\mathbb N}\) in \(\mathrm{dom}(t)\); these nodes (of the form \(wn\)) are called \textit{roots} when \(w=\epsilon\), and are called the \textit{children} of \(w\) when \(w\neq\epsilon\). A \textit{tree} is a forest with exactly one root. ``A forest is \textit{regular} if it has only finitely many distinct subtrees. A forest is \textit{thin} if it has countably many branches. This notion has different names: e.g. a thin tree by this definition is called a \textit{scattered tree} in [\textit{A. Rabinovic} and \textit{S. Rubin}, ``Interpretations in trees with countably many branches, in: Proceedings of the 27th annual IEEE symposium on logic in computer science, LICS'12. Los Alamitos, CA: IEEE Computer Society. 551--560 (2012; \url{doi:10.1109/LICS.2012.65})] and a thin forest is called a \textit{tame tree} (up to isomorphism) in [\textit{S. Lifsches} and \textit{S. Shelah}, J. Symb. Log. 63, No. 1, 103--127 (1998; Zbl 0899.03010)]. In this paper, the authors ``propose to study \textit{thin trees}, which generalize both finite trees and infinite words but which are still simpler than arbitrary infinite trees. A tree is called thin if it has only countably many infinite branches (or equivalently, it does not contain a full binary tree as a minor). The authors believe that ``thin trees are a good stepping stone on the way to understanding regular languages of arbitrary infinite trees. ``The developments presented in this paper, in particular introduction of thin forest algebra, lead to some new results on unambiguity and uniformization on infinite trees \dots. The characterizations in the paper are divided into two cases by the authors: Effective characterizations. The following classes of regular languages of thin trees are characterized in terms of finite sets of identities: {\parindent=0.6cm \begin{itemize}\item[--] ``closed under rearranging of siblings, \item[--] open in the standard topology, \item[--] definable in the temporal logic EF, \item[--] definable among all trees in weak MSO logic. \end{itemize}} Upper bounds. It is shown that in various contexts thin trees are not as rich as generic trees: {\parindent=0.6cm \begin{itemize}\item[--] ``The Rabin-Mostowski index hierarchy collapses to the level \((1,3)\) on thin trees. \item[--] The projective hierarchy of regular languages collapses to the level of \(\Pi_1^1\) on thin trees (comparing to \(\Delta_2^1\) in the class of all trees). \item[--] We observe a \textit{gap property}\dots : a regular language of thin trees, treated as a subset of all trees, is either definable in weak MSO logic or \(\Pi_1^1\)-complete. \item[--] If we treat thin trees as our universe then no regular language is topologically harder than Borel sets. \end{itemize}}

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Regular languages of thin trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290908)