- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Some applications of propositional logic to cellular automata
Mathematical Logic Quarterly 55 (6):605-616 (2009)
Abstract
In this paper we give a new proof of Richardson's theorem [31]: a global function G[MATHEMATICAL DOUBLE-STRUCK CAPITAL A] of a cellular automaton [MATHEMATICAL DOUBLE-STRUCK CAPITAL A] is injective if and only if the inverse of G[MATHEMATICAL DOUBLE-STRUCK CAPITAL A] 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]My notes
Similar books and articles
On coding uncountable sets by reals.Joan Bagaria & Vladimir Kanovei - 2010 - Mathematical Logic Quarterly 56 (4):409-424.
Distributed Control of a Manufacturing System with One-Dimensional Cellular Automata.Irving Barragan-Vite, Juan C. Seck-Tuoh-Mora, Norberto Hernandez-Romero, Joselito Medina-Marin & Eva S. Hernandez-Gress - 2018 - Complexity 2018:1-15.
On completely nonmeasurable unions.Szymon Żeberski - 2007 - Mathematical Logic Quarterly 53 (1):38-42.
Combinatorial properties of some cellular automata related to the mosaic cycle concept.Claude Lobry & Hervé Elmoznino - 2000 - Acta Biotheoretica 48 (3-4):219-242.
Cellular automata and the sciences of complexity (part I): A review of some outstanding problems in the theory of cellular automata. [REVIEW]Howard Gutowitz - 1996 - Complexity 1 (5):16-22.
Weyl, Dirac and Maxwell Quantum Cellular Automata: Analitical Solutions and Phenomenological Predictions of the Quantum Cellular Automata Theory of Free Fields.Alessandro Bisio, Giacomo Mauro D’Ariano, Paolo Perinotti & Alessandro Tosini - 2015 - Foundations of Physics 45 (10):1203-1221.
Mutual synchronization in a network of digital clocks as the key cellular automaton mechanism of nature: computational model of fundamental physics.Simon Y. Berkovich - 1986 - Rockville, MD: Synopsis.
An Outline of Cellular Automaton Universe via Cosmological KdV equation.Victor Christianto, Florentin Smarandache & Yunita Umniyati - manuscript
The emergence of dynamical complexity: An exploration using elementary cellular automata.Eduardo Mizraji - 2004 - Complexity 9 (6):33-42.
Analytics
Added to PP
2013-12-01
Downloads
6 (#1,485,580)
6 months
26 (#116,274)
2013-12-01
Downloads
6 (#1,485,580)
6 months
26 (#116,274)
Historical graph of downloads
References found in this work
Three uses of the herbrand-Gentzen theorem in relating model theory and proof theory.William Craig - 1957 - Journal of Symbolic Logic 22 (3):269-285.
A Machine-Oriented Logic based on the Resolution Principle.J. A. Robinson - 1966 - Journal of Symbolic Logic 31 (3):515-516.
Lower Bounds to the size of constant-depth propositional proofs.Jan Krajíček - 1994 - Journal of Symbolic Logic 59 (1):73-86.
A Computing Procedure for Quantification Theory.Martin Davis & Hilary Putnam - 1966 - Journal of Symbolic Logic 31 (1):125-126.
Lower Bounds for resolution and cutting plane proofs and monotone computations.Pavel Pudlák - 1997 - Journal of Symbolic Logic 62 (3):981-998.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-68866f4b87-tsllw uwo