Line complexity asymptotics of polynomial cellular automata

DOI10.1007/S11139-017-9957-7MaRDI QIDQ1623886zbMATH OpenOpenAlexFDO

Authors Bertrand Stone

Publication date 15 November 2018

Published in The Ramanujan Journal (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic estimatescellular automataadditive transition rulesline complexity

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

Abstract: Cellular automata are discrete dynamical systems that consist of patterns of symbols on a grid, which change according to a locally determined transition rule. In this paper, we will consider cellular automata that arise from polynomial transition rules, where the symbols in the automaton are integers modulo some prime $p$. We are principally concerned with the asymptotic behavior of the line complexity sequence $a_T(k)$, which counts, for each $k$, the number of coefficient strings of length $k$ that occur in the automaton. We begin with the modulo $2$ case. For a given polynomial $T(x)=c_0+c_{1}x+\mathrm{...}+c_n{x}^n$ with $c_0,c_{n}eq0$, we construct odd and even parts of the polynomial from the strings $0c_1{c}_3{c}_5\mathrm{...}$ and $c_0{c}_2{c}_4\mathrm{...}$, respectively. We prove that for polynomials for which the odd and even parts are relatively prime, $a_T(k)$ satisfies recursions of a specific form. We also consider powers of transition rules modulo $p$, introducing a notion of the order of a recursion. We show that the property of "having a recursion of some order" is preserved when the transition rule is raised to a positive integer power. Extending to a more general setting, we investigate the asymptotics of $a_T(k)$ by considering an abstract generating function $phi(z)=su{m}_{k=1}^{i}nftyalpha(k)z^k$ which satisfies a general functional equation relating $phi(z)$ and $phi(z^p)$ for some prime $p$. We show that there is a continuous, piecewise quadratic function $f$ on $[1/p,1]$ for which $li{m}_{koinfty}(alpha(k)/k^2-f(p^{-langlelo{g}_{p}kangle}))=0$, where $langleyangle$ denotes the fractional part of $y$. We use this result to show that for certain positive integer sequences $s_{k}oinfty$ with a parameter $xin[1/p,1]$, the ratio $alpha(s_k(x))/s_k(x{)}^2$ tends to $f(x)$, and that the limit superior and inferior of $alpha(k)/k^2$ are given by the extremal values of $f$.

Recommendations

• scientific article; zbMATH DE number 4195208
• Complexity and linear cellular automata
• Characteristic and minimal polynomials of linear cellular automata
• Linear complexity of polylinear sequences
• Complexity of generic limit sets of cellular automata
• Algebraic properties of linear cellular automata
• scientific article; zbMATH DE number 3868622
• On the quantitative behavior of the linear cellular automata
• On the computational complexity of finite cellular automata
• Linear algebra based bounds for one-dimensional cellular automata

Cites work

• scientific article; zbMATH DE number 3539473 (Why is no real title available?)
• scientific article; zbMATH DE number 3613366 (Why is no real title available?)
• Complexity and linear cellular automata
• Computing fractal dimensions for additive cellular automata

Cited in

(2)

• Complexity and linear cellular automata
• On the cell probe complexity of polynomial evaluation

This page was built for publication: Line complexity asymptotics of polynomial cellular automata

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