Chebyshev polynomials over finite fields and reversibility of \(\sigma\)-automata on square grids

DOI10.1016/j.tcs.2004.03.031zbMath1068.68089OpenAlexW2064562649MaRDI QIDQ596114

Markus Hunziker, António Machiavelo, Jihun Park

Publication date: 10 August 2004

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.03.031

zbMATH Keywords

Chebyshev polynomialsAdditive cellular automataFinite fields

Mathematics Subject Classification ID

Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.) (33C45) Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15)

Related Items

Lights Out for graphs related to one another by constructions ⋮ On the Dimension of the Space of Harmonic Functions on a Discrete Torus ⋮ A Note on the Insecurity of Cryptosystems Based on Chebyshev Polynomials ⋮ Lights Out On A Random Graph ⋮ Generalized switch-setting problems ⋮ Periodic binary harmonic functions on lattices ⋮ A singular quartic curve over a finite field and the trisentis game ⋮ Linear algebraic approach on real \(\sigma\)-game ⋮ Minimum light number of lit-only \(\sigma\)-game on a tree ⋮ Chasing the Lights in Lights Out ⋮ Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game? ⋮ Periodic harmonic functions on lattices and points count in positive characteristic ⋮ Periodic harmonic functions on lattices and Chebyshev polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\sigma\)-game, \(\sigma ^{+}\)-game and two-dimensional additive cellular automata
• Artin's conjecture for primitive roots
• Multidimensional \(\sigma\)-automata, \(\pi\)-polynomials and generalised S-matrices
• The spectral mapping theorem, norms on rings, and resultants.
• Fibonacci polynomials and parity domination in grid graphs
• Linear cellular automata and the garden-of-eden
• \(\sigma\)-Automata and Chebyshev-polynomials
• Merlin's Magic Square
• Trigonometric diophantine equations (On vanishing sums of roots of unity)
• The σ-Game and Cellular Automata