Some applications of propositional logic to cellular automata

DOI10.1002/malq.200810008zbMath1183.68392OpenAlexW2093602291MaRDI QIDQ3650319

S. Cavagnetto

Publication date: 14 December 2009

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.200810008

zbMATH Keywords

cellular automatapropositional logicpropositional proof complexity

Mathematics Subject Classification ID

Logic in computer science (03B70) Cellular automata (computational aspects) (68Q80) Classical propositional logic (03B05) Complexity of proofs (03F20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reversibility of 2D cellular automata is undecidable
• Reversibility and surjectivity problems of cellular automata
• Inversion of 2D cellular automata: Some complexity results
• Theory of cellular automata: a survey
• Tesselations with local transformations
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory
• Lower bounds to the size of constant-depth propositional proofs
• Lower bounds for resolution and cutting plane proofs and monotone computations
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
• Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
• Developments in Language Theory
• A Machine-Oriented Logic Based on the Resolution Principle
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• The undecidability of the domino problem
• A Computing Procedure for Quantification Theory
• Simple Computation-Universal Cellular Spaces

This page was built for publication: Some applications of propositional logic to cellular automata