| dbo:abstract |
The Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics. It is named after Morton L. Curtis, Gustav A. Hedlund, and Roger Lyndon; in his 1969 paper stating the theorem, Hedlund credited Curtis and Lyndon as co-discoverers. It has been called "one of the fundamental results in symbolic dynamics". The theorem states that a function from a shift space to itself represents the transition function of a one-dimensional cellular automaton if and only if it is continuous (with respect to the Cantor topology) and equivariant (with respect to the shift map). More generally, it asserts that the morphisms between any two shift spaces (that is, continuous mappings that commute with the shift) are exactly those mappings which can be defined uniformly by a local rule. The version of the theorem in Hedlund's paper applied only to one-dimensional finite automata, but a generalization to higher dimensional integer lattices was soon afterwards published by , and it can be even further generalized from lattices to discrete groups. One important consequence of the theorem is that, for reversible cellular automata, the reverse dynamics of the automaton can also be described by a cellular automaton. (en) |
| dbo:wikiPageID |
18903091 (xsd:integer) |
| dbo:wikiPageLength |
12177 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1077974293 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Reversible_cellular_automaton dbr:Characterization_(mathematics) dbr:Integer_lattice dbc:Articles_containing_proofs dbr:Compact_space dbr:Continuous_function dbr:Function_(mathematics) dbr:Morphism dbr:Equivariant_map dbr:Alphabet_(computer_science) dbc:Symbolic_dynamics dbc:Theorems_in_discrete_mathematics dbr:Cellular_automaton dbr:Discrete_group dbr:Equivariant dbr:Symbolic_dynamics dbr:Group_action_(mathematics) dbr:Gustav_A._Hedlund dbc:Cellular_automata dbr:Integer dbr:Open_cover dbr:Sequence dbr:Cellular_automata dbr:Tychonoff's_theorem dbr:Shift_space dbr:Roger_Lyndon dbr:Morton_L._Curtis dbr:Topological_space dbr:Surjunctive_group dbr:Cantor_topology dbr:Transition_map dbr:Shift_map |
| dbp:wikiPageUsesTemplate |
dbt:Harvtxt dbt:Math dbt:Mvar dbt:Reflist |
| dct:subject |
dbc:Articles_containing_proofs dbc:Symbolic_dynamics dbc:Theorems_in_discrete_mathematics dbc:Cellular_automata |
| gold:hypernym |
dbr:Characterization |
| rdf:type |
yago:WikicatCellularAutomata yago:Anomaly109606527 yago:Automaton109825519 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:YagoLegalActor yago:YagoLegalActorGeo yago:Whole100003553 |
| rdfs:comment |
The Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics. It is named after Morton L. Curtis, Gustav A. Hedlund, and Roger Lyndon; in his 1969 paper stating the theorem, Hedlund credited Curtis and Lyndon as co-discoverers. It has been called "one of the fundamental results in symbolic dynamics". (en) |
| rdfs:label |
Curtis–Hedlund–Lyndon theorem (en) |
| owl:sameAs |
freebase:Curtis–Hedlund–Lyndon theorem wikidata:Curtis–Hedlund–Lyndon theorem https://global.dbpedia.org/id/4ievf |
| prov:wasDerivedFrom |
wikipedia-en:Curtis–Hedlund–Lyndon_theorem?oldid=1077974293&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Curtis–Hedlund–Lyndon_theorem |
| is dbo:wikiPageRedirects of |
dbr:Curtis-Hedlund-Lyndon_theorem dbr:Hedlund's_theorem |
| is dbo:wikiPageWikiLink of |
dbr:Reversible_cellular_automaton dbr:Equivariant_map dbr:Garden_of_Eden_(cellular_automaton) dbr:Curtis-Hedlund-Lyndon_theorem dbr:Cellular_automaton dbr:Gustav_A._Hedlund dbr:Sofic_group dbr:Tychonoff's_theorem dbr:List_of_theorems dbr:Roger_Lyndon dbr:Morton_L._Curtis dbr:Surjunctive_group dbr:Hedlund's_theorem |
| is foaf:primaryTopic of |
wikipedia-en:Curtis–Hedlund–Lyndon_theorem |