𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some applications of propositional logic to cellular automata

✍ Scribed by Stefano Cavagnetto

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
154 KB
Volume
55
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

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 using the method of feasible interpolation from [20]. We also solve two problems regarding complexity of cellular automata formulated by Durand [12] (Β© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

πŸ“œ SIMILAR VOLUMES

The application of cellular automata to
The application of cellular automata to the erosion of landforms
✍ Roger Smith πŸ“‚ Article πŸ“… 1991 πŸ› John Wiley and Sons 🌐 English βš– 769 KB

Two approaches to modelling surface erosion are described which can be used to explain the development of geomorphological features. The first approach uses non-linear wave theory and shows how surface gradient discontinuities can arise as the erosion of an initially smooth surface proceeds. For iso

Logical Complexity of Some Classes of Tr
Logical Complexity of Some Classes of Tree Languages Generated by Multiple-Tree-Automata
✍ Wojciech Buszkowski πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 515 KB

LOGICAL COMPLEXITY O F SOME CLASSES O F TREE LANGUAGES GENERATED BY MULTIPLE-TREE-AUTOMATA by WOJCIECH BUSZKOWSKI in Poznaii (Poland) 0. Introduction. Preliminary terminology and notation Multiple-tree-automata (MTAs) correspond to the kind of grammars called Lindenmayer systems with tables (cf. ROZ