Search

This paper studies the average trapping time of honeypots on some evolving networks. We propose a simple algorithmic framework for generating networks with Sturmian structure. From the balance property and the recurrence property of Sturmian words, we estimate the average trapping time of our proposed networks with an asymptotic expression 〈 T 〉 t ∼ M t (α) 2 t , where M t (α) is a bounded expression related to word α ∈ { 0 , 1 } ∞ . We next consider networks with multi-honeypots and generalize our basic models. Additionally, we give an symmetrical method to create a series of networks with the Sturmian structure, and the average trapping time satisfies 〈 T 〉 t ∼ 5 × 2 t , which is independent of any word α. The generalized methods may have some illuminating effects on the study of networks with randomness. [ABSTRACT FROM AUTHOR]

We consider 1D discrete Schrödinger operators with aperiodic potentials given by a Sturmian word, which is a natural generalisation of the Fibonacci Hamiltonian. Via a standard approximation by periodic potentials, we establish Hausdorff convergence of the corresponding spectra for the Schrödinger operators on the axis as well as for their compressions to the halfaxis. Based on the half-axis results, we study the finite section method, which is another operator approximation, now by compressions to finite but growing intervals, that is often used to solve operator equations approximately. We find that, also for this purpose, the aperiodic case can be studied via its periodic approximants. Our results on the finite section method of the aperiodic operator are illustrated by confirming a result on the finite sections of the special case of the Fibonacci Hamiltonian. [ABSTRACT FROM AUTHOR]

We calculate the parity divisor functions associated to the ranks of the infinite monoletter word and to the Sturmian words and prove that there is a tilt of size proportional to log 2-1/2 towards the number of odd divisors. [ABSTRACT FROM AUTHOR]

Two finite words u and v are called abelian equivalent if each letter occurs equally many times in both u and v. The abelian closure A (x) of an infinite word x is the set of infinite words y such that, for each factor u of y , there exists a factor v of x which is abelian equivalent to u. The notion of an abelian closure gives a characterization of Sturmian words: among uniformly recurrent binary words, periodic and aperiodic Sturmian words are exactly those words for which A (x) equals the shift orbit closure Ω (x). In this paper, we investigate how this property extends to non-binary words. We consider the abelian closures of most natural generalizations of Sturmian words to non-binary alphabets, such as balanced words and minimal complexity words. We characterize the abelian closures of words in these families and show that in both families, there exist both words which satisfy the property A (x) = Ω (x) and which do not. We observe that for Arnoux-Rauzy words, we always have a strict inclusion Ω (x) ⊂ A (x). We also consider abelian closures of general subshifts and make some initial observations of their abelian closures and pose some related open questions. [ABSTRACT FROM AUTHOR]

We give asymptotic formulas for the number of balanced words whose slope α and intercept ρ lie in a prescribed rectangle. They are related to uniform distribution of Farey fractions and Riemann Hypothesis. In the general case, the error term is deduced using an inequality of large sieve type. [ABSTRACT FROM AUTHOR]

We discuss some seemingly unrelated observations on integers, whose close or far-ther away neighbors show a complex of combinatorial, ordering, arithmetical or probabilistic properties, emphasizing puzzlement in more common expectations. [ABSTRACT FROM AUTHOR]

• We present constructions of infinite prefix normal words. • We explore connections between infinite prefix normal words and other infinite words. • We study abelian complexity and infinite prefix normal words. • Prefix normal forms can be extended to infinite words. • We characterize Sturmian words which are prefix normal. Prefix normal words are binary words with the property that no factor has more 1s than the prefix of the same length. Finite prefix normal words were introduced in Fici and Lipták (2011) [18]. In this paper, we study infinite prefix normal words and explore their relationship to some known classes of infinite binary words. In particular, we establish a connection between prefix normal words and Sturmian words, between prefix normal words and abelian complexity, and between prefix normality and lexicographic order. 1 [ABSTRACT FROM AUTHOR]

The stable set associated to a given set S of nonerasing endomorphisms or substitutions is the set of all right infinite words that can be indefinitely desubstituted over S. This notion generalizes the notion of sets of fixed points of morphisms. It is linked to S -adicity and to property preserving morphisms. Two main questions are considered. Which known sets of infinite words are stable sets? Which ones are stable sets of a finite set of substitutions? While bringing answers to the previous questions, some new characterizations of several well-known sets of words such as the set of binary balanced words or the set of episturmian words are presented. A characterization of the set of nonerasing endomorphisms that preserve episturmian words is also provided. • The notion of stable sets formalizes an iterative desubstitution process. • Several well-known families of infinite words are stable sets but, sometimes, only for infinite sets of substitution. • The nonerasing endomorphisms that preserve episturmian words are characterized. [ABSTRACT FROM AUTHOR]

