Applications of Propositional Logic to Cellular Automata

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]

Bookmark and Share

Rating: 1  2  3  4  5 
by 30 people

Added on Jan 14, 2010

Report Abuse


    Profile info

    Stefano Cavagnetto

    MSc International Management

    Résumé (CV)


    About me

    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.

    Contact form