Reversible Cellular Automata: From Fundamental Classical Results to Recent Developments View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-07

AUTHORS

Jarkko Kari

ABSTRACT

A cellular automaton is a dynamical system on an infinite array of cells defined by a local update rule that is applied simultaneously at all cells. By carefully choosing the update rule, the global dynamics can be made information preserving. In this case, the cellular automaton is called reversible. In this article, we explain fundamental classical results concerning reversible cellular automata and discuss some more recent developments on selected topics. Classical results reviewed include the Curtis–Hedlund–Lyndon theorem, the Garden-of-Eden theorem and the invariance of uniform Bernoulli distribution under reversible cellular automata. We then describe several techniques to construct reversible cellular automata and a method to determine whether a given one-dimensional automaton is reversible. We present undecidability issues concerning reversible cellular automata and discuss three types of universality: computational universality, intrinsic universality, and physical universality. We finish with short notes about time symmetry, expansiveness, and conservation laws. More... »

PAGES

145-172

References to SciGraph publications

  • 1970-10. Mathematical Games in SCIENTIFIC AMERICAN
  • 2005. A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2010. Cellular Automata and Groups in NONE
  • 2015-09. Statistical Mechanics of Surjective Cellular Automata in JOURNAL OF STATISTICAL PHYSICS
  • 1973. Some general dynamical notions in RECENT ADVANCES IN TOPOLOGICAL DYNAMICS
  • 1969-12. Endomorphisms and automorphisms of the shift dynamical system in MATHEMATICAL SYSTEMS THEORY
  • 2005. Reversible Cellular Automata in DEVELOPMENTS IN LANGUAGE THEORY
  • 2008. Periodicity and Immortality in Reversible Computing in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2008
  • 2012. Universalities in Cellular Automata* in HANDBOOK OF NATURAL COMPUTING
  • 1982-04. Conservative logic in INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS
  • 1996-02. Representation of reversible cellular automata with block permutations in MATHEMATICAL SYSTEMS THEORY
  • 2002. Computing Inside the Billiard Ball Model in COLLISION-BASED COMPUTING
  • 2017. Permutive One-Way Cellular Automata and the Finiteness Problem for Automaton Groups in UNVEILING DYNAMICS AND COMPLEXITY
  • 2011. Snakes and Cellular Automata: Reductions and Inseparability Results in COMPUTER SCIENCE – THEORY AND APPLICATIONS
  • 2011-12. On the hierarchy of conservation laws in a cellular automaton in NATURAL COMPUTING
  • 2017. A One-Dimensional Physically Universal Cellular Automaton in UNVEILING DYNAMICS AND COMPLEXITY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00354-018-0034-6

    DOI

    http://dx.doi.org/10.1007/s00354-018-0034-6

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1105086529


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0601", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Biochemistry and Cell Biology", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/06", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Biological Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Turku", 
              "id": "https://www.grid.ac/institutes/grid.1374.1", 
              "name": [
                "Department of Mathematics and Statistics, University of Turku, 20014, Turku, Finland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kari", 
            "givenName": "Jarkko", 
            "id": "sg:person.011735452354.35", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011735452354.35"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1090/s0002-9939-1963-0155764-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000280146"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0061728", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000307890", 
              "https://doi.org/10.1007/bfb0061728"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-92910-9_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000675121", 
              "https://doi.org/10.1007/978-3-540-92910-9_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0019-3577(93)90040-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001465095"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(95)00038-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002866933"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-2789(91)90150-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004501638"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-2789(91)90150-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004501638"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11505877_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004669217", 
              "https://doi.org/10.1007/11505877_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11505877_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004669217", 
              "https://doi.org/10.1007/11505877_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(05)80025-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006334600"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/scientificamerican1070-120", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007582166", 
              "https://doi.org/10.1038/scientificamerican1070-120"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2004.11.021", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008892501"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-2789(90)90195-u", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010901944"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-2789(90)90195-u", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010901944"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01201813", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011622046", 
              "https://doi.org/10.1007/bf01201813"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01201813", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011622046", 
              "https://doi.org/10.1007/bf01201813"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2008.01.041", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012017670"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(96)00081-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012430781"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(72)80009-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016636649"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-2789(84)90253-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017085534"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-2789(84)90253-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017085534"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-2789(84)90252-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024857421"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-2789(84)90252-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024857421"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-20712-9_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027023655", 
              "https://doi.org/10.1007/978-3-642-20712-9_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-20712-9_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027023655", 
              "https://doi.org/10.1007/978-3-642-20712-9_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2011.02.023", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028506815"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11047-010-9222-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030150049", 
              "https://doi.org/10.1007/s11047-010-9222-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4471-0129-1_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030314599", 
              "https://doi.org/10.1007/978-1-4471-0129-1_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4471-0129-1_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030314599", 
              "https://doi.org/10.1007/978-1-4471-0129-1_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(72)80013-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032327804"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-85238-4_34", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032588457", 
              "https://doi.org/10.1007/978-3-540-85238-4_34"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01857727", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032661873", 
              "https://doi.org/10.1007/bf01857727"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01857727", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032661873", 
              "https://doi.org/10.1007/bf01857727"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10955-015-1281-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032836701", 
              "https://doi.org/10.1007/s10955-015-1281-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10955-015-1281-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032836701", 
              "https://doi.org/10.1007/s10955-015-1281-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2011.02.024", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035046025"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11523468_34", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035438053", 
              "https://doi.org/10.1007/11523468_34"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11523468_34", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035438053", 
              "https://doi.org/10.1007/11523468_34"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jcss.2012.01.006", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041095532"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1041394511", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14034-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041394511", 
              "https://doi.org/10.1007/978-3-642-14034-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14034-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041394511", 
              "https://doi.org/10.1007/978-3-642-14034-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2011.12.037", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041614651"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2688073.2688107", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044103794"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-2789(90)90185-r", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044244052"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-2789(90)90185-r", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044244052"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-0000(77)80007-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046362897"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01691062", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049449230", 
              "https://doi.org/10.1007/bf01691062"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01691062", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049449230", 
              "https://doi.org/10.1007/bf01691062"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01691062", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049449230", 
              "https://doi.org/10.1007/bf01691062"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.31.276", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060777564"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.31.276", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060777564"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0129054195000202", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062897674"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1147/rd.176.0525", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063180324"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-58741-7_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086750862", 
              "https://doi.org/10.1007/978-3-319-58741-7_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-58741-7_35", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086750874", 
              "https://doi.org/10.1007/978-3-319-58741-7_35"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/psapm/014/9961", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1089193116"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/conm/469/09161", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1089202801"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511549755", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098679392"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-07", 
        "datePublishedReg": "2018-07-01", 
        "description": "A cellular automaton is a dynamical system on an infinite array of cells defined by a local update rule that is applied simultaneously at all cells. By carefully choosing the update rule, the global dynamics can be made information preserving. In this case, the cellular automaton is called reversible. In this article, we explain fundamental classical results concerning reversible cellular automata and discuss some more recent developments on selected topics. Classical results reviewed include the Curtis\u2013Hedlund\u2013Lyndon theorem, the Garden-of-Eden theorem and the invariance of uniform Bernoulli distribution under reversible cellular automata. We then describe several techniques to construct reversible cellular automata and a method to determine whether a given one-dimensional automaton is reversible. We present undecidability issues concerning reversible cellular automata and discuss three types of universality: computational universality, intrinsic universality, and physical universality. We finish with short notes about time symmetry, expansiveness, and conservation laws.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00354-018-0034-6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1053619", 
            "issn": [
              "0288-3635", 
              "1882-7055"
            ], 
            "name": "New Generation Computing", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "36"
          }
        ], 
        "name": "Reversible Cellular Automata: From Fundamental Classical Results to Recent Developments", 
        "pagination": "145-172", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "db8673f46e336ee019d1077b8afdd93e544443f34f95bd3ece547e0b02adb303"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00354-018-0034-6"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1105086529"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00354-018-0034-6", 
          "https://app.dimensions.ai/details/publication/pub.1105086529"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T10:30", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000349_0000000349/records_113644_00000004.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00354-018-0034-6"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00354-018-0034-6'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00354-018-0034-6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00354-018-0034-6'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00354-018-0034-6'


     

    This table displays all metadata directly associated to this object as RDF triples.

    205 TRIPLES      21 PREDICATES      70 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00354-018-0034-6 schema:about anzsrc-for:06
    2 anzsrc-for:0601
    3 schema:author N1c80c1e7138a41b984f521fb9ea67109
    4 schema:citation sg:pub.10.1007/11505877_5
    5 sg:pub.10.1007/11523468_34
    6 sg:pub.10.1007/978-1-4471-0129-1_6
    7 sg:pub.10.1007/978-3-319-58741-7_23
    8 sg:pub.10.1007/978-3-319-58741-7_35
    9 sg:pub.10.1007/978-3-540-85238-4_34
    10 sg:pub.10.1007/978-3-540-92910-9_6
    11 sg:pub.10.1007/978-3-642-14034-1
    12 sg:pub.10.1007/978-3-642-20712-9_17
    13 sg:pub.10.1007/bf01201813
    14 sg:pub.10.1007/bf01691062
    15 sg:pub.10.1007/bf01857727
    16 sg:pub.10.1007/bfb0061728
    17 sg:pub.10.1007/s10955-015-1281-2
    18 sg:pub.10.1007/s11047-010-9222-0
    19 sg:pub.10.1038/scientificamerican1070-120
    20 https://app.dimensions.ai/details/publication/pub.1041394511
    21 https://doi.org/10.1016/0019-3577(93)90040-6
    22 https://doi.org/10.1016/0167-2789(84)90252-5
    23 https://doi.org/10.1016/0167-2789(84)90253-7
    24 https://doi.org/10.1016/0167-2789(90)90185-r
    25 https://doi.org/10.1016/0167-2789(90)90195-u
    26 https://doi.org/10.1016/0167-2789(91)90150-8
    27 https://doi.org/10.1016/0304-3975(95)00038-x
    28 https://doi.org/10.1016/j.jcss.2012.01.006
    29 https://doi.org/10.1016/j.tcs.2004.11.021
    30 https://doi.org/10.1016/j.tcs.2008.01.041
    31 https://doi.org/10.1016/j.tcs.2011.02.023
    32 https://doi.org/10.1016/j.tcs.2011.02.024
    33 https://doi.org/10.1016/j.tcs.2011.12.037
    34 https://doi.org/10.1016/s0022-0000(05)80025-x
    35 https://doi.org/10.1016/s0022-0000(72)80009-6
    36 https://doi.org/10.1016/s0022-0000(72)80013-8
    37 https://doi.org/10.1016/s0022-0000(77)80007-x
    38 https://doi.org/10.1016/s0304-3975(96)00081-3
    39 https://doi.org/10.1017/cbo9780511549755
    40 https://doi.org/10.1090/conm/469/09161
    41 https://doi.org/10.1090/psapm/014/9961
    42 https://doi.org/10.1090/s0002-9939-1963-0155764-9
    43 https://doi.org/10.1103/physrevlett.31.276
    44 https://doi.org/10.1142/s0129054195000202
    45 https://doi.org/10.1145/2688073.2688107
    46 https://doi.org/10.1147/rd.176.0525
    47 schema:datePublished 2018-07
    48 schema:datePublishedReg 2018-07-01
    49 schema:description A cellular automaton is a dynamical system on an infinite array of cells defined by a local update rule that is applied simultaneously at all cells. By carefully choosing the update rule, the global dynamics can be made information preserving. In this case, the cellular automaton is called reversible. In this article, we explain fundamental classical results concerning reversible cellular automata and discuss some more recent developments on selected topics. Classical results reviewed include the Curtis–Hedlund–Lyndon theorem, the Garden-of-Eden theorem and the invariance of uniform Bernoulli distribution under reversible cellular automata. We then describe several techniques to construct reversible cellular automata and a method to determine whether a given one-dimensional automaton is reversible. We present undecidability issues concerning reversible cellular automata and discuss three types of universality: computational universality, intrinsic universality, and physical universality. We finish with short notes about time symmetry, expansiveness, and conservation laws.
    50 schema:genre research_article
    51 schema:inLanguage en
    52 schema:isAccessibleForFree false
    53 schema:isPartOf N539ec72652234c66813886018cd8cd21
    54 Ne077a0c532bb4d8d8adfc44b8fe3ad14
    55 sg:journal.1053619
    56 schema:name Reversible Cellular Automata: From Fundamental Classical Results to Recent Developments
    57 schema:pagination 145-172
    58 schema:productId N66d13d40206b467c817095eccdeb778f
    59 N862d01cab2ed409eaad2ac283c7073f5
    60 Ncc6370a790204002a83567baf3242a82
    61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105086529
    62 https://doi.org/10.1007/s00354-018-0034-6
    63 schema:sdDatePublished 2019-04-11T10:30
    64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    65 schema:sdPublisher N4f64ef369c56485b929a825ae2dd310a
    66 schema:url https://link.springer.com/10.1007%2Fs00354-018-0034-6
    67 sgo:license sg:explorer/license/
    68 sgo:sdDataset articles
    69 rdf:type schema:ScholarlyArticle
    70 N1c80c1e7138a41b984f521fb9ea67109 rdf:first sg:person.011735452354.35
    71 rdf:rest rdf:nil
    72 N4f64ef369c56485b929a825ae2dd310a schema:name Springer Nature - SN SciGraph project
    73 rdf:type schema:Organization
    74 N539ec72652234c66813886018cd8cd21 schema:issueNumber 3
    75 rdf:type schema:PublicationIssue
    76 N66d13d40206b467c817095eccdeb778f schema:name dimensions_id
    77 schema:value pub.1105086529
    78 rdf:type schema:PropertyValue
    79 N862d01cab2ed409eaad2ac283c7073f5 schema:name readcube_id
    80 schema:value db8673f46e336ee019d1077b8afdd93e544443f34f95bd3ece547e0b02adb303
    81 rdf:type schema:PropertyValue
    82 Ncc6370a790204002a83567baf3242a82 schema:name doi
    83 schema:value 10.1007/s00354-018-0034-6
    84 rdf:type schema:PropertyValue
    85 Ne077a0c532bb4d8d8adfc44b8fe3ad14 schema:volumeNumber 36
    86 rdf:type schema:PublicationVolume
    87 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Biological Sciences
    89 rdf:type schema:DefinedTerm
    90 anzsrc-for:0601 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Biochemistry and Cell Biology
    92 rdf:type schema:DefinedTerm
    93 sg:journal.1053619 schema:issn 0288-3635
    94 1882-7055
    95 schema:name New Generation Computing
    96 rdf:type schema:Periodical
    97 sg:person.011735452354.35 schema:affiliation https://www.grid.ac/institutes/grid.1374.1
    98 schema:familyName Kari
    99 schema:givenName Jarkko
    100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011735452354.35
    101 rdf:type schema:Person
    102 sg:pub.10.1007/11505877_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004669217
    103 https://doi.org/10.1007/11505877_5
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.1007/11523468_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035438053
    106 https://doi.org/10.1007/11523468_34
    107 rdf:type schema:CreativeWork
    108 sg:pub.10.1007/978-1-4471-0129-1_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030314599
    109 https://doi.org/10.1007/978-1-4471-0129-1_6
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/978-3-319-58741-7_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086750862
    112 https://doi.org/10.1007/978-3-319-58741-7_23
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/978-3-319-58741-7_35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086750874
    115 https://doi.org/10.1007/978-3-319-58741-7_35
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/978-3-540-85238-4_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032588457
    118 https://doi.org/10.1007/978-3-540-85238-4_34
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/978-3-540-92910-9_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000675121
    121 https://doi.org/10.1007/978-3-540-92910-9_6
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/978-3-642-14034-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041394511
    124 https://doi.org/10.1007/978-3-642-14034-1
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/978-3-642-20712-9_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027023655
    127 https://doi.org/10.1007/978-3-642-20712-9_17
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/bf01201813 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011622046
    130 https://doi.org/10.1007/bf01201813
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/bf01691062 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049449230
    133 https://doi.org/10.1007/bf01691062
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/bf01857727 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032661873
    136 https://doi.org/10.1007/bf01857727
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/bfb0061728 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000307890
    139 https://doi.org/10.1007/bfb0061728
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/s10955-015-1281-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032836701
    142 https://doi.org/10.1007/s10955-015-1281-2
    143 rdf:type schema:CreativeWork
    144 sg:pub.10.1007/s11047-010-9222-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030150049
    145 https://doi.org/10.1007/s11047-010-9222-0
    146 rdf:type schema:CreativeWork
    147 sg:pub.10.1038/scientificamerican1070-120 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007582166
    148 https://doi.org/10.1038/scientificamerican1070-120
    149 rdf:type schema:CreativeWork
    150 https://app.dimensions.ai/details/publication/pub.1041394511 schema:CreativeWork
    151 https://doi.org/10.1016/0019-3577(93)90040-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001465095
    152 rdf:type schema:CreativeWork
    153 https://doi.org/10.1016/0167-2789(84)90252-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024857421
    154 rdf:type schema:CreativeWork
    155 https://doi.org/10.1016/0167-2789(84)90253-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017085534
    156 rdf:type schema:CreativeWork
    157 https://doi.org/10.1016/0167-2789(90)90185-r schema:sameAs https://app.dimensions.ai/details/publication/pub.1044244052
    158 rdf:type schema:CreativeWork
    159 https://doi.org/10.1016/0167-2789(90)90195-u schema:sameAs https://app.dimensions.ai/details/publication/pub.1010901944
    160 rdf:type schema:CreativeWork
    161 https://doi.org/10.1016/0167-2789(91)90150-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004501638
    162 rdf:type schema:CreativeWork
    163 https://doi.org/10.1016/0304-3975(95)00038-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1002866933
    164 rdf:type schema:CreativeWork
    165 https://doi.org/10.1016/j.jcss.2012.01.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041095532
    166 rdf:type schema:CreativeWork
    167 https://doi.org/10.1016/j.tcs.2004.11.021 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008892501
    168 rdf:type schema:CreativeWork
    169 https://doi.org/10.1016/j.tcs.2008.01.041 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012017670
    170 rdf:type schema:CreativeWork
    171 https://doi.org/10.1016/j.tcs.2011.02.023 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028506815
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1016/j.tcs.2011.02.024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035046025
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1016/j.tcs.2011.12.037 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041614651
    176 rdf:type schema:CreativeWork
    177 https://doi.org/10.1016/s0022-0000(05)80025-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1006334600
    178 rdf:type schema:CreativeWork
    179 https://doi.org/10.1016/s0022-0000(72)80009-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016636649
    180 rdf:type schema:CreativeWork
    181 https://doi.org/10.1016/s0022-0000(72)80013-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032327804
    182 rdf:type schema:CreativeWork
    183 https://doi.org/10.1016/s0022-0000(77)80007-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1046362897
    184 rdf:type schema:CreativeWork
    185 https://doi.org/10.1016/s0304-3975(96)00081-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012430781
    186 rdf:type schema:CreativeWork
    187 https://doi.org/10.1017/cbo9780511549755 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098679392
    188 rdf:type schema:CreativeWork
    189 https://doi.org/10.1090/conm/469/09161 schema:sameAs https://app.dimensions.ai/details/publication/pub.1089202801
    190 rdf:type schema:CreativeWork
    191 https://doi.org/10.1090/psapm/014/9961 schema:sameAs https://app.dimensions.ai/details/publication/pub.1089193116
    192 rdf:type schema:CreativeWork
    193 https://doi.org/10.1090/s0002-9939-1963-0155764-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000280146
    194 rdf:type schema:CreativeWork
    195 https://doi.org/10.1103/physrevlett.31.276 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060777564
    196 rdf:type schema:CreativeWork
    197 https://doi.org/10.1142/s0129054195000202 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062897674
    198 rdf:type schema:CreativeWork
    199 https://doi.org/10.1145/2688073.2688107 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044103794
    200 rdf:type schema:CreativeWork
    201 https://doi.org/10.1147/rd.176.0525 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063180324
    202 rdf:type schema:CreativeWork
    203 https://www.grid.ac/institutes/grid.1374.1 schema:alternateName University of Turku
    204 schema:name Department of Mathematics and Statistics, University of Turku, 20014, Turku, Finland
    205 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...