Applications of Propositional Logic to Cellular Automata

In this paper we give a new proof of Richardson’s theorem : a global function G_{A} of a cellular automaton A is injective if and only if the inverse of G_{A} is a global function of a cellular automaton. More- over, we show a way how to construct the inverse cellular automaton using the method of feasible interpolation. We also solve two problems regarding complexity of cellular automata formulated by Bruno Durand.[preprint available in pdf]

Rating: 1 2 3 4 5
by 16 people

Added on Jan 14, 2010

Report Abuse

Comment

Profile info

Stefano Cavagnetto

Lecturer,
MSc International Management

Résumé (CV)

Stefano is a Doctor in Mathematics and Philosophy. He earned his degrees from Charles University, the Institute of Mathematics of the Academy of Sciences and the Amedeo Avogadro University, in Vercelli, Italy respectively. His MA in Science Communication was completed at COREP - Centre for Education and Permanent Research - of the Polytechnic University of Turin. Stefano was a visiting scholar at Columbia University in New York City and the Isaac Newton Institute in Cambridge. He founded the Prague College Research Centre in 2008 and is currently exploring with his staff such diverse topics as the history of programming languages, exploring links between art and mathematics in cooperation with the design school, and looking at game theory and its application to philosophy and business management. Stefano helps to ensure that the research activities of students and staff, and especially the Bachelors and Masters dissertations, are intrinsically connected to the our key areas of inquiry in Business, IT and Art & Design.

Contact me

To contact a student or faculty member, please use this form.Your requests will be forwarded to the person concerned by Prague College. Messages violating our terms of use, will not be forwarded. Thank you.

Applications of Propositional Logic to Cellular Automata