A universal cellular automaton in the hyperbolic plane.

DOI10.1016/S0304-3975(02)00660-6zbMATH Open1045.68095OpenAlexW1988062990MaRDI QIDQ1401276FDOQ1401276

Authors: Francine Herrmann, M. Margenstern 

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00660-6

Recommendations

• Universal cellular automata with two states in the hyperbolic plane
• Cellular automata and hyperbolic spaces
• A particular universal cellular automaton
• Cellular Automata in the Hyperbolic Plane: Proposal for a New Environment
• A weakly universal cellular automaton in the heptagrid of the hyperbolic plane
• scientific article; zbMATH DE number 2111977
• scientific article; zbMATH DE number 5244680
• A physically universal cellular automaton
• New tools for cellular automata in the hyperbolic plane
• A uniform and intrinsic proof that there are universal cellular automata in hyperbolic spaces

zbMATH Keywords

Cellular automataCircuitsHyperbolic planeRegistersSwitchesUniversality

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Introduction to hyperbolic geometry
• New tools for cellular automata in the hyperbolic plane
• Undecidable tiling problems in the hyperbolic plane
• NP problems are tractable in the space of cellular automata in the hyperbolic plane
• Title not available (Why is that?)
• One-way cellular automata on Cayley graphs
• Two railway circuits: A universal circuit and an NP-difficult one

Cited In (26)

• Title not available (Why is that?)
• Cellular Automata in the Hyperbolic Plane: Proposal for a New Environment
• ON A CHARACTERIZATION OF CELLULAR AUTOMATA IN TILINGS OF THE HYPERBOLIC PLANE
• A weakly universal cellular automaton in the pentagrid with five states
• A uniform and intrinsic proof that there are universal cellular automata in hyperbolic spaces
• A universal semi-totalistic cellular automaton on kite and dart Penrose tilings
• Universal cellular automata with two states in the hyperbolic plane
• Small universal cellular automata in hyperbolic spaces. A collection of jewels
• A weakly universal cellular automaton in the heptagrid of the hyperbolic plane
• A 6-state universal semi-totalistic cellular automaton on kite and dart Penrose tilings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A new way to implement cellular automata on the penta- and heptagrids
• A universal cellular automaton on the heptagrid of the hyperbolic plane with four states
• Title not available (Why is that?)
• On the communication between cells of a cellular automaton on the penta- and heptagrids of the hyperbolic plane
• A five-state von Neumann neighbor universal hyperbolic cellular automaton
• Universality and the halting problem for cellular automata in hyperbolic spaces: the side of the halting problem
• Surprising areas in the quest for small universal devices
• A universal cellular automaton on the ternary heptagrid
• Title not available (Why is that?)
• A strongly universal cellular automaton on the heptagrid with seven states
• In some curved spaces, one can solve NP-hard problems in polynomial time
• A package of algorithms to device cellular automata in the hyperbolic plane and related questions

This page was built for publication: A universal cellular automaton in the hyperbolic plane.

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