Profinite automata

DOI10.1016/J.AAM.2016.11.005MaRDI QIDQ504425zbMATH OpenOpenAlexFDO

Authors Reem Yassawi, Eric Rowland

Publication date 16 January 2017

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.7659, http://oro.open.ac.uk/67092/1/profinite_August_28.pdf

zbMATH Keywords

\(p\)-adic integersequence of integersuncountable alphabet

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Congruences; primitive roots; residue systems (11A07) Symbolic dynamics (37B10) Automata sequences (11B85) Word problems, etc. in computability and recursion theory (03D40)

Abstract: Many sequences of $p$-adic integers project modulo $p^{a}lpha$ to $p$-automatic sequences for every $alphageq0$. Examples include algebraic sequences of integers, which satisfy this property for every prime $p$, and some cocycle sequences, which we show satisfy this property for a fixed $p$. For such a sequence, we construct a profinite automaton that projects modulo $p^{a}lpha$ to the automaton generating the projected sequence. In general, the profinite automaton has infinitely many states. Additionally, we consider the closure of the orbit, under the shift map, of the $p$-adic integer sequence, defining a shift dynamical system. We describe how this shift is a letter-to-letter coding of a shift generated by a constant-length substitution defined on an uncountable alphabet, and we establish some dynamical properties of these shifts.

Recommendations

• A characterization of \(p\)-automatic sequences as columns of linear cellular automata
• The \(p\)-adic theory of automata functions
• Automata finiteness criterion in terms of van der Put series of automata functions
• scientific article; zbMATH DE number 4073118
• scientific article; zbMATH DE number 3933195

Cites work

• scientific article; zbMATH DE number 124862 (Why is no real title available?)
• scientific article; zbMATH DE number 3513916 (Why is no real title available?)
• scientific article; zbMATH DE number 687959 (Why is no real title available?)
• scientific article; zbMATH DE number 3431597 (Why is no real title available?)
• scientific article; zbMATH DE number 2236657 (Why is no real title available?)
• A Second Course in Formal Languages and Automata Theory
• Algebraic power series and diagonals
• Arithmetics properties of substitutions and infinite automata
• Automatic congruences for diagonals of rational functions
• Avoiding 3/2-powers over the natural numbers
• Avoiding squares and overlaps over the natural numbers
• Fibonacci Series Modulo m
• Fonctions zeta p-adiques des corps de nombres abeliens réels
• Generating trees and forbidden subsequences
• Inverse Limits of Measure Spaces
• Power of words and recognizability of fixpoints of a substitution
• Substitution dynamical systems - spectral analysis
• Substitution dynamical systems on infinite alphabets
• Suites algébriques, automates et substitutions
• The rational-transcendental dichotomy of Mahler functions
• The ring of k-regular sequences
• The spectrum of dynamical systems arising from substitutions of constant length
• Uniform tag sequences
• \(p\)-adic asymptotic properties of constant-recursive sequences

Cited in

(5)

• Profinite Methods in Automata Theory
• Spectral properties of substitutions on compact alphabets
• Substitution-dynamics and invariant measures for infinite alphabet-path space
• Prime automata do not exist
• \(p\)-adic asymptotic properties of constant-recursive sequences

This page was built for publication: Profinite automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q504425)