Fibonacci numbers are the basis of a new geometric construction that leads to the definition of a family { C n : n ∈ N } of octagons that come very close to the regular octagon. Such octagons, in some previous articles, have been given the name of Carboncettus octagons for historical reasons. Going further, in this paper we want to introduce and investigate some algebraic constructs that arise from the family { C n : n ∈ N } and therefore from Fibonacci numbers: From each Carboncettus octagon C n , it is possible to obtain an infinite (right) word W n on the binary alphabet { 0 , 1 } , which we will call the nth Carboncettus word. The main theorem shows that all the Carboncettus words thus defined are Sturmian words except in the case n = 5 . The fifth Carboncettus word W 5 is in fact the only word of the family to be purely periodic: It has period 17 and periodic factor 000 100 100 010 010 01. Finally, we also define a further word W ∞ named the Carboncettus limit word and, as second main result, we prove that the limit of the sequence of Carboncettus words is W ∞ itself. [ABSTRACT FROM AUTHOR]

The paper provides a criterion for substitutivity of symmetric Sturmian words infinite on both sides and its proof, and a theorem on the substitutivity of factor dynamics of circle rotations. [ABSTRACT FROM AUTHOR]

This paper focuses on generalized pseudostandard words, defined by de Luca and De Luca in 2006. In every step of the construction, the involutory antimorphism to be applied for the pseudopalindromic closure changes and is given by a so called directive bi-sequence. The concept of a normalized form of directive bi-sequences was introduced by Blondin-Massé et al. in 2013 and an algorithm for finding the normalized directive bi-sequence over a binary alphabet was provided. In this paper, we present an algorithm to find the normalized form of any directive bi-sequence over a ternary alphabet. Moreover, the algorithm was implemented in Python language and carefully tested, and is now publicly available in a module for working with ternary generalized pseudostandard words. [ABSTRACT FROM AUTHOR]

Given an infinite word x = x0x1x2 · · · ∈ AN over some finite alphabet A, the factor complexity px(n) counts the number of distinct factors of x of each given length n, i.e., the number of distinct blocks xixi+1 · · · xi+n−1 ∈ An occurring in x. The factor complexity provides a useful measure of the extent of randomness of x: periodic words have bounded factor complexity while digit expansions of normal numbers have maximal complexity. In this paper we obtain a new characterization of infinite words x of sublinear complexity, namely we show that px(n) = O(n) if and only if there exists a set S ⊆ A∗ of bounded complexity (meaning lim sup pS(n) < +∞) such that each factor w of x is a concatenation of two elements of S, i.e., w = uv with u, v ∈ S. In the process we introduce the notions of marker words and marker sets which are both new and may be of independent interest. Marker sets defined by right special factors constitute the key tool needed to split each factor of an infinite word of linear complexity into two pieces. [ABSTRACT FROM AUTHOR]

The trade-off between the cost of acquiring and processing data, and uncertainty due to a lack of data is fundamental in machine learning. A basic instance of this trade-off is the problem of deciding when to make noisy and costly observations of a discrete-time Gaussian random walk, so as to minimise the posterior variance plus observation costs. We present the first proof that a simple policy, which observes when the posterior variance exceeds a threshold, is optimal for this problem. The proof generalises to a wide range of cost functions other than the posterior variance. It is based on a new verification theorem by Ni~no-Mora that guarantees threshold structure for Markov decision processes, and on the relation between binary sequences known as Christoffel words and the dynamics of discontinuous nonlinear maps, which frequently arise in physics, control and biology. This result implies that optimal policies for linear-quadratic-Gaussian control with costly observations have a threshold structure. It also implies that the restless bandit problem of observing multiple such time series, has a well-defined Whittle index policy. We discuss computation of that index, give closed-form formulae for it, and compare the performance of the associated index policy with heuristic policies. [ABSTRACT FROM AUTHOR]

We determine the classical exponents of approximation w 3 ( ζ ) , w 3 ⁎ ( ζ ) , λ 3 ( ζ ) and w ˆ 3 ( ζ ) , w ˆ 3 ⁎ ( ζ ) , λ ˆ 3 ( ζ ) associated to real numbers ζ whose continued fraction expansions are given by a Sturmian word. We more generally provide a description of the combined graph of the parametric successive minima functions defined by Schmidt and Summerer in dimension three for such Sturmian continued fractions. This both complements similar results due to Bugeaud and Laurent concerning the two-dimensional exponents and generalizes a recent result of the author. As a side result we obtain new information on the spectra of the above exponents. Moreover, we provide some information on the exponents λ n ( ζ ) for a Sturmian continued fraction ζ and arbitrary n . [ABSTRACT FROM AUTHOR]

