Overlap-freeness in infinite partial words

We prove that there exist infinitely many infinite overlap-free binary partial words containing at least one hole. Moreover, we show that these words cannot contain more than one hole and the only hole must occur either in the first or in the second position. We define that a partial word is $k$-overlap-free if it does not contain a factor of the form $xyxyx$ where the length of $x$ is at least $k$. We prove that there exist infinitely many 2-overlap-free binary partial words containing an infinite number of holes.     

Square-free partial words

We say that a partial word w over an alphabet A is square-free if every factor xx^′ of w such that x and x^′ are compatible is either of the form ?a or a? where ? is a hole and a∈A. We prove that there exist uncountably many square-free partial words over a ternary alphabet with an infinite number of holes.     

Avoiding large squares in infinite binary words

We consider three aspects of avoiding large squares in infinite binary words. First, we construct an infinite binary word avoiding both cubes xxx and squares yy with $\left|y\right|⩾4$; our construction is somewhat simpler than the original construction of Dekking. Second, we construct an infinite binary word avoiding all squares except $0^2$, $1^2$, and $(01{)}^2$; our construction is somewhat simpler than the original construction of Fraenkel and Simpson. In both cases, we also show how to modify our construction to obtain exponentially many words of length n with the given avoidance properties. Finally, we answer an open question of Prodinger and Urbanek from 1979 by demonstrating the existence of two infinite binary words, each avoiding arbitrarily large squares, such that their perfect shuffle has arbitrarily large squares.     

Periods in Extensions of Words

Let π(w) denote the minimum period of the word w,let w be a primitive word with period π(w) < |w|, and let z be a prefix of w. It is shown that if π(wz) = π(w), then |z| < π(w) − gcd (|w|, |z|). Detailed improvements of this result are also proven. Finally, we show that each primitive word w has a conjugate w′ = vu, where w = uv, such that π(w′) = |w′| and |u| < π(w). As a corollary we give a short proof of the fact that if u,v,w are words such that u ² is a prefix of v ², and v ² is a prefix of w ², and v is primitive, then |w| > 2|u|.     

A generalization of Thue freeness for partial words

This paper approaches the combinatorial problem of Thue freeness for partial words. Partial words are sequences over a finite alphabet that may contain a number of “holes”. First, we give an infinite word over a three-letter alphabet which avoids squares of length greater than two even after we replace an infinite number of positions with holes. Then, we give an infinite word over an eight-letter alphabet that avoids longer squares even after an arbitrary selection of its positions are replaced with holes, and show that the alphabet size is optimal. We find similar results for overlap-free partial words.     

Fewest repetitions versus maximal-exponent powers in infinite binary words

A square is the concatenation of a nonempty word with itself. A word has period p if its letters at distance p match. The exponent of a nonempty word is the quotient of its length over its smallest period. In this article we give some new results on the trade-off between the number of squares and the number of maximal-exponent powers in infinite binary words, in the three cases where the maximal exponent is 7/3, 5/2, and 3. These are the only threshold values related to the question.     

Minimal non-convex words

Using a combinatorial characterization of digital convexity based on words, one defines the language of convex words. The complement of this language forms an ideal whose minimal elements, with respect to the factorial ordering, appear to have a particular combinatorial structure very close to the Christoffel words. In this paper, those words are completely characterized as those of the form uw^kv where k≥1, w=u⋅v and u,v,w are Christoffel words. Also, by considering the most balanced among the unbalanced words, we obtain a second characterization for a special class of minimal non-convex words that are of the form u²v² corresponding to the case k=1 in the previous form.     

On the number of frames in binary words

A frame is a square uu, where u is an unbordered word. Let F(n) denote the maximum number of distinct frames in a binary word of length n. We count this number for small values of n and show that F(n) is at most ⌊n/2⌋+8 for all n and greater than 7n/30−? for any positive ? and infinitely many n. We also show that Fibonacci words, which are known to contain plenty of distinct squares, have only a few frames. Moreover, by modifying the Thue-Morse word, we prove that the minimum number of occurrences of frames in a word of length n is ⌈n/2⌉−2.     

A proof of the extended Duval's conjecture

We give a short and elementary proof of the following stronger version of Duval's conjecture: let u be an unbordered word, and $v$ a word of length $\left|u\right|-1$, such that $v$ is not a prefix of u. Then u$v$ contains an unbordered word of length at least $\left|u\right|+1$.     

Pseudo-cyclic renewal systems

A finite set W of words over an alphabet A is cyclic if, whenever u,v∈A^∗ and uv,vu∈W^∗, we have u,v∈W^∗. If it is only assumed that the property holds for all u,v∈A^∗ with a large length, then W is called pseudo-cyclic, that is, there is N∈N such that, whenever u,v∈A^∗ with |u|, |v|≥N and uv,vu∈W^∗, we have u,v∈W^∗. We analyze the class of pseudo-cyclic sets and describe how it is related to the open question which asks whether every irreducible shift of finite type is conjugate to a renewal system.     

Avoidable binary patterns in partial words

The problem of classifying all the avoidable binary patterns in (full) words has been completely solved (see Chap. 3 of M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002). In this paper, we classify all the avoidable binary patterns in partial words, or sequences that may have some undefined positions called holes. In particular we show that, if we do not substitute any variable of the pattern by a partial word consisting of only one hole, the avoidability index of the pattern remains the same as in the full word case.     

On the complexity of deciding avoidability of sets of partial words

