Some applications of propositional logic to cellular automata

DOI10.1002/MALQ.200810008zbMATH Open1183.68392OpenAlexW2093602291MaRDI QIDQ3650319FDOQ3650319

Authors: 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

Recommendations

• scientific article; zbMATH DE number 4074491
• Propositional logic and cellular automata on monoids
• Reversibility and surjectivity problems of cellular automata
• scientific article; zbMATH DE number 4197448
• scientific article; zbMATH DE number 2063251

zbMATH Keywords

cellular automatapropositional logicpropositional proof complexity

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Propositional logic and cellular automata on monoids
• Injectivity of cellular automata

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3650319)