Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 14 of 14 for “"automatic sequences"”.
-
Deciding Properties of Automatic Sequences
… we show that several natural questions about automatic sequences can be expressed as logical predicates and then decided mechanically. We extend known results in this area to broader classes of sequences (e.g., paperfolding words), introduce new operations that extend the space of possible …
-
Decision Algorithms for Ostrowski-Automatic Sequences
We 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 …
-
Automatic Sequences and Decidable Properties: Implementation and Applications
… ayaya. Since then many interesting properties of sequences began to be discovered and studied. In this thesis, we consider a class of infinite sequences generated by automata, called the k-automatic sequences. In particular, we present a logical theory in which many properties of k-automatic …
-
Automatic sequences from algebraic, dynamical, and computational perspectives
We investigate some interesting properties of automatic sequences and other relative families of sequences using three broadly distinguished approaches: algebraic, dynamical, and computational. We consider the semigroup associated to a primitive substitution. We use it to construct a minimal …
-
New Methods for Analyzing the Properties of Automatic Sequences
Automatic sequences and morphic words lie at the intersection of automata theory, logic, and combinatorics on words. Many of their structural properties can be formulated as logical predicates over integer representations and decided using automata. This thesis presents automata-based methods for …
-
Positional Numeration Systems: Ultimate Periodicity, Complexity and Automatic Sequences
… recognizable sets through decision problems and automatic sequences. The first part is devoted to the following problem: given a numeration system U and a finite automaton accepting U-representations of a set X ⊆ N, can we decide whether the set X is ultimately periodic (i.e. a finite union of …
-
Distances and automatic sequences in distinguished variants of Hanoi graphs
… TH(K_3^-) are discussed concerning the infinite sequences of moves which arise from the solutions as n tends to infinity. The Allouche-Sapir Conjecture says that these sequences are not d-automatic for any d. I prove this for the TH(C_3^+) sequence with the aid of the frequency of a letter and …
-
State Complexity of Linear Relations and Linear Subsequences of Automatic Sequences
… We also study the state complexity of linear subsequences of automatic sequences; for example, we study the number of states required in the minimal automaton generating the linear subsequence $(h(i+c))_{i \geq 0}$ for some automatic sequences $(h(i))_{i \geq 0}$ and some constant integer $c \geq …
-
Forward Limit Sets of Semigroups of Substitutions and Arithmetic Progressions in Automatic Sequences
This thesis deals with symbolic sequences generated by semigroups of substitutions acting on finite alphabets. First, we investigate the underlying structure of certain automatic sequences by studying the maximum length A(d) of the monochromatic arithmetic progressions of difference d appearing in …
-
Variations on the Erdos Discrepancy Problem
… show that there are exactly two infinite {-1,1} sequences with discrepancy bounded by 1 and an uncountable number of in nite {-1,1} sequences with discrepancy bounded by 2. We also show that the number of {-1,1} sequences of length n with discrepancy bounded by 1 is 2^{s2(n)} where s2(n) is the …
-
On combinatorial properties of nil-Bohr sets of integers and related problems
… set. This leads to a partial characterisation of automatic sequences which are given by generalised polynomial formulas.</p> <p>In Chapter V, we estimate the Gowers norms of the Thue-Morse sequence and the Rudin-Shapiro sequence. This gives some of the simplest deterministic examples of sequences …
-
Sparse Automatic Sets
The theory of automatic sets and sequences arises naturally in many different areas of mathematics, notably in the study of algebraic power series in positive characteristic, due to work of Christol, and in Derksen's classification of zero sets for sequences satisfying a linear recurrence over …
-
Extensions of the Pascal Triangle to Words, and Related Counting Problems
… The second part is concerned with particular sequences extracted from generalized Pascal triangles. They count non-zeroes binomial coefficients on each row of a given Pascal-like triangle. We study their regularity and their automaticity with respect to different numeration systems. In the …
-
Abstract Numeration Systems : Recognizability, Decidability, Multidimensional S-Automatic Words, and Real Numbers
… of a result of A. Maes and M. Rigo regarding S-automatic infinite words. Finally, we propose a formalism to represent real numbers in the general framework of abstract numeration systems built on languages that are not necessarily regular. We end by a list of open questions in the continuation …