๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Inversion of 2D cellular automata: some complexity results

โœ Scribed by B. Durand

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
1021 KB
Volume
134
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

On the Computational Complexity of Finit
On the Computational Complexity of Finite Cellular Automata
โœ K. Sutner ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 932 KB

We study the computational complexity of several problems with the evolution of configurations on finite cellular automata. In many cases, the problems turn out to be complete in their respective classes. For example, the problem of deciding whether a configuration has a predecessor is shown to be N

Some applications of propositional logic
Some applications of propositional logic to cellular automata
โœ Stefano Cavagnetto ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 154 KB

## Abstract In this paper we give a new proof of Richardson's theorem [31]: a global function __G__~๐”ธ~ of a cellular automaton ๐”ธ is injective if and only if the inverse of __G__~๐”ธ~ is a global function of a cellular automaton. Moreover, we show a way how to construct the inverse cellular automaton