The ring of $k$-regular sequences

DOI10.1016/0304-3975(92)90001-VzbMath0774.68072OpenAlexW4210391712WikidataQ59663516 ScholiaQ59663516MaRDI QIDQ1193879

Jean-Paul Allouche, Jeffrey O. Shallit

Publication date: 27 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90001-v

zbMATH Keywords

Fourier expansion closure properties formal power series automatic sequence $k$-regular sequences pattern sequence $\mathbb{Z}$-rational formal series

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Valuations, completions, formal power series and related constructions (associative rings and algebras) (16W60) Special sequences and polynomials (11B83) Automata sequences (11B85)

Related Items

Abelian-square-rich words, On formal inverse of the Prouhet-Thue-Morse sequence, Canonical positions for the factors in paperfolding sequences, Growth degree classification for finitely generated semigroups of integer matrices, Mellin transforms and asymptotics. The mergesort recurrence, Spectral theory of regular sequences, Synchronized sequences, Nilpotence order growth of recursion operators in characteristic $p$, Stern polynomials, On congruence schemes for constant terms and their applications, THE MINIMAL GROWTH OF A -REGULAR SEQUENCE, Asymptotic analysis of $q$-recursive sequences, Automatic sequences as good weights for ergodic theorems, Summation of series defined by counting blocks of digits, The 2-adic valuation of generalized Fibonacci sequences with an application to certain Diophantine equations, Generalized Lucas congruences and linear $p$-schemes, Linear cellular automata, finite automata and Pascal's triangle, Algorithmic classification of noncorrelated binary pattern sequences, Asymptotics of Mahler recurrences: The cyclotomic case, Morphisms on infinite alphabets, countable states automata and regular sequences, On the abelian complexity of the Rudin-Shapiro sequence, Automaticity of double sequences generated by one-dimensional linear cellular automata, On the number of hypercubic bipartitions of an integer, Separators in infinite words generated by morphisms., On Lindenmayerian algebraic sequences, On the regularity of $\{\lfloor \log_b(\alpha n+\beta)\rfloor\}_{n\geq 0}$, Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: algebraic and analytic approaches collated, Path sets in one-sided symbolic dynamics, On the $k$-abelian complexity of the Cantor sequence, A pattern sequence approach to Stern's sequence, Avoiding 3/2-powers over the natural numbers, On factors of synchronized sequences, Joint spectral radius, dilation equations, and asymptotic behavior of radix-rational sequences, Avoiding 5/4-powers on the alphabet of nonnegative integers, Properties and limits of recognition of sets of integers by countable automata, On the permutation complexity of the Cantor-like sequences, Patterns in numbers and infinite sums and products, Analytic functions over $\mathbb Z_p$ and $p$-regular sequences, On a family of 2-automatic sequences generating algebraic continued fractions in characteristic 2, Number Theoretic Aspects of Regular Sequences, First-Order Logic and Numeration Systems, On the k-regularity of the k-adic valuation of Lucas sequences, Cobham's theorem for substitutions, Affinely recursive sets and orderings of languages., Unnamed Item, The ring of $k$-regular sequences. II., On some questions regarding $k$-regular and $k$-context-free sequences, Exact asymptotics of divide-and-conquer recurrences, Continuants, run lengths, and Barry's modified Pascal triangle, Automatic Dirichlet series, $p$-adic valuations and $k$-regular sequences, On the regularity of the Hankel determinant sequence of the characteristic sequence of powers of 2, Quasi-universal $k$-regular sequences, On the vector space of the automatic reals, Subword complexity of a generalized Thue-Morse word, On the 2-abelian complexity of the Thue-Morse word, Criteria for regularity of Mahler power series and Becker's conjecture, Profinite automata, Automatic maps in exotic numeration systems, The maximal order of hyper-($b$-ary)-expansions, Unnamed Item, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Behavior of digital sequences through exotic numeration systems, Avoiding fractional powers over the natural numbers, A new approach to the 2-regularity of the $\ell$-abelian complexity of 2-automatic sequences, Sequences of linear arithmetical complexity, Self-generating sets, integers with missing blocks, and substitutions, Metric properties of the Tower of Hanoi graphs and Stern's diatomic sequence, Robustness of Pisot-regular sequences, An unusual continued fraction, Divisibility of binomial coefficients by powers of two, Morphic words and equidistributed sequences, Minimal automaton for multiplying and translating the Thue-Morse set, Asymptotic analysis of regular sequences, On some conjectures of P. Barry, Automaticity of the Hankel determinants of difference sequences of the Thue-Morse sequence, Proof of Northshield's conjecture concerning an analogue of Stern's sequence for $\mathbb{Z}[\sqrt{2}$], ON THE REPETITIVITY INDEX OF INFINITE WORDS, A diffraction abstraction, Revisiting regular sequences in light of rational base numeration systems, Regular sequences and synchronized sequences in abstract numeration systems, On the complexity of a family of $k$-context-free sequences, Composition inverses of the variations of the Baum-Sweet sequence, Sum-free sets generated by the period-$k$-folding sequences and some Sturmian sequences, Decidability and $k$-regular sequences, Transcendence of formal power series with rational coefficients, Avoiding squares and overlaps over the natural numbers, On the values attained by a $k$-regular sequence, On the 2-abelian complexity of generalized Cantor sequences, Squares and overlaps in the Thue-Morse sequence and some variants, Unnamed Item, Algebraic independence of the power series defined by blocks of digits, Palindrome complexity., A POLYNOMIAL ANALOGUE TO THE STERN SEQUENCE, 2- and 3-Mahler recurrences, Polynomial subsequences of certain automatic sequences, Mellin transforms and asymptotics: Digital sums, On the regular sum-free sets, On synchronized sequences and their separators, Automatic congruences for diagonals of rational functions, Prefix palindromic length of the Thue-Morse word, A sequential view of self--similar measures, or, What the ghosts of Mahler and Cantor can teach us about dimension, Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus, A More Malicious Maitre d’, Interview with Jeffrey Shallit, The binary digits of n+t, Bracket words: A generalisation of Sturmian words arising from generalised polynomials, Magic Numbers in Periodic Sequences, Dyck Words, Pattern Avoidance, and Automatic Sequences, ZAREMBA, SALEM AND THE FRACTAL NATURE OF GHOST DISTRIBUTIONS, A note on the relation between recognisable series and regular sequences, and their minimal linear representations, On $k$-regularity of sequences of valuations and last non-zero digits, Fast coefficient computation for algebraic power series in positive characteristic, Diophantine approximations. Abstracts from the workshop held April 17--23, 2022, Values of binary partition function represented by a sum of three squares, A height gap theorem for coefficients of Mahler functions, Record-setters in the Stern sequence, Algebraic aspects of B-regular series, From Combinatorial Games to Shape-Symmetric Morphisms, A natural probability measure derived from Stern’s diatomic sequence, ENUMERATION AND DECIDABLE PROPERTIES OF AUTOMATIC SEQUENCES, The Ghost Measures of Affine Regular Sequences, Unnamed Item, A Final Coalgebra for k-regular Sequences, Cobham’s theorem and its extensions, A matrix generalization of a theorem of Fine, Mahler takes a regular view of Zaremba, Counting Subwords Occurrences in Base-b Expansions, Automatic Sequences and Generalised Polynomials, Reconnaissabilité des substitutions et complexité des suites automatiques, Unnamed Item, Regular Sequences and the Joint Spectral Radius, Unnamed Item, Becker’s conjecture on Mahler functions, A digit reversal property for an analogue of Stern's sequence, AN INVESTIGATION OF UNIFORM EXPANSIONS OF LARGE ORDER BESSEL FUNCTIONS IN GRAVITATIONAL WAVE SIGNALS, Diophantine approximation of Mahler numbers, Dirichlet series associated to sum-of-digits functions, A lower bound for Cusick’s conjecture on the digits of n + t, GAPS IN THE THUE–MORSE WORD

Uses Software

ALGOL 60

Cites Work

The ring of \(k\)-regular sequences