# Branching Densities of Cube-Free and Square-Free Words
## 1 Introduction  
A formal language, which is a subset of the set of all finite words over some (usually finite) alphabets, is one of the most common objects in discrete mathematics and computer science. Languages are often defined by properties of their elements, and many \"good\" properties are hereditary--all factors (=contiguous subwords) of a word with such a property also possesses this property. Typical hereditary properties are \"to be a factor of a certain infinite word\" or \"to contain no factors from a given set\". A factorial language forms posets under some natural order relations; the relation \"to be a prefix of\" is probably the simplest relation of this sort. The diagram of this relation is called a _prefix tree_; the structure of this tree reflects the properties of the language. For example, the prefix tree of a language \(L\) can be viewed as a deterministic (finite or infinite) automaton accepting \(L\): each edge has the form \((w,wa)\) and is labeled by the letter \(a\), the root is the initial state, all nodes are final states. An important class of factorial languages is constituted by _power-free languages_. Any language of this class contains no factors from the set of \(\alpha\)-powers for a certain integer or rational \(\alpha\); an \(\alpha\)-power of a nonempty word \(u\) is the prefix of an infinite word \(uuu\cdots\) of length \(\lceil\alpha|u|\rceil\), where \(|u|\) stands for the length of \(u\). Power-free languages are studied in hundreds of papers starting with the seminal work by [PERSON] [1], but the topic still contains a number of challenging open problems. One group of problems concerns the structure of prefix trees of infinite power-free languages. Let us briefly recall the related known results. In the following text, the _subtree_ of a prefix tree means a tree consisting of some node \(w\) and all its descendants. For infinite power-free languages, there is a natural partition into \"small\" and \"big\" [2, 3, 4, 5, 6, 7, 8]: in binary languages avoiding small powers (up to \(7/3\)), the number of words grows only polynomially with length, while all other infinite power-free languages are conjectured to have exponential growth. This conjecture has been proved [4, 5, 6, 7, 8] for almost all power-free languages (up to a finite number of cases). Polynomial-size binary power-free languagespossess several distinctive properties (see, e.g., [9] Section 2.2); all properties stem from a close relation of all words from these languages to a single infinite word, called the _Thue-Morse word_[10]. Among these languages, the _overlap-free language_, avoiding all \(\alpha\)-powers with \(\alpha>2\), attracted the most attention; as a result, it is studied very well. For example, the asymptotic order of growth for this language is computed exactly [11; 12]. Further, it is decidable whether a subtree of the prefix tree, rooted at a given word \(w\), is finite or infinite [13]. Moreover, the results of [14] imply that the depth of a finite subtree can be computed in time linear in \(|w|\), and the isomorphism of two given subtrees can be decided in linear time also. Most of the results about the overlap-free language can be extended, with additional and sometimes tedious technicalities, to all small binary power-free languages (see, e.g., [4]). The knowledge about \"big\" power-free languages is rather limited. For all these languages, any subtree has at least one leaf [15]. Further, for any fixed alphabet and fixed integer \(\alpha\), it is decidable whether a given word generates finite or infinite subtrees, and every infinite subtree often branches out infinitely [16; 17]. All other results concern two particular languages: the binary 3-free (_cube-free_) language CF and the ternary 2-free (_square-free_) language SF. These two languages are the most interesting \"test cases\", the analysis of which was initiated by [PERSON] [1]. Note that the prefix tree of SF is binary in spite of the ternary alphabet, because a square-free word has no factors of the form \(aa\).