×

Multidimensional \(\sigma\)-automata, \(\pi\)-polynomials and generalised S-matrices. (English) Zbl 0902.68125

Summary: In this article we study \(\sigma (\sigma^{+})\)-automata on finite multidimensional grids with different boundary conditions. We obtain a natural representation of the global linear map of such automata in terms of Kronecker products of matrices having a simple structure. Using this representation and properties of binary Chebyshev polynomials, we obtain necessary and sufficient condition for the invertibility of this map. Also in certain cases, we relate this condition to the number theoretic properties of the number of dimensions and the lengths of the dimensions. We generalise the notion of nearest neighbourhood to many dimensions and characterise invertibility of \(\sigma\)-automata with such neighbourhoods.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Ullman, J. D., Principles of Compiler Design (1977), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01702
[2] Barnett, S., Matrices, Methods and Applications (1990), Clarendon Press: Clarendon Press Oxford · Zbl 0706.15001
[3] Barua, R.; Ramakrishna, S., σ-game, \(σ^+\)-game, and two dimensional cellular automata, Theoret. Comput. Sci., 154, 349-366 (1996) · Zbl 0872.68121
[4] Chowdhury, D. R., Theory and application of additive cellular automata for reliable and testable VLSI circuit design, (Ph.D Dissertation (1992), Dept. of Comput. Sci. & Engg., Indian Institute of Technology: Dept. of Comput. Sci. & Engg., Indian Institute of Technology Kharagpur, India)
[5] Lidl, R.; Niederreiter, H., Encyclopedia of Mathematics, Finite Fields (1986), Cambridge University Press: Cambridge University Press Cambridge
[6] Lindenmayer, A., Mathematical models for cellular interactions in development, J. Theoret. Biol., 18, 280-299 (1968)
[7] Martin, O.; Odlyzko, A. M.; Wolfram, S., Algebraic properties of cellular automata, Comm. Math. Phys., 93, 219-258 (1984) · Zbl 0564.68038
[8] Mignotte, M., Mathematics for Computer Algebra (1991), Springer: Springer Berlin
[9] Pelletier, D. H., Merlin’s magic square, Amer. Math. Monthly, 94, 143-150 (1987) · Zbl 0627.05020
[10] Sutner, K., On σ-automata, Complex Systems, 2, 1-28 (1988) · Zbl 0657.68060
[11] Sutner, K., Linear cellular automata and the Garden-of-Eden, Math. Intelligencer, 11, 49-53 (1989) · Zbl 0770.68094
[12] Serra, M., The analysis of one dimensional cellular automata and their aliasing properties, IEEE Trans. Comput. Aided Design of Circuits and Systems, 9, 767-778 (1990)
[13] Sutner, K., The σ-game and cellular automata, Amer. Math. Monthly, 97, 24-34 (1990) · Zbl 0797.68122
[14] Sutner, K., σ-automata and π-polynomials, (Tech. Rep. CS-9408 (1994), Stevens Institute of Technology), 6 December · Zbl 0947.68540
[15] K. Sutner, σ-automata and Chebyshev polynomials, see http://www.cs.cmu.edu/ Sutner.; K. Sutner, σ-automata and Chebyshev polynomials, see http://www.cs.cmu.edu/ Sutner.
[16] Wolfram, S., Statistical mechanics of cellular automata, Rev. Modern Phys., 55, 601-644 (1983) · Zbl 1174.82319
[17] Wolfram, S., Theory and Applications of Cellular Automata: Including Selected Papers 1983-1986 (1986), World Scientific: World Scientific Singapore · Zbl 0609.68043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.