On cube-free ω-words generated by binary morphisms

Let h be a morphism satisfying h(a) = ax for a letter a and a nonempty word x. Then h defines an infinite word (an ω-word) when applied iteratively starting from a. Such ω-words are considered in a binary case. It is shown that only biprefixes can generate cube-free ω-words, i.e. words which do not contain a word υ³, with υ ≠ λ, as a subword. The same does not hold true for fourth power-free ω-words, the counterexample being the ω-word defined by the Fibonaccimorphism: h(a) = ba, h(b) = a.As the main result it is proved that it is decidable whether a given morphism of the above form generates a cube-free ω-word. Moreover, it is shown that no more than 10 steps of iterations are needed to solve the problem.     

On the infinite permutation generated by the period doubling word

The paper is devoted to the properties of infinite permutations. We introduce the infinite permutation ξ, in some sense similar to the period doubling word w (which is the fixed point of the morphism φ_w:00100,10101). We investigate combinatorial properties of ξ and find the complexity of ξ.     

On minimal Sturmian partial words

Partial words, which are sequences that may have some undefined positions called holes, can be viewed as sequences over an extended alphabet A_?=A∪{?}, where ? stands for a hole and matches (or is compatible with) every letter in A. The subword complexity of a partial word w, denoted by p_w(n), is the number of distinct full words (those without holes) over the alphabet that are compatible with factors of length n of w. A function f:N→N is (k,h)-feasible if for each integer N≥1, there exists a k-ary partial word w with h holes such that p_w(n)=f(n) for all n such that 1≤n≤N. We show that when dealing with feasibility in the context of finite binary partial words, the only affine functions that need investigation are f(n)=n+1 and f(n)=2n. It turns out that both are (2,h)-feasible for all non-negative integers h. We classify all minimal partial words with h holes of order N with respect to f(n)=n+1, called Sturmian, computing their lengths as well as their numbers, except when h=0 in which case we describe an algorithm that generates all minimal Sturmian full words. We show that up to reversal and complement, any minimal Sturmian partial word with one hole is of the form aⁱ?a^jba^l, where i,j,l are integers satisfying some restrictions, that all minimal Sturmian partial words with two holes are one-periodic, and that up to complement, ?(a^N−1?)^h−1 is the only minimal Sturmian partial word with h≥3 holes. Finally, we give upper bounds on the lengths of minimal partial words with respect to f(n)=2n, showing them tight for h=0,1 or 2.     

Fixed points avoiding Abelian k-powers

We show that the problem of whether the fixed point of a morphism avoids Abelian k-powers is decidable under rather general conditions, the most important being that the frequency matrix M of the morphism be invertible and that |M−1|<1, where |⋅| denotes a certain matrix norm.     

Unbordered factors and Lyndon words

A primitive word w is a Lyndon word if w is minimal among all its conjugates with respect to some lexicographic order. A word w is bordered if there is a nonempty word u such that w=uvu for some word v. A right extension of a word w of length n is a word wu where all factors longer than n are bordered. A right extension wu of w is called trivial if there exists a positive integer k such that w^k=uv for some word v.We prove that Lyndon words have only trivial right extensions. Moreover, we give a conjecture which characterizes a property of every word w which has a nontrivial right extension of length 2|w|-2.     

Avoiding squares and overlaps over the natural numbers

We consider avoiding squares and overlaps over the natural numbers, using a greedy algorithm that chooses the least possible integer at each step; the word generated is lexicographically least among all such infinite words. In the case of avoiding squares, the word is 01020103, the familiar ruler function, and is generated by iterating a uniform morphism. The case of overlaps is more challenging. We give an explicitly-defined morphism that generates the lexicographically least infinite overlap-free word by iteration. Furthermore, we show that for all with h≤k, the word φ^k−h(h) is the lexicographically least overlap-free word starting with the letter h and ending with the letter k, and give some of its symmetry properties.     

Graph minors. II. Algorithmic aspects of tree-width

We introduce an invariant of graphs called the tree-width, and use it to obtain a polynomially bounded algorithm to test if a graph has a subgraph contractible to H, where H is any fixed planar graph. We also nonconstructively prove the existence of a polynomial algorithm to test if a graph has tree-width ≤ w, for fixed w. Neither of these is a practical algorithm, as the exponents of the polynomials are large. Both algorithms are derived from a polynomial algorithm for the DISJOINT CONNECTING PATHS problem (with the number of paths fixed), for graphs of bounded tree-width.     

Preface

The following morphic characterization of EOL languages is established. The family of EOL languages equals the family of all languages of the form h(L∩R) where h is a morphism, R is a regular language and L is the maximal solution of an equation $\text{?(X) = g(X)}$, where ? is a morphism, g is a coding and X is a language variable. It is shown that if g is allowed to be a weak coding, then a larger family of languages is obtained, which however is strictly contained in the family of ETOL languages.     

A new simultaneous iterative method with a parameter for solving the extended split equality problem and the extended split equality fixed point problem

