Search

The (bitwise) complement x of a binary word x is obtained by changing each 0 in x to 1 and vice versa. An antisquare is a nonempty word of the form x x. In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is (5 +√5)/2. We also study repetition thresholds for related classes, where "two" in the previous sentence is replaced by a larger number. We say a binary word is good if the only antisquares it contains are 01 and 10. We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the growth rate of the number of good words of length n and determine the repetition threshold between polynomial and exponential growth for the number of good words. [ABSTRACT FROM AUTHOR]

A simple scheme was proposed by Knuth to generate binary balanced codewords from any information word. However, this method is limited in the sense that its redundancy is twice that of the full sets of balanced codes. The gap between Knuth's algorithm's redundancy and that of the full sets of balanced codes is significantly considerable. This paper attempts to reduce that gap. Furthermore, many constructions assume that a full balancing can be performed without showing the steps. A full balancing refers to the overall balancing of the encoded information together with the prefix. We propose an efficient way to perform a full balancing scheme that does not make use of lookup tables or enumerative coding. [ABSTRACT FROM AUTHOR]

Let F k be the family of the binary words containing exactly k 0s. Ilić, Klavžar and Rho constructed an infinite subfamily of 2-isometric but not 3-isometric words among F 2. Wei, Yang and Wang further found there are 2-isometric but not 3-isometric words among F k for all k ∈ { 2 , 5 , 6 } and k ≥ 8 , and they conjectured that F 1 , F 3 , F 4 and F 7 are the only families in which there are not 2-isometric but not 3-isometric words. In the present paper, we show that this conjecture is true, and find all the 2-isometric words among F 5 and F 6. [ABSTRACT FROM AUTHOR]

Sets of finite words, as well as some infinite ones, can be described using finite systems, e.g. automata. On the other hand, some automata may be constructed with the use of even more compact systems, like Petri nets. We call such automata Petri net solvable. In this paper we consider the solvability of singleton languages over a binary alphabet (i.e. binary words). An unsolvable (i.e. not solvable) word w is called minimal if each proper factor of w is solvable. We present a complete language-theoretical characterisation of the set of all minimal unsolvable binary words. The characterisation utilises morphic-based transformations which expose the combinatorial structure of those words, and allows to introduce a pattern matching condition for unsolvability. [ABSTRACT FROM AUTHOR]

We consider words over a binary alphabet. A word w is overlap-free if it does not have factors (blocks of consecutive letters) of the form u v u v u for nonempty u. Let M (w) denote the number of positions that are middle positions of squares (of the form u u) in w. We show that for overlap-free binary words, 2 M (w) ≤ | w | + 3 , and that there are infinitely many overlap-free binary words for which 2 M (w) = | w | + 3. [ABSTRACT FROM AUTHOR]

Let F k be the family of the binary words containing the letter 0 exactly k times. Ilić, Klavžar and Rho constructed an infinite subfamily of 2-isometric and not 3-isometric words in F 2 . Wei and Zhang further found all such words in F 2 . In this paper we find that there exists no 2-isometric and not 3-isometric word in F 3 . For k ≠ 1 , 3 , 4 and 7, we also construct an infinite subfamily of 2-isometric and not 3-isometric words in F k . Based on those results and computer experiments, we conjecture that F 1 , F 3 , F 4 and F 7 are the only families in which there exists no 2-isometric and not 3-isometric word. [ABSTRACT FROM AUTHOR]

Abstract: The gap function of an infinite word over the binary alphabet gives the distances between consecutive 1''s in this word. In this paper we study infinite binary words whose gap function is injective or “almost injective.” A method for computing the subword complexity of such words is given. A necessary and sufficient condition for a function to be the subword complexity function of a binary word whose gap function is increasing is obtained. [Copyright &y& Elsevier]

We consider the numerical characteristics of identities of nonassociative algebras and propose a method for constructing some algebra A(w) with prescribed properties of the codimension growth function. The growth of codimensions of A(w) is completely determined by the combinatorial complexity of the language of subwords of w. [ABSTRACT FROM AUTHOR]

The authors propose and analyze the optical signal processing functionality of periodic structures consisting of alternating layers of materials possessing different Kerr nonlinearities. They explore structure-materials-performance relationships in all-optical analog-to-digital converters, hardlimiters, and AND and OR gates. They show that their proposed analog-to-digital converters can extract a binary word from multilevel optical signals in a single bit interval. They also propose a family of optical limiters whose output signal clamps to a set upper logic level for any input value exceeding a chosen threshold. They explore the performance of an all-optical logic gate whose forward-directed output implements a binary AND and whose backward-directed output implements an OR function [ABSTRACT FROM PUBLISHER]