Algebraic Characterization of Reversible First Degree Cellular Automata over $\mathbb{Z}_d$
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914371953754112 |
|---|---|
| author | J., Baby C. Bhattacharjee, Kamalika |
| author_facet | J., Baby C. Bhattacharjee, Kamalika |
| contents | There exists algorithms to detect reversibility of cellular automaton (CA) for both finite and infinite lattices taking quadratic time. But, can we identify a $d$-state CA rule in constant time that is always reversible for every lattice size $n\in \mathbb{N}$? To address this issue, this paper explores the reversibility properties of a subset of one-dimensional, $3$-neighborhood, $d$-state finite cellular automata (CAs), known as the first degree cellular automata (FDCAs) for any number of cells $(n\in \mathbb{N})$ under the null boundary condition. {In a first degree cellular automaton (FDCA), the local rule is defined using eight parameters. To ensure that the global transition function of $d$-state FDCA is reversible for any number of cells $(n\in \mathbb{N})$, it is necessary and sufficient to verify only three algebraic conditions among the parameter values. Based on these conditions, for any given $d$, one can synthesize all reversible FDCAs rules. Similarly, given a FDCA rule, one can check these conditions to decide its reversibility in constant time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_05253 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Algebraic Characterization of Reversible First Degree Cellular Automata over $\mathbb{Z}_d$ J., Baby C. Bhattacharjee, Kamalika Formal Languages and Automata Theory Discrete Mathematics There exists algorithms to detect reversibility of cellular automaton (CA) for both finite and infinite lattices taking quadratic time. But, can we identify a $d$-state CA rule in constant time that is always reversible for every lattice size $n\in \mathbb{N}$? To address this issue, this paper explores the reversibility properties of a subset of one-dimensional, $3$-neighborhood, $d$-state finite cellular automata (CAs), known as the first degree cellular automata (FDCAs) for any number of cells $(n\in \mathbb{N})$ under the null boundary condition. {In a first degree cellular automaton (FDCA), the local rule is defined using eight parameters. To ensure that the global transition function of $d$-state FDCA is reversible for any number of cells $(n\in \mathbb{N})$, it is necessary and sufficient to verify only three algebraic conditions among the parameter values. Based on these conditions, for any given $d$, one can synthesize all reversible FDCAs rules. Similarly, given a FDCA rule, one can check these conditions to decide its reversibility in constant time. |
| title | Algebraic Characterization of Reversible First Degree Cellular Automata over $\mathbb{Z}_d$ |
| topic | Formal Languages and Automata Theory Discrete Mathematics |
| url | https://arxiv.org/abs/2603.05253 |