Blanchet-Sadri et al. have shown that Avoidability, or the problem of deciding the avoidability of a finite set of partial words over an alphabet of size k≥2, is NP-hard [F. Blanchet-Sadri, R. Jungers, J. Palumbo, Testing avoidability on sets of partial words is hard, Theoret. Comput. Sci. 410 (2009) 968-972]. Building on their work, we analyze in this paper the complexity of natural variations on the problem. While some of them are NP-hard, others are shown to be efficiently decidable. Using some combinatorial properties of de Bruijn graphs, we establish a correspondence between lengths of cycles in such graphs and periods of avoiding words, resulting in a tight bound for periods of avoiding words. We also prove that Avoidability can be solved in polynomial space, and reduces in polynomial time to the problem of deciding the avoidability of a finite set of partial words of equal length over the binary alphabet. We give a polynomial bound on the period of an infinite avoiding word, in the case of sets of full words, in terms of two parameters: the length and the number of words in the set. We give a polynomial space algorithm to decide if a finite set of partial words is avoided by a non-ultimately periodic infinite word. The same algorithm also decides if the number of words of length n avoiding a given finite set of partial words grows polynomially or exponentially with n.     

Parabolic equations with double variable nonlinearities

The paper is devoted to the study of the homogeneous Dirichlet problem for the doubly nonlinear parabolic equation with nonstandard growth conditions:

ut=div(a(x,t,u)|u^|α(x,t)|∇u^|p(x,t)−2∇u)+f(x,t)     

On stabilizers of infinite words

The stabilizer of an infinite word over a finite alphabet Σ is the monoid of morphisms over Σ that fix . In this paper we study various problems related to stabilizers and their generators. We show that over a binary alphabet, there exist stabilizers with at least n generators for all n. Over a ternary alphabet, the monoid of morphisms generating a given infinite word by iteration can be infinitely generated, even when the word is generated by iterating an invertible primitive morphism. Stabilizers of strict epistandard words are cyclic when non-trivial, while stabilizers of ultimately strict epistandard words are always non-trivial. For this latter family of words, we give a characterization of stabilizer elements.     

基于PDEs的图像平滑数值方法

对基于PDEs的图像平滑技术进行了探讨,在对四阶模型u/t=-▽² [c（|▽²u|）▽²u] 解的分析基础上,给出一种求解该模型的数值方法,数值实验结果给出了良好的去噪效果。     

On the structure of bispecial Sturmian words

A balanced word is one in which any two factors of the same length contain the same number of each letter of the alphabet up to one. Finite binary balanced words are called Sturmian words. A Sturmian word is bispecial if it can be extended to the left and to the right with both letters remaining a Sturmian word. There is a deep relation between bispecial Sturmian words and Christoffel words, that are the digital approximations of Euclidean segments in the plane. In 1997, J. Berstel and A. de Luca proved that palindromic bispecial Sturmian words are precisely the maximal internal factors of primitive Christoffel words. We extend this result by showing that bispecial Sturmian words are precisely the maximal internal factors of all Christoffel words. Our characterization allows us to give an enumerative formula for bispecial Sturmian words. We also investigate the minimal forbidden words for the language of Sturmian words.     

Rational chebyshev spectral methods for unbounded solutions on an infinite interval using polynomial-growth special basis functions

In the method of matched asymptotic expansions, one is often forced to compute solutions which grow as a polynomial in y as |y| → ∞. Similarly, the integral or repeated integral of a bounded function f(y) is generally unbounded also. The k^th integral of a function f(y) solves

. We describe a two-part algorithm for solving linear differential equations on y ϵ [−∞, ∞] where u(y) grows as a polynomial as |y| → ∞. First, perform an explicit, analytic transformation to a new unknown v so that v is bounded. Second, expand v as a rational Chebyshev series and apply a pseudospectral or Galerkin discretization. (For our examples, it is convenient to perform a preliminary step of splitting the problem into uncoupled equations for the parts of u which are symmetric and antisymmetric with respect to y = 0, but although this is very helpful when applicable, it is not necessary.) For the integral and interated integrals and for constant coefficient differential equations in general, the Galerkin matrices are banded with very low bandwidth. We derive an improvement on the “last coefficient error estimate” of the author's book which applies to series with a subgeometric rate of convergence, as is normally true of rational Chebyshev expansions.     

Monadic Thue systems

Certain infinite Thue systems over a finite alphabet are studied, in particular, systems $\text{S?∑}{}^1\text{×(∑∪{e})}$ such that for each a?∑∪{e}, the set {u| (u,a)?S} is a context-freelanguage. The syntactic structure of sets of ancestors and sets of descendants is considered, as well as that of unions of congruence classes, taken over (infinite) context-free languages or regular sets. The common descendant problem is shown to be tractable while the common ancestor problem is shown to be undecidable (even for finite systems). The word problem for confluent systems of this type is shown to be tractable. The question of whether an infinite system of this type is confluent is shown to be undecidable as is the question of whether the congruence generated by such a system has a confluent presentation.     

Pictures as Boolean Formulas

Both labellability and realizability problems of planar projections of polyhedra (i.e., pictures) are known to be NP-complete problems. This is true, even in the case of trihedral polyhedra, where exactly three faces meet at every vertex. In this paper, we examine pictures that are taken to be projections of trihedral polyhedra without holes, and contain the projections of all edges (hidden and visible) of a polyhedron. In other words, we examine pictures which represent the entire shape of a trihedral polyhedron without holes. Such a picture is a connected graph P=(V,E) with |E| edges and |V| nodes, each of degree 3 ( $|E| = \frac{3|V|}{2}$ ). We propose a mathematical scheme that constructs from the picture a Boolean formula Φ _P , which is a conjunction of clauses, each consisting of at most two literals. Based on the satisfiability of Φ _P , we show that both labellability and realizability problems can be solved efficiently in polynomial time. The category of pictures with hidden lines consists of the first category of pictures, where the labellability problem is solved in polynomial time, and, moreover, its solution implies the solution of the realizability problem in polynomial time too. Our approach may also prove useful in other applications of scene analysis.