Search

Let t (n) denote the number of 1-bits in the base-2 representation of n , taken modulo 2. We show how to prove the classic conjecture of Leo Moser, on the rarefied sum ∑ 0 ≤ i < n (− 1) t (3 i) , using tools from automata theory and logic. The same technique can be used to prove results about analogous sums. [ABSTRACT FROM AUTHOR]

We investigate the size of the largest entry (in absolute value) in the inverse of certain Vandermonde matrices. More precisely, for every real b > 1 , let M b (n) be the maximum of the absolute values of the entries of the inverse of the n × n matrix [ b i j ] 0 ≤ i , j < n . We prove that lim n → + ∞ M b (n) exists, and we provide some formulas for it. [ABSTRACT FROM AUTHOR]

Given a finite alphabet Σ and a right-infinite word w over Σ, we define the Lie complexity function L w : N → N , whose value at n is the number of conjugacy classes (under cyclic shift) of length- n factors x of w with the property that every element of the conjugacy class appears in w. We show that the Lie complexity function is uniformly bounded for words with linear factor complexity. As a result, we show that words of linear factor complexity have at most finitely many primitive factors y with the property that y n is again a factor for every n. We then look at automatic sequences and show that the Lie complexity function of a k -automatic sequence is also k -automatic. [ABSTRACT FROM AUTHOR]

We study the properties of the uncountable set of Stewart words. These are Toeplitz words specified by infinite sequences of Toeplitz patterns of the form αβγ , where α , β , γ is any permutation of the symbols 0,1,?. We determine the critical exponent of the Stewart words, prove that they avoid the pattern x x y y x x , find all factors that are palindromes, and determine their subword complexity. An interesting aspect of our work is that we use automata-theoretic methods and a decision procedure for automata to carry out the proofs. [ABSTRACT FROM AUTHOR]

In this paper we consider a number of natural decision problems involving k -regular sequences. Specifically, they arise from considering • lower and upper bounds on growth rate; in particular boundedness, • images, • regularity (recognizability by a deterministic finite automaton) of preimages, and • factors, such as squares and palindromes, of such sequences. We show that these decision problems are undecidable. [ABSTRACT FROM AUTHOR]

We revisit the topic of power-free morphisms, focusing on the properties of the class of complementary morphisms. Such morphisms are defined over a 2-letter alphabet, and map the letters 0 and 1 to complementary words. We prove that every prefix of the famous Thue–Morse word t gives a complementary morphism that is 3 + -free and hence α -free for every real number α > 3. We also describe, using a 4-state binary finite automaton, the lengths of all prefixes of t that give cubefree complementary morphisms. Next, we show that 3-free (cubefree) complementary morphisms of length k exist for all k ∉ { 3 , 6 }. Moreover, if k is not of the form 3 ⋅ 2 n , then the images of letters can be chosen to be factors of t. Finally, we observe that each cubefree complementary morphism is also α -free for some α < 3 ; in contrast, no binary morphism that maps each letter to a word of length 3 (resp., a word of length 6) is α -free for any α < 3. In addition to more traditional techniques of combinatorics on words, we also rely on the Walnut theorem-prover. Its use and limitations are discussed. [ABSTRACT FROM AUTHOR]

Stern's diatomic series, denoted by (a (n)) n ≥ 0 , is defined by the recurrence relations a (2 n) = a (n) and a (2 n + 1) = a (n) + a (n + 1) for n ≥ 1 , with initial values a (0) = 0 and a (1) = 1. A record-setter for a sequence (s (n)) n ≥ 0 is an index v such that s (i) < s (v) holds for all i < v. In this paper, we provide a complete description of the record-setters for the Stern sequence. As a consequence, we prove that the running max sequence of the Stern sequence is not 2-regular. • Obtains a complete description of the record-setting maximum values of the Stern sequence. • Proves that the set of record-setters in binary form a context-free language. • Proves that the running max sequence is not a 2-regular sequence. [ABSTRACT FROM AUTHOR]

Venkatachala on the one hand, and Avdispahić & Zejnulahi on the other, both studied integer sequences with an unusual sum property defined in a greedy way, and proved many results about them. However, their proofs were rather lengthy and required numerous cases. In this paper, I provide a different approach, via finite automata, that can prove the same results (and more) in a simple, unified way. Instead of case analysis, we use a decision procedure implemented in the free software Walnut. Using these ideas, we can prove a conjecture of Quet and find connections between Quet's sequence and the "married" functions of Hofstadter. • Uses a new technique, automata theory, to prove properties of some greedily-defined integer sequences. • Finds much simpler proofs of some known results in the literature. • Finds a new connection between Quet's sequence and the Hofstadter married functions. [ABSTRACT FROM AUTHOR]

