 |
 |
 |
Conference papers
Permutive one-way cellular automata and the finiteness problem for automaton groups
Abstract : The decidability of the finiteness problem for automaton groups is a well-studied open question on Mealy automata. We connect this question of algebraic nature to the periodicity problem of one-way cellular automata, a dynamical question known to be undecidable in the general case. We provide a first undecidability result on the dynamics of one-way permutive cellular automata, arguing in favor of the undecidability of the finiteness problem for reset Mealy automata.
Cited literature [16 references]
https://hal-univ-orleans.archives-ouvertes.fr/hal-01436460
Contributor : Martin Delacourt <>
Submitted on : Tuesday, March 14, 2017 - 12:52:39 PM
Last modification on : Tuesday, November 19, 2019 - 4:48:10 PM
Long-term archiving on: : Thursday, June 15, 2017 - 1:55:39 PM
Contributor : Martin Delacourt <>
Submitted on : Tuesday, March 14, 2017 - 12:52:39 PM
Last modification on : Tuesday, November 19, 2019 - 4:48:10 PM
Long-term archiving on: : Thursday, June 15, 2017 - 1:55:39 PM
File
pocafpag.pdf
Files produced by the author(s)