1,721,095 research outputs found
Waring’s theorem for binary powers
Full text linkA natural number is a binary k’ th power if its binary representation consists of k consecutive identical blocks. We prove, using tools from combinatorics, linear algebra, and number theory, an analogue of Waring’s theorem for sums of binary k’th powers. More precisely, we show that for each integer k> 2, there exists an effectively computable natural number n such that every sufficiently large multiple of Ek:=gcd(2k - 1,k) is the sum of at most n binary k’th powers. (The hypothesis of being a multiple of Ek cannot be omitted, since we show that the gcd of the binary k’th powers is Ek.) Furthermore, we show that n = 2O(k3). Analogous results hold for arbitrary integer bases b>2
Rollercoasters: Long Sequences without Short Runs
No full textA rollercoaster is a sequence of real numbers for which every maximal contiguous subsequence---increasing or decreasing---has length at least three. By translating this sequence to a set of points in the plane, a rollercoaster can be defined as an ehBmonotone polygonal path for which every maximal subpath, with positive- or negative-slope edges, has at least three vertices. Given a sequence of distinct real numbers, the rollercoaster problem asks for a maximum-length (not necessarily contiguous) subsequence that is a rollercoaster. It was conjectured that every sequence of \lceil n/2\rceil, while the best known lower bound is . In this paper we prove this conjecture. Our proof is constructive and implies a linear-time algorithm for computing a rollercoaster of this length. Extending the (n\log n)ehBtime algorithm for computing a longest increasing subsequence, we show how to compute a maximum-length rollercoaster within the same time bound. A maximum-length rollercoaster in a permutation of can be computed in (n\log\log n)\frac{25}{3}(n+4). We also show that such a drawing can be obtained in linear time when the points are given in sorted order
Abelian-square-rich words
No full textAn abelian square is the concatenation of two words that are anagrams of one another. A word of length n can contain at most Θ(n2) distinct factors, and there exist words of length n containing Θ(n2) distinct abelian-square factors, that is, distinct factors that are abelian squares. This motivates us to study infinite words such that the number of distinct abelian-square factors of length n grows quadratically with n. More precisely, we say that an infinite word w is abelian-square-rich if, for every n, every factor of w of length n contains, on average, a number of distinct abelian-square factors that is quadratic in n; and uniformly abelian-square-rich if every factor of w contains a number of distinct abelian-square factors that is proportional to the square of its length. Of course, if a word is uniformly abelian-square-rich, then it is abelian-square-rich, but we show that the converse is not true in general. We prove that the Thue–Morse word is uniformly abelian-square-rich and that the function counting the number of distinct abelian-square factors of length 2n of the Thue–Morse word is 2-regular. As for Sturmian words, we prove that a Sturmian word sα of angle α is uniformly abelian-square-rich if and only if the irrational α has bounded partial quotients, that is, if and only if sα has bounded exponent
Properties of Two-Dimensional Words
No full textCombinatorics on words in one dimension is a well-studied subfield of theoretical computer science with its origins in the early 20th century. However, the closely-related study of two-dimensional words is not as popular, even though many results seem naturally extendable from the one-dimensional case. This thesis investigates various properties of these two-dimensional words.
In the early 1960s, Roger Lyndon and Marcel-Paul Schutzenberger developed two famous results on conditions where nontrivial prefixes and suffixes of a one-dimensional word are identical and on conditions where two one-dimensional words commute. Here, the theorems of Lyndon and Schutzenberger are extended in the one-dimensional case to include a number of additional equivalent conditions. One such condition is shown to be equivalent to the defect theorem from formal languages and coding theory. The same theorems of Lyndon and Schutzenberger are then generalized to the two-dimensional case.
The study of two-dimensional words continues by considering primitivity and periodicity in two dimensions, where a method is developed to enumerate two-dimensional primitive words. An efficient computer algorithm is presented to assist with checking the property of primitivity in two dimensions. Finally, borders in both one and two dimensions are considered, with some results being proved and others being offered as suggestions for future work. Another efficient algorithm is presented to assist with checking whether a two-dimensional word is bordered.
The thesis concludes with a selection of open problems and an appendix containing extensive data related to one such open problem
Proving Properties of Fibonacci Representations via Automata Theory
Full text linkIn this work, we introduce a novel framework for mechanically testing the completeness and unambiguity of Fibonacci-based representations via automata theory. We call a representation (or a number system) complete and unambiguous when it provides one and only one representation for each number in the range covered by the representation. Many commonly used representations are complete and unambiguous: consider the familiar binary number system—each natural number has a unique representation up to leading zeros. Additionally, if a representation is complete, we describe an algorithm, of O(log n)
complexity, to find a representation for any particular number n
Using Automata Theory to Solve Problems in Additive Number Theory
Full text linkAdditive number theory is the study of the additive properties of integers. Perhaps the best-known theorem is Lagrange’s result that every natural number is the sum of four squares. We study numbers whose base-k representations have certain interesting proper- ties. In particular, we look at palindromes, which are numbers whose base-k representations read the same forward and backward, and binary squares, which are numbers whose binary representation is some block repeated twice (like (36)_2 = 100100).
We show that all natural numbers are the sum of four binary palindromes. We also show that all natural numbers are the sum of three base-3 palindromes, and are also the sum of three base-4 palindromes. We also show that every sufficiently large natural number is the sum of four binary squares.
We establish these results using virtually no number theory at all. Instead, we construct automated proofs using automata. The general proof technique is to build an appropriate machine, and then run decision algorithms to establish our theorems
Counting, Adding, and Regular Languages
Full text linkIn this thesis we consider two mostly disjoint topics in formal language theory that both involve the study and use of regular languages.
The first topic lies in the intersection of automata theory and additive number theory. We introduce a method of producing results in additive number theory, relying on theorem-proving software and an approximation technique. As an example of the method, we prove that every natural number greater than 25 can be written as the sum of at most 3 natural numbers whose canonical base-2 representations have an equal number of 0's and 1's. We prove analogous results about similarly defined sets using the automata theory approach, but also give proofs using more "traditional" approaches.
The second topic is the study languages defined by criteria involving the number of occurrences of a particular pair of words within other words. That is, we consider languages of words z defined with respect to words x, y where z has the same number of occurrences (resp., fewer occurrences), (resp., fewer occurrences or the same number of occurrences) of x as a subword of z and y as a subword of z. We give a necessary and sufficient condition on when such languages are regular, and show how to check this condition efficiently.
We conclude by briefly considering ideas tying the two topics together
Decision Algorithms for Ostrowski-Automatic Sequences
Full text linkWe extend the notion of automatic sequences to a broader class, the Ostrowski-automatic sequences. We develop a procedure for computationally deciding certain combinatorial and enumeration questions about such sequences that can be expressed as predicates in first-order logic.
In Chapter 1, we begin with topics and ideas that are preliminary to this work, including a small introduction to non-standard positional numeration systems and the relationship between words and automata. In Chapter 2, we define the theoretical foundations for recognizing addition in a generalized Ostrowski numeration system and formalize the general theory that develops our decision procedure. Next, in Chapter 3, we show how to implement these ideas in practice, and provide the implementation as an integration to the automatic theorem-proving software package -- Walnut.
Further, we provide some applications of our work in Chapter 4. These applications span several topics in combinatorics on words, including repetitions, pattern-avoidance, critical exponents of special classes of words, properties of Lucas words, and so forth. Finally, we close with open problems on decidability and higher-order numeration systems and discuss future directions for research
Powers and Anti-Powers in Binary Words
Full text linkFici et al. recently introduced the notion of anti-powers in the context of combinatorics on words. A power (also called tandem repeat) is a sequence of consecutive identical blocks. An anti-power is a sequence of consecutive distinct blocks of the same length. Fici et al. showed that the existence of powers or anti-powers is an unavoidable regularity for sufficiently long words. In this thesis we explore this notion further in the context of binary words and obtain new results
Counting Flimsy Numbers via Formal Language Theory
Full text linkLet s_2(n) be the sum of the digits of n when expressed in base 2. For integers n and k, Stolarsky defined n to be k-flimsy if s_2(kn) < s_2(n). In this paper, we generalize the definition of k-flimsy numbers to all bases b, and provide a method to construct a pushdown automaton recognizing the k-flimsy base-b numbers. Using the tools of context-free languages and analytic combinatorics, we use this automaton to determine precise asymptotics for the number of k-flimsy N-digit numbers in base b. Lastly, using the results we obtained, we discuss the natural densities of k-flimsy numbers in base b for all values k and b.
Our main results can be found in Theorems 2, 3, 8, and 9
- …
