Conditional large deviations for a sequence of words

Cut an i.i.d. sequence (_Xi)$\left(X_i\right)$ of ‘letters’ into ‘words’ according to an independent renewal process. Then one obtains an i.i.d. sequence of words, and thus the level 3 large deviation behaviour of this sequence of words is governed by the specific relative entropy. We consider the corresponding problem for the conditional   empirical process of words, where one conditions on a typical underlying (_Xi)$\left(X_i\right)$. We find that if the tails of the word lengths decay exponentially, the large deviations under the conditional distribution are almost surely again governed by the specific relative entropy, but the set of attainable limits is restricted.     

Topology of words

We introduce a topological approach to words. Words are approximatedby Gauss words and then studied up to modifications inspiredby homotopy of plane curves.     

Count of primitive words

Abstract. The present paper concerns with the formula of the count of primitive words and ex-changeable primitive words.     

The perimeter of words

We define $\left[k\right]=\{1,2,\dots ,k\}$ to be a (totally ordered) alphabet on $k$ letters. A word $w$ of length $n$ on the alphabet $\left[k\right]$ is an element of ${\left[k\right]}^n$. A word can be represented by a bargraph (i.e., by a column-convex polyomino whose lower edges lie on the $x$-axis) in which the height of the $i$th column equals the size of the $i$th part of the word. Thus these bargraphs have heights which are less than or equal to $k$. We consider the perimeter, which is the number of edges on the boundary of the bargraph. By way of Cramer’s method and the kernel method, we obtain the generating function that counts the perimeter of words. Using these generating functions we find the average perimeter of words of length $n$ over the alphabet $\left[k\right]$. We also show how the mean and variance can be obtained using a direct counting method.     

Relations on words

In the first part of this survey, we present classical notions arising in combinatorics on words: growth function of a language, complexity function of an infinite word, pattern avoidance, periodicity and uniform recurrence. Our presentation tries to set up a unified framework with respect to a given binary relation.In the second part, we mainly focus on abelian equivalence, $k$-abelian equivalence, combinatorial coefficients and associated relations, Parikh matrices and $M$-equivalence. In particular, some new refinements of abelian equivalence are introduced.     

Quasiperiods of biinfinite words

We study the notion of quasiperiodicity, in the sense of “coverability”, for biinfinite words. All previous work about quasiperiodicity focused on right infinite words, but the passage to the biinfinite case could help to prove stronger results about quasiperiods of Sturmian words. We demonstrate this by showing that all biinfinite Sturmian words have infinitely many quasiperiods, which is not quite (but almost) true in the right infinite case, and giving a characterization of those quasiperiods.The main difference between right infinite and the biinfinite words is that, in the latter case, we might have several quasiperiods of the same length. This is not possible with right infinite words because a quasiperiod has to be a prefix of the word. We study in depth the relations between quasiperiods of the same length in a given biinfinite quasiperiodic word. This study gives enough information to allow to determine the set of quasiperiods of an arbitrary word.     

On a problem of P. Hall for Engel words

Let θ be a word in n variables and let G be a group; the marginal and verbal subgroups of G determined by θ are denoted by θ(G) and θ ^*(G), respectively. The following problems are generally attributed to P. Hall:

1. (I)
   If π is a set of primes and |G : θ ^*(G)| is a finite π-group, is θ(G) also a finite π-group?
    
2. (II)
   If θ(G) is finite and G satisfies maximal condition on its subgroups, is |G : θ ^*(G)| finite?
    
3. (III)
   If the set \({\{\theta(g_1,\ldots,g_n) \;|\; g_1,\ldots,g_n\in G\}}\) is finite, does it follow that θ(G) is finite?
    

We investigate the case in which θ is the n-Engel word e _n  = [x, _n y] for \({n\in\{2,3,4\}}\) .

     

The length and thickness of words in a free group

In this paper we generalize the notion of a cut point of a graph. We assign to each graph a non-negative integer, called its thickness, so that a graph has thickness 0 if and only if it has a cut point. We then apply a method of J. H. C. Whitehead to show that if the coinitial graph of a given word has thickness , then any word equivalent to it in a free group of rank has length at least . We also define what it means for a word in a free group to be separable and we show that there is an algorithm to decide whether or not a given word is separable.

     

Unbordered partial words

An unbordered word is a string over a finite alphabet such that none of its proper prefixes is one of its suffixes. In this paper, we extend the results on unbordered words to unbordered partial words. Partial words are strings that may have a number of “do not know” symbols. We extend a result of Ehrenfeucht and Silberger which states that if a word u can be written as a concatenation of nonempty prefixes of a word v, then u can be written as a unique concatenation of nonempty unbordered prefixes of v. We study the properties of the longest unbordered prefix of a partial word, investigate the relationship between the minimal weak period of a partial word and the maximal length of its unbordered factors, and also investigate some of the properties of an unbordered partial word and how they relate to its critical factorizations (if any).     

字集的识别模型

在[2]中，讨论了符号字表达式的归约问题．在字归约定理的基础上，该文将研究字集X5的归约结构及其识别模型．     

Lectures on topology of words

We discuss a topological approach to words introduced by the author in [Tu2]–[Tu4]. Words on an arbitrary alphabet are approximated by Gauss words and then studied up to natural modifications inspired by the Reidemeister moves on knot diagrams. This leads us to a notion of homotopy for words. We introduce several homotopy invariants of words and give a homotopy classification of words of length five. Based on notes by Eri Hatakenaka, Daniel Moskovich, and Tadayuki Watanabe     

Homotopy invariants of Gauss words

By defining combinatorial moves, we can define an equivalence relation on Gauss words called homotopy. In this paper we define a homotopy invariant of Gauss words. We use this to show that there exist Gauss words that are not homotopic to the empty Gauss word, disproving a conjecture by Turaev. In fact, we show that there are an infinite number of equivalence classes of Gauss words under homotopy.     

Weinbaum factorizations of primitive words

C. M. Weinbaum [1] showed the following: Let w be a primitive word and a be letter in w. Then a conjugate of w can be written as uv such that a is a prefix and a suffix of u, but v neither starts nor ends with a, and u and v have a unique position in w as cyclic factors. The latter condition means that there is exactly one conjugate of w having u as a prefix and there is exactly one conjugate of w having v as a prefix. It is this condition which makes the result non-trivial. We give a simplified proof for Weinbaum’s result. Guided by this proof we exhibit quite different, but still simple, proofs for more general statements. For this purpose we introduce the notion of Weinbaum factor and Weinbaum factorization.     

Enumeration of irreducible binary words

Overlap free words over two letters are called irreducible binary words. Let d(n) denote the number of irreducible binary words of length n. In this paper we show that there are positive constants C₁ and C₂ such that C₁n^1.155<d(n)<C₂n^1.587 holds for all n>0.