Dimensionality of biinfinite systems

The problem of determining the uniqueness of the coefficient of interpolation of M compactly supported real functions, with a biinfinite sequence of interpolation points, leads to the study of the kernel Z of the biinfinite block Toeplitz matrix

$\text{D=}\text{?}\text{?}\text{A}\text{B}\text{A}\text{B}\text{?}\text{?}$

. The dimension of Z is found by considering the “maximal solvable subspace” V (relative to A and B). Further results are obtained using the Kronecker canonical form of the matrix pencil A+λB and “restricted generalized inverses” of A (and B).     

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.     

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).     

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.     

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.     

字集的识别模型

在[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     

Counting minimal semi-Sturmian words

A finite Sturmian   word w$w$ is a balanced word over the binary alphabet {a,b}$\{a,b\}$, that is, for all subwords u$u$ and v$v$ of w$w$ of equal length, |_|u|a−_|v|a|≤1$|{\left|u\right|}_a-{\left|v\right|}_a|\le 1$, where _|u|a${\left|u\right|}_a$ and _|v|a${\left|v\right|}_a$ denote the number of occurrences of the letter a$a$ in u$u$ and v$v$, respectively. There are several other characterizations, some leading to efficient algorithms for testing whether a finite word is Sturmian. These algorithms find important applications in areas such as pattern recognition, image processing, and computer graphics. Recently, Blanchet-Sadri and Lensmire considered finite semi-Sturmian words of minimal length and provided an algorithm for generating all of them using techniques from graph theory. In this paper, we exploit their approach in order to count the number of minimal semi-Sturmian words. We also present some other results that come from applying this graph theoretical framework to subword complexity.     

Restricted words by adjacencies

A recurrence, a determinant formula, and generating functions are presented for enumerating words with restricted letters by adjacencies. The main theorem leads to refinements (with up to two additional parameters) of known results on compositions, polyominoes, and permutations. Among the examples considered are (1) the introduction of the ascent variation on compositions, (2) the enumeration of directed vertically convex polyominoes by upper descents, area, perimeter, relative height, and column number, (3) a tri-variate extension of MacMahon's determinant formula for permutations with prescribed descent set, and (4) a combinatorial setting for an entire sequence of bibasic Bessel functions.     

On palindromic factorization of words

Given a finite word u, we define its palindromic length  _|u|pal${|u|}_{\mathrm{pal}}$ to be the least number n   such that u=_v1v2…_vn$u=v_1{v}_2\dots v_n$ with each _vi$v_i$ a palindrome. We address the following open question: let P be a positive integer and w   an infinite word such that _|u|pal?P${|u|}_{\mathrm{pal}}?P$ for every factor u of w. Must w be ultimately periodic? We give a partial answer to this question by proving that for each positive integer k, the word w must contain a k  -power, i.e., a factor of the form u^k$u^k$. In particular, w cannot be a fixed point of a primitive morphism. We also prove more: for each pair of positive integers k and l, the word w must contain a position covered by at least l distinct k-powers. In particular, w cannot be a Sierpinski-like word.     

Lyndon factorization of sturmian words

We express any general characteristic sturmian word as a unique infinite non-increasing product of Lyndon words. Using this identity, we give a new ω-division for characteristic sturmian words. We also give a short proof of a result by Berstel and de Luca (Sturmian words, Lyndon words and trees, Theoret. Comput. Sci., 178 (1997) 171–203.); more precisely, we show that the set of factors of sturmian words that qualify as Lyndon words is the set of primitive Christoffel words.     

On highly palindromic words

We study some properties of palindromic (scattered) subwords of binary words. In view of the classical problem on subwords, we show that the set of palindromic subwords of a word characterizes the word up to reversal.Since each word trivially contains a palindromic subword of length at least half of its length-a power of the prevalent letter-we call a word that does not contain any palindromic subword longer than half of its length minimal palindromic. We show that every minimal palindromic word is abelian unbordered, that is, no proper suffix of the word can be obtained by permuting the letters of a proper prefix.We also propose to measure the degree of palindromicity of a word w by the ratio |rws|/|w|, where the word rws is minimal palindromic and rs is as short as possible. We prove that the ratio is always bounded by four, and construct a sequence of words that achieves this bound asymptotically.     

On highly potential words

We introduce a class of infinite words, called highly potential words because of their seemingly high potential of being a good supply of examples and counterexamples regarding various problems on words. We prove that they are all aperiodic words of finite positive defect, and having their set of factors closed under reversal, thus giving examples Brlek and Reutenauer were looking for. We prove that they indeed satisfy the Brlek–Reutenauer conjecture. We observe that each highly potential word is recurrent, but not uniformly recurrent. Considering a theorem from the paper of Balková, Pelantová and Starosta, later found to be incorrect, we show that highly potential words constitute an infinite family of counterexamples to that theorem. Finally, we construct a highly potential word which is a fixed point of a nonidentical morphism, thus showing that a stronger version of a conjecture by Blondin-Massé et al., as stated by Brlek and Reutenauer, is false.