For a formal language L , the problem of language enumeration asks to compute the length-lexicographically smallest word in L larger than a given input w ∈ Σ ∗ (henceforth called the L -successor of w). We investigate this problem for regular languages from a computational complexity and state complexity perspective. We first show that if L is recognized by a DFA with n states, then 2 Θ (n log n) states are (in general) necessary and sufficient for an unambiguous finite-state transducer to compute L -successors. As a byproduct, we obtain that if L is recognized by a DFA with n states, then 2 Θ (n log n) states are sufficient for a DFA to recognize the subset S (L) of L composed of its lexicographically smallest words. We give a matching lower bound that holds even if S (L) is represented as an NFA. It has been known that L -successors can be computed in polynomial time, even if the regular language is given as part of the input (assuming a suitable representation of the language, such as a DFA). In this paper, we refine this result in multiple directions. We show that if the regular language is given as part of the input and encoded as a DFA, the problem is in N L. If the regular language L is fixed, we prove that the enumeration problem of the language is reducible to deciding membership to the Myhill-Nerode equivalence classes of L under D L O G T I M E -uniform A C 0 reductions. In particular, this implies that fixed star-free languages can be enumerated in A C 0 , arbitrary fixed regular languages can be enumerated in N C 1 and that there exist regular languages for which the problem is N C 1 -complete. [ABSTRACT FROM AUTHOR]

We show how some problems in additive number theory can be attacked in a novel way, using techniques from the theory of finite automata. We start by recalling the relationship between first-order logic and finite automata, and use this relationship to solve several problems involving sums of numbers defined by their base-2 and Fibonacci representations. Next, we turn to harder results. Recently, Cilleruelo, Luca, & Baxter proved, for all bases b ≥ 5, that every natural number is the sum of at most 3 natural numbers whose base-b representation is a palindrome (Cilleruelo et al., Math. Comput. 87, 3023–3055, 2018). However, the cases b = 2, 3, 4 were left unresolved. We prove that every natural number is the sum of at most 4 natural numbers whose base-2 representation is a palindrome. Here the constant 4 is optimal. We obtain similar results for bases 3 and 4, thus completely resolving the problem of palindromes as an additive basis. We consider some other variations on this problem, and prove similar results. We argue that heavily case-based proofs are a good signal that a decision procedure may help to automate the proof. [ABSTRACT FROM AUTHOR]

We begin a systematic study of the relations between subword complexity of infinite words and their power avoidance. Among other things, we show that – the Thue–Morse word has the minimum possible subword complexity over all overlap-free binary words and all (7 3) -power-free binary words, but not over all (7 3) + -power-free binary words; – the twisted Thue–Morse word has the maximum possible subword complexity over all overlap-free binary words, but no word has the maximum subword complexity over all (7 3) -power-free binary words; – if some word attains the minimum possible subword complexity over all square-free ternary words, then one such word is the ternary Thue word; – the recently constructed 1-2-bonacci word has the minimum possible subword complexity over all symmetric square-free ternary words. [ABSTRACT FROM AUTHOR]

Over an alphabet of size 3 we construct an infinite balanced word with critical exponent 2 + 2 / 2. Over an alphabet of size 4 we construct an infinite balanced word with critical exponent (5 + 5) / 4. Over larger alphabets, we give some candidates for balanced words (found computationally) having small critical exponents. We also explore a method for proving these results using the automated theorem prover Walnut. [ABSTRACT FROM AUTHOR]

We consider the real number σ with continued fraction expansion [a0, a1, a2,...]=[1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16,...], where ai is the largest power of 2 dividing i+1. We show that the irrationality measure of σ² is at least 8/3. We also show that certain partial quotients of σ² grow doubly exponentially, thus confirming a conjecture of Hanna and Wilson. [ABSTRACT FROM AUTHOR]

We consider a measure of similarity for infinite words that generalizes the usual number-theoretic notion of asymptotic or natural density for subsets of natural numbers. We show that every -power-free infinite binary word, other than the Thue-Morse word t and its complement , has this measure of similarity with t between and , and that this bound is optimal in a strong sense just for the class of overlap-free words. This is a generalization of a classical 1927 result of Kurt Mahler. [ABSTRACT FROM AUTHOR]