We prove that if a Sturmian word is the image by a morphism of a word which is a fixed point of another morphism, then this latter word is mostly a Sturmian word, and the involved morphisms are Sturmian. This gives a characterization of Sturmian words that are generated by HD0L systems. We also characterize the non Sturmian words which can be sent on Sturmian words by morphism, and the involved morphisms. We prove that the same Sturmian images can be obtained by using the standard morphisms of which the above morphisms are the conjugates, and we show how to obtain these Sturmian morphisms from their standard representatives. [ABSTRACT FROM AUTHOR]

In this paper we give a broad unified framework via group actions for constructing complexity functions of infinite words x = x0x1x2 ⋯ ∈ Aℕ with values in a finite set A. Factor complexity, Abelian complexity and cyclic complexity are all particular cases of this general construction. We consider infinite sequences of permutation groups w = (Gn)n≥1 with each Gn ⊆ Sn. Associated with every such sequence is a complexity function pw,x : ℕ → ℕ which counts, for each length n, the number of equivalence classes of factors of x of length n under the action of Gn on An given by g * (u1u2 ⋯ un) = ug-1(1)ug-1(2) ⋯ ug-1(n). Each choice of w = (Gn)n≥1 defines a unique complexity function which reflects a different combinatorial property of a given infinite word. For instance, an infinite word x has bounded Abelian complexity if and only if x is k-balanced for some positive integer k, while bounded cyclic complexity is equivalent to x being ultimately periodic. A celebrated result of G.A. Hedlund and M. Morse states that every aperiodic infinite word x ∈ Aℕ contains at least n + 1 distinct factors of each length n. Moreover x ∈ Aℕ has exactly n + 1 distinct factors of each length n if and only if x is a Sturmian word, i.e., binary, aperiodic and balanced. We prove that this characterisation of aperiodicity and Sturmian words extends to this general framework. [ABSTRACT FROM AUTHOR]

We introduce and study a complexity function on words c x ( n ) , called cyclic complexity , which counts the number of conjugacy classes of factors of length n of an infinite word x . We extend the well-known Morse–Hedlund theorem to the setting of cyclic complexity by showing that a word is ultimately periodic if and only if it has bounded cyclic complexity. Unlike most complexity functions, cyclic complexity distinguishes between Sturmian words of different slopes. We prove that if x is a Sturmian word and y is a word having the same cyclic complexity of x , then up to renaming letters, x and y have the same set of factors. In particular, y is also Sturmian of slope equal to that of x . Since c x ( n ) = 1 for some n ≥ 1 implies x is periodic, it is natural to consider the quantity lim inf n → ∞ c x ( n ) . We show that if x is a Sturmian word, then lim inf n → ∞ c x ( n ) = 2 . We prove however that this is not a characterization of Sturmian words by exhibiting a restricted class of Toeplitz words, including the period-doubling word, which also verify this same condition on the limit infimum. In contrast we show that, for the Thue–Morse word t , lim inf n → ∞ c t ( n ) = + ∞ . [ABSTRACT FROM AUTHOR]

Given a finite coloring (or finite partition) of the free semigroup A + over a set A , we consider various types of monochromatic factorizations of right sided infinite words x ∈ A ω . Some stronger versions of the usual notion of monochromatic factorization are introduced. A factorization is called sequentially monochromatic when concatenations of consecutive blocks are monochromatic. A sequentially monochromatic factorization is called ultra monochromatic if any concatenation of arbitrary permuted blocks of the factorization has the same color of the single blocks. We establish links, and in some cases equivalences, between the existence of these factorizations and fundamental results in Ramsey theory including the infinite Ramsey theorem, Hindman's finite sums theorem, partition regularity of IP sets and the Milliken–Taylor theorem. We prove that for each finite set A and each finite coloring φ : A + → C , for almost all words x ∈ A ω , there exists y in the subshift generated by x admitting a φ -ultra monochromatic factorization, where “almost all” refers to the Bernoulli measure on A ω . [ABSTRACT FROM AUTHOR]

