Profinite automata

DOI10.1016/J.AAM.2016.11.005zbMATH Open1375.37041arXiv1403.7659OpenAlexW3037965222MaRDI QIDQ504425FDOQ504425

Authors: Reem Yassawi, Eric Rowland 

Publication date: 16 January 2017

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

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.

Full work available at URL: https://arxiv.org/abs/1403.7659

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

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)

Cites Work

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

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)