We generalize the familiar notion of periodicity in sequences to a new kind of pseudoperiodicity, and we prove some basic results about it. We revisit the results of a 2012 paper of Shevelev and reprove his results in a simpler and more unified manner, and provide a complete answer to one of his previously unresolved questions. We consider finding words with specific pseudoperiod and having the smallest possible critical exponent. Finally, we consider the problem of determining whether a finite word is pseudoperiodic of a given size, and show that it is NP-complete. [ABSTRACT FROM AUTHOR]

The notion of a -automatic set of integers is well-studied. We develop a new notion - the -automatic set of rational numbers - and prove basic properties of these sets, including closure properties and decidability. [ABSTRACT FROM AUTHOR]

A filtration of a formal language L by a sequence s maps L to the set of words formed by taking the letters of words of L indexed only by s. We consider the languages resulting from filtering by all arithmetic progressions. If L is regular, it is easy to see that only finitely many distinct languages result; we give bounds on the number of distinct languages in terms of the state complexity of L. By contrast, there exist CFL's that give infinitely many distinct languages as a result. We use our technique to show that two related operations, including diag (which extracts the diagonal of words of square length arranged in a square array), preserve regularity but do not preserve context-freeness. [ABSTRACT FROM AUTHOR]

The critical exponent of an infinite word is defined to be the supremum of the exponent of each of its factors. For k-automatic sequences, we show that this critical exponent is always either a rational number or infinite, and its value is computable. Our results also apply to variants of the critical exponent, such as the initial critical exponent of Berthé, Holton, and Zamboni and the Diophantine exponent of Adamczewski and Bugeaud. Our work generalizes or recovers previous results of Krieger and others, and is applicable to other situations; e.g., the computation of the optimal recurrence constant for a linearly recurrent k-automatic sequence. [ABSTRACT FROM AUTHOR]

Following up on a paper of Balamohan et al. [‘On the behavior of a variant of Hofstadter’s $q$-sequence’, J. Integer Seq. 10 (2007)], we analyze a variant of Hofstadter’s $Q$-sequence and show that its frequency sequence is 2-automatic. An automaton computing the sequence is explicitly given. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we answer the following question: what is the lexicographically least sequence over the natural numbers that avoids -powers? [Copyright &y& Elsevier]

In this paper we consider the computational complexity of the following problems: given a DFA or NFA representing a regular language L over a finite alphabet Σ, is the set of all prefixes (resp., suffixes, factors, subwords) of all words of L equal to Σ*? In the case of testing universality for factors of languages, there is a connection to two classic problems: the synchronizing words problem of Černý, and Restivo's conjecture on the minimal uncompletable word. [ABSTRACT FROM AUTHOR]

Abstract: Suppose that and let be the number of occurrences of the word in the binary expansion of . Let denote the Stern sequence, defined by , , and for , In this note, we show that where denotes the complement of (obtained by sending and ) and denotes the integer specified by the word interpreted in base . [Copyright &y& Elsevier]

Abstract: Let be the classical Thue–Morse sequence defined by , where is the sum of the bits in the binary representation of n. It is well known that for any integer the frequency of the letter “1” in the subsequence is asymptotically 1/2. Here we prove that for any k there is an such that . Moreover, we show that n can be chosen to have Hamming weight ⩽3. This is best in a twofold sense. First, there are infinitely many k such that implies that n has Hamming weight ⩾3. Second, we characterize all k where the minimal n equals k, , , , or . Finally, we present some results and conjectures for the generalized problem, where is replaced by for an arbitrary base . [Copyright &y& Elsevier]

Abstract: We examine decision problems for various classes of convex languages, previously studied by Ang and Brzozowski, originally under the name “continuous languages”. We can decide whether a language is prefix-, suffix-, factor-, or subword-convex in polynomial time if is represented by a DFA, but these problems become PSPACE-complete if is represented by an NFA. If a regular language is not convex, we find tight upper bounds on the length of the shortest words demonstrating this fact, in terms of the number of states of an accepting DFA. Similar results are proved for some subclasses of convex languages: the prefix-, suffix-, factor-, and subword-closed languages, and the prefix-, suffix-, factor-, and subword-free languages. Finally, we briefly examine these questions where is represented by a context-free grammar. [Copyright &y& Elsevier]

