(Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata

Autor:	Gaétan Richard
Rok vydání:	2009
Předmět:	Counter machine Discrete mathematics Bounded function Quantum finite automata Automata theory Nonlinear Sciences::Cellular Automata and Lattice Gases Completeness (statistics) Computer Science::Formal Languages and Automata Theory Cellular automaton Mathematics Undecidable problem Decidability
Zdroj:	Mathematical Foundations of Computer Science 2009 ISBN: 9783642038150 MFCS
Popis:	Extension of sand pile models, one-dimensional sand automata are an intermediate discrete dynamical system between one dimensional cellular automata and two-dimensional cellular automata. In this paper, we shall study the decidability problem of global behavior of this system. In particular, we shall focus on the problem of injectivity and surjectivity which have the property of being decidable for one-dimensional cellular automata and undecidable for two-dimensional one. We prove the following quite surprising property that surjectivity is undecidable whereas injectivity is decidable. For completeness, we also study these properties on some classical restrictions of configurations (finite, periodic and bounded ones).
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::cd29c43052965fb78b0e53b6652a74ab https://doi.org/10.1007/978-3-642-03816-7_55 Zobrazit plný text záznamu