This paper continues the study initiated by Alex Heinis of the set H of pairs (α, β) obtained as the lower and upper limit of the ratio of complexity and length for an infinite word. Heinis proved that this set contains no point under a certain curve. We extend this result by proving that there are only three points on this curve, namely (1, 1), (3/2, 5/3) and (2, 2), and moreover the point (3/2, 5/3) is an isolated point in the set H. For this, we use Rauzy graphs, generalizing techniques of Ali Aberkane. [ABSTRACT FROM AUTHOR]

The binomial coefficient of two words u and v is the number of times v occurs as a subsequence of u . Based on this classical notion, we introduce the m -binomial equivalence of two words refining the abelian equivalence. Two words x and y are m -binomially equivalent, if, for all words v of length at most m , the binomial coefficients of x and v and respectively, y and v are equal. The m -binomial complexity of an infinite word x maps an integer n to the number of m -binomial equivalence classes of factors of length n occurring in x . We study the first properties of m -binomial equivalence. We compute the m -binomial complexity of two classes of words: Sturmian words and (pure) morphic words that are fixed points of Parikh-constant morphisms like the Thue–Morse word, i.e., images by the morphism of all the letters have the same Parikh vector. We prove that the frequency of each symbol of an infinite recurrent word with bounded 2-binomial complexity is rational. [ABSTRACT FROM AUTHOR]

We regard a finite word u = u 1 u 2 ⋯ u n up to word isomorphism as an equivalence relation on { 1 , 2 , … , n } where i is equivalent to j if and only if u i = u j . Some finite words (in particular all binary words) are generated by palindromic relations of the form k ∼ j + i − k for some choice of 1 ≤ i ≤ j ≤ n and k ∈ { i , i + 1 , … , j } . That is to say, some finite words u are uniquely determined up to word isomorphism by the position and length of some of its palindromic factors. In this paper we study the function μ ( u ) defined as the least number of palindromic relations required to generate u . We show that if x is an infinite word such that μ ( u ) ≤ 2 for each factor u of x , then x is ultimately periodic. On the other hand, we establish the existence of non-ultimately periodic words for which μ ( u ) ≤ 3 for each factor u of x , and obtain a complete classification of such words on a binary alphabet (which includes the well known class of Sturmian words). In contrast, for the Thue–Morse word, we show that the function μ is unbounded. [ABSTRACT FROM AUTHOR]

In this paper we introduce and study a new property of infinite words: An infinite word x ∈ A N , with values in a finite set A , is said to be k - self-shuffling ( k ≥ 2 ) if x admits factorizations: x = ∏ i = 0 ∞ U i ( 1 ) ⋯ U i ( k ) = ∏ i = 0 ∞ U i ( 1 ) = ⋯ = ∏ i = 0 ∞ U i ( k ) . In other words, there exists a shuffle of k -copies of x which produces x . We are particularly interested in the case k = 2 , in which case we say x is self-shuffling. This property of infinite words is shown to be independent of the complexity of the word as measured by the number of distinct factors of each length. Examples exist from bounded to full complexity. It is also an intrinsic property of the word and not of its language (set of factors). For instance, every aperiodic word contains a non-self-shuffling word in its shift orbit closure. While the property of being self-shuffling is a relatively strong condition, many important words arising in the area of symbolic dynamics are verified to be self-shuffling. They include for instance the Thue–Morse word fixed by the morphism 0 ↦ 01 , 1 ↦ 10 . As another example we show that all Sturmian words of slope α ∈ R ∖ Q and intercept 0 < ρ < 1 are self-shuffling (while those of intercept ρ = 0 are not). Our characterization of self-shuffling Sturmian words can be interpreted arithmetically in terms of a dynamical embedding and defines an arithmetic process we call the stepping stone model . One important feature of self-shuffling words stems from their morphic invariance: The morphic image of a self-shuffling word is self-shuffling. This provides a useful tool for showing that one word is not the morphic image of another. In addition to its morphic invariance, this new notion has other unexpected applications particularly in the area of substitutive dynamical systems. For example, as a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, on a classification of pure morphic Sturmian words in the orbit of the characteristic. [ABSTRACT FROM AUTHOR]

We consider binary rotation words generated by partitions of the unit circle to two intervals and give a precise formula for the number of such words of length n. We also give the precise asymptotics for it, which happens to be Θ(n4). The result continues the line initiated by the formula for the number of all Sturmian words obtained by Lipatov [Problemy Kibernet. 39 (1982) 67–84], then independently by Mignosi [Theoret. Comput. Sci. 82 (1991) 71–84], and others. [ABSTRACT FROM PUBLISHER]