Let gj denote the largest integer that is represented exactly j times as a non-negative integer linear combination of { x1, . . . , xn}. We show that for any k > 0, and n == 5, the quantity g0 -- gk is unbounded. Furthermore, we provide examples with g0 > gk for n ≥≥ 6 and g0 > g1 for n ≥≥ 4. [ABSTRACT FROM AUTHOR]

Abstract: 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 , 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 , the word is the lexicographically least overlap-free word starting with the letter and ending with the letter , and give some of its symmetry properties. [Copyright &y& Elsevier]

Abstract: The cross-section enumeration problem is to list all words of length in a regular language in lexicographical order. The enumeration problem is to list the first words in according to radix order. We present an algorithm for the cross-section enumeration problem that is linear in , where is the output size. We provide a detailed analysis of the asymptotic running time of our algorithm and that of known algorithms for both enumeration problems. We discuss some shortcomings of the enumeration algorithm found in the Grail computation package. In the practical domain, we modify Mäkinen’s enumeration algorithm to get an algorithm that is usually the most efficient in practice. We performed an extensive performance analysis of the new and previously known enumeration and cross-section enumeration algorithms and found when each algorithm is preferable. [Copyright &y& Elsevier]

We prove that for every real number there exists an infinite word over a finite alphabet such that is the critical exponent of . [Copyright &y& Elsevier]

Abstract: 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 ; our construction is somewhat simpler than the original construction of Dekking. Second, we construct an infinite binary word avoiding all squares except , , and ; 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. [Copyright &y& Elsevier]

In 1976, Dekking showed that there exists an infinite binary word that contains neither squares yy with |y| ≥ 4 nor cubes xxx. We show that 'cube' can be replaced by any fractional power > 5/2. We also consider the analogous problem where '4' is replaced by any integer. This results in an interesting and subtle hierarchy. [ABSTRACT FROM AUTHOR]

We consider the properties of certain graphs based on iteration of the quadratic maps x→x2 and x→x2−2 over a finite field GF(p). [Copyright &y& Elsevier]

It is known that the number of overlap-free binary words of length n grows polynomially, while the number of cubefree binary words grows exponentially. We show that the dividing line between polynomial and exponential growth is 7/3. More precisely, there are only polynomially many binary words of length n that avoid 7/3-powers, but there are exponentially many binary words of length n that avoid 7/3. More precisely, there are only polynomially many binary words of length n that avoid 7/3-powers, but there are exponentially many binary words of length n that avoid 7/3 -powers, but there are exponentially many binary words of length n that avoid 7/3+-powers. This answers an open question of Kobayashi from 1986. [Copyright &y& Elsevier]

In this paper, we continue our study of k-regular sequences begun in 1992. We prove some new results, give many new examples from the literature, and state some open problems. [Copyright &y& Elsevier]

Presents solutions to the optimal denomination problem that minimizes the average cost of making change. Optimal dimensions for greedy change-making; Definition of optimal representation problem; Frobenius problem; Greedy algorithm.

It is well known that a context-free language defined over a one-letter alphabet is regular. This implies that unary context-free grammars and unary pushdown automata can be transformed into equivalent finite automata. In this paper, we study these transformations from a descriptional complexity point of view. In particular, we give optimal upper bounds for the number of states of nondeterministic and deterministic finite automata equivalent to unary context-free grammars in Chomsky normal form. These bounds are functions of the number of variables of the given grammars. We also give upper bounds for the number of states of finite automata simulating unary pushdown automata. As a main consequence, we are able to prove a log log n lower bound for the workspace used by one-way auxiliary pushdown automata in order to accept nonregular unary languages. The notion of space we consider is the so-called weak space concept. [Copyright &y& Elsevier]

In this paper we give the cost, in terms of states, of some basic operations (union, intersection, concatenation, and Kleene star) on regular languages in the unary case (where the alphabet contains only one symbol). These costs are given by explicitly determining the number of states in the noncyclic and cyclic parts of the resulting automata. Furthermore, we prove that our bounds are optimal. We also present an interesting connection to Jacobsthal′s function from number theory. [ABSTRACT FROM AUTHOR]

Discusses a mathematical problem on the decimal digits of prime inspired from a classical theorem in formal language theory. Background on the decimal digits of prime; Definition of 'repunits' and 'near-repunits'; Right- and left-truncatable primes; Notations representing strings of digits; Proofs of the theorems.

