Solving the parity problem in one-dimensional cellular automata View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2013-09

AUTHORS

Heather Betel, Pedro P. B. de Oliveira, Paola Flocchini

ABSTRACT

The parity problem is a well-known benchmark task in various areas of computer science. Here we consider its version for one-dimensional, binary cellular automata, with periodic boundary conditions: if the initial configuration contains an odd number of 1s, the lattice should converge to all 1s; otherwise, it should converge to all 0s. Since the problem is ill-defined for even-sized lattices (which, by definition, would never be able to converge to 1), it suffices to account for odd-sized lattices only. We are interested in determining the minimal neighbourhood size that allows the problem to be solvable for any arbitrary initial configuration. On the one hand, we show that radius 2 is not sufficient, proving that there exists no radius 2 rule that can solve the parity problem, even in the simpler case of prime-sized lattices. On the other hand, we design a radius 4 rule that converges correctly for any initial configuration and formally prove its correctness. Whether or not there exists a radius 3 rule that solves the parity problem remains an open problem; however, we review recent data against a solution in radius 3, thus providing strong empirical evidence that there may not exist a radius 3 solution even for prime-sized lattices only, contrary to a recent conjecture in the literature. More... »

PAGES

323-337

References to SciGraph publications

  • 1993. Automata Network Epidemic Models in CELLULAR AUTOMATA AND COOPERATIVE SYSTEMS
  • 2009. Additive Cellular Automata in ENCYCLOPEDIA OF COMPLEXITY AND SYSTEMS SCIENCE
  • 2007-11. The computational power of population protocols in DISTRIBUTED COMPUTING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s11047-013-9374-9

    DOI

    http://dx.doi.org/10.1007/s11047-013-9374-9

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Ottawa", 
              "id": "https://www.grid.ac/institutes/grid.28046.38", 
              "name": [
                "School of Electrical Engineering and Computer Science, University of Ottawa, 800 King Edward Avenue, K1N 6N5, Ottawa, ON, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Betel", 
            "givenName": "Heather", 
            "id": "sg:person.012470366420.65", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012470366420.65"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Universidade Presbiteriana Mackenzie", 
              "id": "https://www.grid.ac/institutes/grid.412403.0", 
              "name": [
                "Faculdade de Computa\u00e7\u00e3o e Inform\u00e1tica, Universidade Presbiteriana Mackenzie, Rua da Consola\u00e7\u00e3o 896, Consola\u00e7\u00e3o, 01302-907, S\u00e3o Paulo, SP, Brazil"
              ], 
              "type": "Organization"
            }, 
            "familyName": "de Oliveira", 
            "givenName": "Pedro P. B.", 
            "id": "sg:person.015255667177.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015255667177.43"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Ottawa", 
              "id": "https://www.grid.ac/institutes/grid.28046.38", 
              "name": [
                "School of Electrical Engineering and Computer Science, University of Ottawa, 800 King Edward Avenue, K1N 6N5, Ottawa, ON, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Flocchini", 
            "givenName": "Paola", 
            "id": "sg:person.011601470625.25", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601470625.25"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/j.entcs.2009.09.017", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004626168"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-94-011-1691-6_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006877307", 
              "https://doi.org/10.1007/978-94-011-1691-6_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-94-011-1691-6_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006877307", 
              "https://doi.org/10.1007/978-94-011-1691-6_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-007-0040-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008272694", 
              "https://doi.org/10.1007/s00446-007-0040-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-007-0040-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008272694", 
              "https://doi.org/10.1007/s00446-007-0040-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.55.r2081", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009821740"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.55.r2081", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009821740"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-0-387-30440-3_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017663987", 
              "https://doi.org/10.1007/978-0-387-30440-3_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1378533.1378540", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021130488"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2009.05.004", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021957083"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2009.06.023", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022338794"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-2789(86)90237-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026577542"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.neucom.2006.07.003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030535019"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2010.11.006", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038098076"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.64.026702", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051029610"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.64.026702", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051029610"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2004.06.008", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051825580"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.57.3589", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060722130"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.57.3589", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060722130"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9780898719772", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098557268"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2013-09", 
        "datePublishedReg": "2013-09-01", 
        "description": "The parity problem is a well-known benchmark task in various areas of computer science. Here we consider its version for one-dimensional, binary cellular automata, with periodic boundary conditions: if the initial configuration contains an odd number of 1s, the lattice should converge to all 1s; otherwise, it should converge to all 0s. Since the problem is ill-defined for even-sized lattices (which, by definition, would never be able to converge to 1), it suffices to account for odd-sized lattices only. We are interested in determining the minimal neighbourhood size that allows the problem to be solvable for any arbitrary initial configuration. On the one hand, we show that radius 2 is not sufficient, proving that there exists no radius 2 rule that can solve the parity problem, even in the simpler case of prime-sized lattices. On the other hand, we design a radius 4 rule that converges correctly for any initial configuration and formally prove its correctness. Whether or not there exists a radius 3 rule that solves the parity problem remains an open problem; however, we review recent data against a solution in radius 3, thus providing strong empirical evidence that there may not exist a radius 3 solution even for prime-sized lattices only, contrary to a recent conjecture in the literature.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s11047-013-9374-9", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.5489586", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1033918", 
            "issn": [
              "1567-7818", 
              "1572-9796"
            ], 
            "name": "Natural Computing", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "12"
          }
        ], 
        "name": "Solving the parity problem in one-dimensional cellular automata", 
        "pagination": "323-337", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "dfb24e16dc22a6401adf0fb36ee8fe4b4e3b6c5c398222889df33183e21d7d5c"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s11047-013-9374-9"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1046959061"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s11047-013-9374-9", 
          "https://app.dimensions.ai/details/publication/pub.1046959061"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T02:02", 
        "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/0000000001_0000000264/records_8700_00000515.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2Fs11047-013-9374-9"
      }
    ]
     

    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/s11047-013-9374-9'

    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/s11047-013-9374-9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11047-013-9374-9'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11047-013-9374-9'


     

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

    128 TRIPLES      21 PREDICATES      42 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s11047-013-9374-9 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Nd37bd6644c80435b94fb1750a7f4c3a2
    4 schema:citation sg:pub.10.1007/978-0-387-30440-3_4
    5 sg:pub.10.1007/978-94-011-1691-6_4
    6 sg:pub.10.1007/s00446-007-0040-2
    7 https://doi.org/10.1016/0167-2789(86)90237-x
    8 https://doi.org/10.1016/j.entcs.2009.09.017
    9 https://doi.org/10.1016/j.neucom.2006.07.003
    10 https://doi.org/10.1016/j.tcs.2004.06.008
    11 https://doi.org/10.1016/j.tcs.2009.05.004
    12 https://doi.org/10.1016/j.tcs.2009.06.023
    13 https://doi.org/10.1016/j.tcs.2010.11.006
    14 https://doi.org/10.1103/physreve.55.r2081
    15 https://doi.org/10.1103/physreve.57.3589
    16 https://doi.org/10.1103/physreve.64.026702
    17 https://doi.org/10.1137/1.9780898719772
    18 https://doi.org/10.1145/1378533.1378540
    19 schema:datePublished 2013-09
    20 schema:datePublishedReg 2013-09-01
    21 schema:description The parity problem is a well-known benchmark task in various areas of computer science. Here we consider its version for one-dimensional, binary cellular automata, with periodic boundary conditions: if the initial configuration contains an odd number of 1s, the lattice should converge to all 1s; otherwise, it should converge to all 0s. Since the problem is ill-defined for even-sized lattices (which, by definition, would never be able to converge to 1), it suffices to account for odd-sized lattices only. We are interested in determining the minimal neighbourhood size that allows the problem to be solvable for any arbitrary initial configuration. On the one hand, we show that radius 2 is not sufficient, proving that there exists no radius 2 rule that can solve the parity problem, even in the simpler case of prime-sized lattices. On the other hand, we design a radius 4 rule that converges correctly for any initial configuration and formally prove its correctness. Whether or not there exists a radius 3 rule that solves the parity problem remains an open problem; however, we review recent data against a solution in radius 3, thus providing strong empirical evidence that there may not exist a radius 3 solution even for prime-sized lattices only, contrary to a recent conjecture in the literature.
    22 schema:genre research_article
    23 schema:inLanguage en
    24 schema:isAccessibleForFree false
    25 schema:isPartOf N2f8ba89625cc4c72a1c207fa825a95cf
    26 Ne1caa5b731724a85a4b9ec2adbe290c7
    27 sg:journal.1033918
    28 schema:name Solving the parity problem in one-dimensional cellular automata
    29 schema:pagination 323-337
    30 schema:productId N38f326d2ae8149f797179270223e3e52
    31 N5cecbb36d3524f03a59a3bc65a4ed83c
    32 N8e0c74825cf144f0ab967542a53ad900
    33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046959061
    34 https://doi.org/10.1007/s11047-013-9374-9
    35 schema:sdDatePublished 2019-04-11T02:02
    36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    37 schema:sdPublisher Nbc2b69d1c6884c55a1ac72b8c3bd8474
    38 schema:url http://link.springer.com/10.1007%2Fs11047-013-9374-9
    39 sgo:license sg:explorer/license/
    40 sgo:sdDataset articles
    41 rdf:type schema:ScholarlyArticle
    42 N2f8ba89625cc4c72a1c207fa825a95cf schema:issueNumber 3
    43 rdf:type schema:PublicationIssue
    44 N38f326d2ae8149f797179270223e3e52 schema:name readcube_id
    45 schema:value dfb24e16dc22a6401adf0fb36ee8fe4b4e3b6c5c398222889df33183e21d7d5c
    46 rdf:type schema:PropertyValue
    47 N44a72a8630154904a4a06a53e1445851 rdf:first sg:person.015255667177.43
    48 rdf:rest Nb9a6fa7658ac4f7d8a74470163824d61
    49 N5cecbb36d3524f03a59a3bc65a4ed83c schema:name dimensions_id
    50 schema:value pub.1046959061
    51 rdf:type schema:PropertyValue
    52 N8e0c74825cf144f0ab967542a53ad900 schema:name doi
    53 schema:value 10.1007/s11047-013-9374-9
    54 rdf:type schema:PropertyValue
    55 Nb9a6fa7658ac4f7d8a74470163824d61 rdf:first sg:person.011601470625.25
    56 rdf:rest rdf:nil
    57 Nbc2b69d1c6884c55a1ac72b8c3bd8474 schema:name Springer Nature - SN SciGraph project
    58 rdf:type schema:Organization
    59 Nd37bd6644c80435b94fb1750a7f4c3a2 rdf:first sg:person.012470366420.65
    60 rdf:rest N44a72a8630154904a4a06a53e1445851
    61 Ne1caa5b731724a85a4b9ec2adbe290c7 schema:volumeNumber 12
    62 rdf:type schema:PublicationVolume
    63 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    64 schema:name Mathematical Sciences
    65 rdf:type schema:DefinedTerm
    66 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Pure Mathematics
    68 rdf:type schema:DefinedTerm
    69 sg:grant.5489586 http://pending.schema.org/fundedItem sg:pub.10.1007/s11047-013-9374-9
    70 rdf:type schema:MonetaryGrant
    71 sg:journal.1033918 schema:issn 1567-7818
    72 1572-9796
    73 schema:name Natural Computing
    74 rdf:type schema:Periodical
    75 sg:person.011601470625.25 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
    76 schema:familyName Flocchini
    77 schema:givenName Paola
    78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601470625.25
    79 rdf:type schema:Person
    80 sg:person.012470366420.65 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
    81 schema:familyName Betel
    82 schema:givenName Heather
    83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012470366420.65
    84 rdf:type schema:Person
    85 sg:person.015255667177.43 schema:affiliation https://www.grid.ac/institutes/grid.412403.0
    86 schema:familyName de Oliveira
    87 schema:givenName Pedro P. B.
    88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015255667177.43
    89 rdf:type schema:Person
    90 sg:pub.10.1007/978-0-387-30440-3_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017663987
    91 https://doi.org/10.1007/978-0-387-30440-3_4
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1007/978-94-011-1691-6_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006877307
    94 https://doi.org/10.1007/978-94-011-1691-6_4
    95 rdf:type schema:CreativeWork
    96 sg:pub.10.1007/s00446-007-0040-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008272694
    97 https://doi.org/10.1007/s00446-007-0040-2
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1016/0167-2789(86)90237-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1026577542
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1016/j.entcs.2009.09.017 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004626168
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1016/j.neucom.2006.07.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030535019
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/j.tcs.2004.06.008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051825580
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1016/j.tcs.2009.05.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021957083
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1016/j.tcs.2009.06.023 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022338794
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1016/j.tcs.2010.11.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038098076
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1103/physreve.55.r2081 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009821740
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1103/physreve.57.3589 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060722130
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1103/physreve.64.026702 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051029610
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1137/1.9780898719772 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098557268
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1145/1378533.1378540 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021130488
    122 rdf:type schema:CreativeWork
    123 https://www.grid.ac/institutes/grid.28046.38 schema:alternateName University of Ottawa
    124 schema:name School of Electrical Engineering and Computer Science, University of Ottawa, 800 King Edward Avenue, K1N 6N5, Ottawa, ON, Canada
    125 rdf:type schema:Organization
    126 https://www.grid.ac/institutes/grid.412403.0 schema:alternateName Universidade Presbiteriana Mackenzie
    127 schema:name Faculdade de Computação e Informática, Universidade Presbiteriana Mackenzie, Rua da Consolação 896, Consolação, 01302-907, São Paulo, SP, Brazil
    128 rdf:type schema:Organization
     




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


    ...