A word w is rich if it has |w| + 1 many distinct palindromic factors, including the empty word. This article contains several results about rich words, particularly related to extending them. A word w can be eventually extended richly in n ways if there exists a finite word u and n distinct letters a ∈ Alph (w) such that wua is rich. We will prove that every (non-unary) rich word can be eventually extended richly in at least two different ways, but not always in three or more ways. We will also prove that every rich word can be extended to both periodic and aperiodic infinite rich words. The defect of a finite word w is defined by D (w) = |w| + 1 - |Pal(w)|. This concept has been studied in various papers. Here, we will define a new concept, infinite defect. For a finite word w the definition is D ∞ (w) = min {D(z)|z is an infinite word which has factorw}. We will show that the infinite defect of a finite word is always finite and give some upper bounds for it. The difference between defect and infinite defect is also investigated. We will also give an upper and a lower bound for the number of rich words. A new class of words, two-dimensional rich words, is also introduced. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we consider the following question in the spirit of Ramsey theory: Given , where A is a finite non-empty set, does there exist a finite coloring of the non-empty factors of x with the property that no factorization of x is monochromatic? We prove that this question has a positive answer using two colors for almost all words relative to the standard Bernoulli measure on . We also show that it has a positive answer for various classes of uniformly recurrent words, including all aperiodic balanced words, and all words satisfying for all n sufficiently large, where denotes the number of distinct factors of x of length n. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

This paper is concerned with the analysis of the worst case behavior of Hopcroft's algorithm for minimizing deterministic finite state automata. We extend a result of Castiglione, Restivo and Sciortino. They show that Hopcroft's algorithm has a worst case behavior for the automata recognizing Fibonacci words. We prove that the same holds for all standard Sturmian words having an ultimately periodic directive sequence (the directive sequence for Fibonacci words is $(1,1,\ldots)$).

Abstract: In this paper we introduce and study a family of complexity functions of infinite words indexed by . Let and A be a finite non-empty set. Two finite words u and v in are said to be k-Abelian equivalent if for all of length less than or equal to k, the number of occurrences of x in u is equal to the number of occurrences of x in v. This defines a family of equivalence relations on , bridging the gap between the usual notion of Abelian equivalence (when ) and equality (when ). We show that the number of k-Abelian equivalence classes of words of length n grows polynomially, although the degree is exponential in k. Given an infinite word , we consider the associated complexity function which counts the number of k-Abelian equivalence classes of factors of ω of length n. We show that the complexity function is intimately linked with periodicity. More precisely we define an auxiliary function and show that if for some and , then ω is ultimately periodic. Moreover if ω is aperiodic, then if and only if ω is Sturmian. We also study k-Abelian complexity in connection with repetitions in words. Using Szemerédiʼs theorem, we show that if ω has bounded k-Abelian complexity, then for every with positive upper density and for every positive integer N, there exists a k-Abelian N-power occurring in ω at some position . [Copyright &y& Elsevier]

Abstract: In this paper we introduce a new class of so-called privileged words which have been previously considered only a little. We develop the basic properties of privileged words, which turn out to share similar properties with palindromes. Privileged words are studied in relation to previously studied classes of words, rich words, Sturmian words and episturmian words. A new characterization of Sturmian words is given in terms of privileged complexity. The privileged complexity of the Thue–Morse word is also briefly studied. [Copyright &y& Elsevier]

We prove that the Fibonacci word f satisfies among all characteristic Sturmian words, three interesting extremal properties. The first concerns the length and the second the minimal period of its palindromic prefixes. Each of these two properties characterizes f up to a renaming of its letters. A third property concerns the number of occurrences of the letter b in its palindromic prefixes. It characterizes uniquely f among all characteristic Sturmian words having the prefix abaa. [ABSTRACT FROM AUTHOR]

This overview paper is devoted to Sturmian words. The first part summarizes different characterizations of Sturmian words. Besides the well known theorem of Hedlund and Morse it also includes recent results on the characterization of Sturmian words using return words or palindromes. The second part deals with substitution invariant Sturmian words, where we present our recent results. We generalize one-sided Sturmian words using the cut-and-project scheme and give a full characterization of substitution invariant Sturmian words.

We define an infinite permutation as a sequence of reals taken up to the order, or, equivalently, as a linear ordering of a finite or countable set. Then we introduce and characterize periodic permutations; surprisingly, for each period $t$ there is an infinite number of distinct $t$-periodic permutations. At last, we introduce a complexity notion for permutations analogous to subword complexity for words, and consider the problem of minimal complexity of non-periodic permutations. Its answer is different for the right infinite and the bi-infinite case.