Surjective multiband linear cellular automata and Smith's normal form

Authors

  • Ignacia Arcaya Universidad Central de Venezuela, Venezuela
  • Neptalí Romero Universidad Centroccidental Lisandro Alvarado, Venezuela

Keywords:

Smith normal form, multiband cellular automata

Abstract

In this paper the Smith normal form of certain matrices is used to provide another char acterization for the surjectivity of one-dimensional linear cellular automata with multiple local rules over the ring ZN of integers modulo N ≥ 2.. We reached this goal through an adaptation of a well known result of G. A. Hedlund which characterize the surjectivity of general one-dimensional cellular automata.

Downloads

Download data is not yet available.

Author Biographies

Ignacia Arcaya, Universidad Central de Venezuela, Venezuela

Departamento de Matem´atica, Universidad Central de Venezuela , Ciudad Universitaria, Caracas, Venezuela

Neptalí Romero, Universidad Centroccidental Lisandro Alvarado, Venezuela

Departamento de Matem´atica, Universidad Centroccidental Lisandro Alvarado, Barquisimeto, Lara, Apdo 3001,
Venezuela

References

J.P. Allouche and G. Skordev. Remarks on permutive cellular automata. J. Comput. Syst. Sci. 67, (2003) 174-182.

Arcaya and N. Romero. On a Hedlund's theorem and place-dependent cellular automata. Divulg. Mat. 15(2) 81-92 (2007).

N. A. Baas and T. Helvik. Higher order Cellular Automata. Adv. Complex Syst. 8. (2005) 169-192.

M. Itó, N. Osato and M. Nasu. Linear Cellular Automata over Zm. Journal of Computer and System Sciences, 27 (1983) 125-140.

R. Q. Jia. Multivariate Discrete Splines and Linear Diophantine Equations. Trans. Amer. Math. Soc. 340 (1993) 179-198.

F. Lazebnik. On Systems of Linear Diophantine Equations. Math. Mag. 69 (1996) 261-266.

G. A. Hedlund. Endomorphisms and Automorphisms of the shift dynamical systems. Math. Sys. Th. 3, (1969) 320-375.

J. Kari. Linear cellular automata with multiple state variables. Lecture Notes in Computer Science Vol. 1770, (2000) 110-121. Springer, New York.

E. Lange, H.O. Peitgen and G. Skordev. Fractal patterns in Gaussian and Stirling number tables. Ars Combin. 48, (1998) 3-26.

N. Romero, A. Rovella and F. Vilamajó. Remark on Cellular Automata and Shift Preserving Maps. Appl. Math. Lett. 19, (2006) 576-580.

B.L. van der Waerden. Algebra. Springer-Verlag. Berlin, Heidelberg, New York (1967).
Publicaciones en Ciencias y Tecnologia Vol 4 nro 1 año 2010

Published

2009-07-10

How to Cite

[1]
I. Arcaya and N. Romero, “Surjective multiband linear cellular automata and Smith’s normal form”, Publ.Cienc.Tecnol, vol. 4, no. 1, pp. 17-23, Jul. 2009.

Issue

Vol. 4 No. 1 (2010): January - June

Section

Research Article

Creative Commons Reconocimiento-NoComercial-CompartirIgual 4.0 Internacional (CC BY-NC-SA 4.0)

The opinions expressed by the authors do not necessarily reflect the position of the publisher of the publication or of UCLA. The total or partial reproduction of the texts published here is authorized, as long as the complete source and the electronic address of this journal are cited.

The authors fully retain the rights to their works, giving the journal the right to be the first publication where the article is presented. The authors have the right to use their articles for any purpose as long as it is done for non-profit. Authors are recommended to disseminate their articles in the final version, after publication in this journal, in the electronic media of the institutions to which they are affiliated or personal digital media.