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"”.

  1. 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 …

    waterloo Repository record for Deciding Properties of Automatic Sequences (opens in a new tab)

  2. 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 …

    waterloo Repository record for Decision Algorithms for Ostrowski-Automatic Sequences (opens in a new tab)

  3. 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 …

    waterloo Repository record for Automatic Sequences and Decidable Properties: Implementation and Applications (opens in a new tab)

  4. 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 …

    the-open-u Download PDF for Automatic sequences from algebraic, dynamical, and computational perspectives (opens in a new tab)

  5. 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 …

    waterloo Repository record for New Methods for Analyzing the Properties of Automatic Sequences (opens in a new tab)

  6. 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 …

    liege Repository record for Positional Numeration Systems: Ultimate Periodicity, Complexity and Automatic Sequences (opens in a new tab) Download PDF for Positional Numeration Systems: Ultimate Periodicity, Complexity and Automatic Sequences (opens in a new tab)

  7. 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 …

    lmu-germany Repository record for Distances and automatic sequences in distinguished variants of Hanoi graphs (opens in a new tab)

  8. 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 …

    waterloo Repository record for State Complexity of Linear Relations and Linear Subsequences of Automatic Sequences (opens in a new tab)

  9. 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 …

    the-open-u Download PDF for Forward Limit Sets of Semigroups of Substitutions and Arithmetic Progressions in Automatic Sequences (opens in a new tab)

  10. 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 …

    waterloo Repository record for Variations on the Erdos Discrepancy Problem (opens in a new tab)

  11. 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 …

    oxford Repository record for On combinatorial properties of nil-Bohr sets of integers and related problems (opens in a new tab)

  12. 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 …

    waterloo Repository record for Sparse Automatic Sets (opens in a new tab)

  13. 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 …

    liege Repository record for Extensions of the Pascal Triangle to Words, and Related Counting Problems (opens in a new tab) Download PDF for Extensions of the Pascal Triangle to Words, and Related Counting Problems (opens in a new tab)

  14. 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 …

    liege Repository record for Abstract Numeration Systems : Recognizability, Decidability, Multidimensional S-Automatic Words, and Real Numbers (opens in a new tab) Download PDF for Abstract Numeration Systems : Recognizability, Decidability, Multidimensional S-Automatic Words, and Real Numbers (opens in a new tab)