We generalize Axel Thue's familiar definition of overlaps in words, and observe that there are no infinite words avoiding split occurrences of these generalized overlaps. We give estimates for the length of the longest finite word that avoids split overlaps. Along the way we prove a useful theorem about repeated disjoint occurrences in words — an interesting natural variation on the classical de Bruijn sequences. [ABSTRACT FROM AUTHOR]

Describes a factoring machine invented by mathematician Eugene Olivier Carissan. Principles on which the machine was based; Sieving; Features of the machine; Brief biography of Carissan.

Investigates the social issues of networking in Canada's information society. Concerns on the detrimental effects of volumes of low-quality material distributed by the Internet; Examination of the interaction between the Canadian Charter of Rights and Freedoms and cyberspace; Impact of the internet on the rights enshrined in the charter.

First, we show that the sum-free set generated by the period-doubling sequence is not κ -regular for any κ ≥ 2. Next, we introduce a generalization of the period-doubling sequence, which we call the period- k -folding sequences. We show that the sum-free sets generated by the period- k -folding sequences also fail to be κ -regular for all κ ≥ 2. Finally, we study the sum-free sets generated by Sturmian sequences that begin with '11', and their difference sequences. [ABSTRACT FROM AUTHOR]

Abstract: Let be strings of equal length. The Hamming distance between and is the number of positions in which and differ. If is a cyclic shift of , we say and are conjugates. We consider , the Hamming distance between the conjugates and . Over a binary alphabet is always even, and must satisfy a further technical condition. By contrast, over an alphabet of size 3 or greater, can take any value between 0 and , except 1; furthermore, we can always assume that the smaller string has only one type of letter. [Copyright &y& Elsevier]

We prove an inequality for the number of periods in a word x in terms of the length of x and its initial critical exponent. Next, we characterize all periods of the length- n prefix of a characteristic Sturmian word in terms of the lazy Ostrowski representation of n , and use this result to show that our inequality is tight for infinitely many words x. We propose two related measures of periodicity for infinite words. Finally, we also consider special cases where x is overlap-free or squarefree. [ABSTRACT FROM AUTHOR]

We extend the notion of k -automatic sequences to Ostrowski-automatic sequences, and develop a procedure to computationally decide certain combinatorial and enumeration questions about such sequences that can be expressed as predicates in first-order logic. Our primary contribution is the design and implementation of an adder recognizing addition in a generalized Ostrowski numeration system. We also provide applications of our work to several topics in combinatorics on words, including repetitions and pattern avoidance. We partially resolve a previous conjecture about balanced words by Rampersad et al., and make the first progress on an open problem on rich words by Vesti. We also prove some known results about Lucas words using only machine computation. [ABSTRACT FROM AUTHOR]

We prove some new theorems in additive number theory, using novel techniques from automata theory and formal languages. As an example of our method, we prove that every natural number > 2 5 is the sum of at most three natural numbers whose base- 2 representation has an equal number of 0 's and 1 's. [ABSTRACT FROM AUTHOR]

We consider several language-theoretic aspects of various notions of unique decipherability (or unique factorization) in formal languages. Given a language L at some position within the Chomsky hierarchy, we investigate the language of words UD (L) in L ⁎ that have unique factorization over L. We also consider similar notions for weaker forms of unique decipherability, such as numerically decipherable words ND (L) , multiset decipherable words MSD (L) and set decipherable words SD (L). Although these notions of unique factorization have been considered before, it appears that the languages of words having these properties have not been positioned in the Chomsky hierarchy up until now. We show that UD (L) , ND (L) , MSD (L) and SD (L) need not be context-free if L is context-free. In fact ND (L) and MSD (L) need not be context-free even if L is finite, although UD (L) and SD (L) are regular in this case. We show that if L is context-sensitive, then so are UD (L) , ND (L) , MSD (L) and SD (L). We also prove that the membership problem (resp., emptiness problem) for these classes is PSPACE-complete (resp., undecidable). We finally determine upper and lower bounds on the length of the shortest word of L ⁎ not having the various forms of unique decipherability into elements of L. [ABSTRACT FROM AUTHOR]

We make certain bounds in Krebs' proof of Cobham's theorem explicit and obtain corresponding upper bounds on the length of a common prefix of an aperiodic a -automatic sequence and an aperiodic b -automatic sequence, where a and b are multiplicatively independent. We also show that an automatic sequence cannot have arbitrarily large factors in common with a Sturmian sequence. [ABSTRACT FROM AUTHOR]