In this article, we first propose an extended split equality problem which is an extension of the convex feasibility problem, and then introduce a parameter w to establish the fixed point equation system. We show the equivalence of the extended split equality problem and the fixed point equation system. Based on the fixed point equation system, we present a simultaneous iterative algorithm and obtain the weak convergence of the proposed algorithm. Further, by introducing the concept of a G-mapping of a finite family of strictly pseudononspreading mappings \(\{T_{i}\}_{i = 1}^{N}\), we consider an extended split equality fixed point problem for G-mappings and give a simultaneous iterative algorithm with a way of selecting the stepsizes which do not need any prior information about the operator norms, and the weak convergence of the proposed algorithm is obtained. We apply our iterative algorithms to some convex and nonlinear problems. Finally, several numerical results are shown to confirm the feasibility and efficiency of the proposed algorithms.     

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

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.     

Rational homotopy of the (homotopy) fixed point sets of circle actions

In this paper, when G is the circle S¹ and M is a G-space, we study the rational homotopy type of the fixed point set MG, the homotopy fixed point set MhG, and the natural injection MG→MhG.     

Output-Polynomial Enumeration of All Fixed-Cardinality Ideals of a Poset,Respectively All Fixed-Cardinality Subtrees of a Tree

The N cardinality k ideals of any w-element poset (k?≤?w fixed) can be enumerated in time O(Nw ³). The corresponding bound for k-element subtrees of a w-element tree is O(Nw ⁵). An algorithm is described that by the use of wildcards displays all order ideals of a poset in a compact manner, i.e. not one by one.     

WORD READING IS A CRYSTAL MORPHISM

We observe that word reading is a crystal morphism. This leads us to prove that for SLn (?) the map from all galleries to Mikovi?–Vilonen cycles is a surjective morphism of crystals. We also compute the fibers of this map in terms of the Littelmann path model.     

Some fixed point results on L-embedded Banach spaces

In this paper we prove that w-fixed point property and w^★-fixed point property are equivalent concepts for L-embedded Banach spaces which are duals of M-embedded spaces. Similar results will be obtained with respect to the normal structure. These equivalences will be applied to establish new fixed point results for different examples. We will also prove the existence of fixed points for both nonexpansive and asymptotically regular mappings defined on subsets of L-embedded Banach spaces which are sequentially compact for the abstract measure topology. We will check that our results do not hold in the case of the weak topology.     

Fine and Wilf words for any periods

Let w = w₁ … w_n be a word of maximal length n, and with a maximal number of distinct letters for this length, such that w has periods p₁, …, p_n but not period gcd(p₁,…,p_r). We provide a fast algorithm to compute n and w. We show that w is uniquely determined apart from isomorphism and that it is a palindrome. Furthermore we give lower and upper bounds for n as explicit functions of p₁, …p_r. For r = 2 the exact value of n is due to Fine and Wilf. In case the number of distinct letters in the extremal word equals r a formula for n had been given by Castelli, Mignosi and Restivo in case r = 3 and by Justin if r > 3.     

Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups

A pseudo-natural algorithm for the word problem of a finitely presented group is an algorithm which not only tells us whether or not a word w equals 1 in the group but also gives a derivation of 1 from w when w equals 1. In [13], [14] Madlener and Otto show that, if we measure complexity of a primitive recursive algorithm by its level in the Grzegorczyk hierarchy, there are groups in which a pseudo-natural algorithm is arbitrarily more complicated than an algorithm which simply solves the word problem. In a given group the lowest degree of complexity that can be realised by a pseudo-natural algorithm is essentially the derivational complexity of that group. Thus the result separates the derivational complexity of the word problem of a finitely presented group from its intrinsic complexity. The proof given in [13] involves the construction of a finitely presented group G from a Turing machine T such that the intrinsic complexity of the word problem for G reflects the complexity of the halting problem of T, while the derivational complexity of the word problem for G reflects the runtime complexity of T. The proof of one of the crucial lemmas in [13] is only sketched, and part of the purpose of this paper is to give the full details of this proof. We will also obtain a variant of their proof, using modular machines rather than Turing machines. As for several other results, this simplifies the proofs considerably. MSC: 03D40, 20F10.     

The standard factorization of Lyndon words: an average point of view

A non-empty word w is a Lyndon word if and only if it is strictly smaller for the lexicographical order than any of its proper suffixes. Such a word w is either a letter or admits a standard factorization uv where v is its smallest proper suffix. For any Lyndon word v, we show that the set of Lyndon words having v as right factor of the standard factorization is regular and compute explicitly the associated generating function. Next, considering the Lyndon words of length n over a two-letter alphabet, we establish that, for the uniform distribution, the average length of the right factor v of the standard factorization is asymptotically 3n/4.     

Successions in Words and Compositions

We consider words over the alphabet [k] = {1, 2, . . . , k}, k ?? 2. For a fixed nonnegative integer p, a p-succession in a word w ₁ w ₂ . . . w _n consists of two consecutive letters of the form (w _i , w _i ?+ p), i = 1, 2, . . . , n ? 1. We analyze words with respect to a given number of contained p-successions. First we find the mean and variance of the number of p-successions. We then determine the distribution of the number of p-successions in words of length n as n (and possibly k) tends to infinity; a simple instance of a phase transition (Gaussian-Poisson-degenerate) is encountered. Finally, we also investigate successions in compositions of integers.