μ-Limit sets of cellular automata from a computational complexity perspective

•We characterize the set of μ-limit sets of cellular automata.•We prove that the language of these limit sets can be Σ3-complete.•We prove a Rice theorem for μ-limit sets of cellular automata. This paper concerns μ-limit sets of cellular automata: sets of configurations made of words whose probabili...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2015-12, Vol.81 (8), p.1623-1647
Main Authors: Boyer, L., Delacourt, M., Poupet, V., Sablik, M., Theyssier, G.
Format: Article
Language:English
Subjects:
Arithmetical hierarchy
Cellular automata
Computer Science
Discrete Mathematics
Rice theorem
μ-Limit sets
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c448t-28f47e5b6dcd6cc08b55ca3cf49effcbf1d32736254d06153de50160f872a81f3
cites cdi_FETCH-LOGICAL-c448t-28f47e5b6dcd6cc08b55ca3cf49effcbf1d32736254d06153de50160f872a81f3
container_end_page 1647
container_issue 8
container_start_page 1623
container_title Journal of computer and system sciences
container_volume 81
creator Boyer, L.
Delacourt, M.
Poupet, V.
Sablik, M.
Theyssier, G.
description •We characterize the set of μ-limit sets of cellular automata.•We prove that the language of these limit sets can be Σ3-complete.•We prove a Rice theorem for μ-limit sets of cellular automata. This paper concerns μ-limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial μ-random configuration. More precisely, we investigate the computational complexity of these sets and of related decision problems. Main results: first, μ-limit sets can have a Σ30-hard language, second, they can contain only α-complex configurations, third, any non-trivial property concerning them is at least Π30-hard. We prove complexity upper bounds, study restrictions of these questions to particular classes of CA, and different types of (non-)convergence of the measure of a word during the evolution.
doi_str_mv 10.1016/j.jcss.2015.05.004
format article
fullrecord <record><control><sourceid>hal_cross</sourceid><recordid>TN_cdi_hal_primary_oai_HAL_hal_00866094v2</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0022000015000616</els_id><sourcerecordid>oai_HAL_hal_00866094v2</sourcerecordid><originalsourceid>FETCH-LOGICAL-c448t-28f47e5b6dcd6cc08b55ca3cf49effcbf1d32736254d06153de50160f872a81f3</originalsourceid><addsrcrecordid>eNp9kMFKxDAQhoMouK6-gKdcPbRO0iTtgpdlUVcoetFzyKYJprTbkmQX9918Bp_J1BWPDj8MM8w38P8IXRPICRBx2-atDiGnQHgOScBO0IzAAjJaUnaKZgCUZpDqHF2E0AIQwkUxQ89fn1ntehdxMDHgwWJtum7XKY_VLg69igpbP_RYYT304y6q6Iat6n6mzny4eMCj8WE0Orq9uURnVnXBXP32OXp7uH9drbP65fFptawzzVgVM1pZVhq-EY1uhNZQbTjXqtCWLYy1emNJU9CyEJSzBgThRWN4sgm2KqmqiC3m6Ob49111cvSuV_4gB-XkelnLaQdQCQELtqfplh5vtR9C8Mb-AQTklJ5s5ZSenNKTkAQsQXdHyCQXe2e8DNqZrTaN88mqbAb3H_4NZzZ6CA</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>μ-Limit sets of cellular automata from a computational complexity perspective</title><source>Elsevier</source><creator>Boyer, L. ; Delacourt, M. ; Poupet, V. ; Sablik, M. ; Theyssier, G.</creator><creatorcontrib>Boyer, L. ; Delacourt, M. ; Poupet, V. ; Sablik, M. ; Theyssier, G.</creatorcontrib><description>•We characterize the set of μ-limit sets of cellular automata.•We prove that the language of these limit sets can be Σ3-complete.•We prove a Rice theorem for μ-limit sets of cellular automata. This paper concerns μ-limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial μ-random configuration. More precisely, we investigate the computational complexity of these sets and of related decision problems. Main results: first, μ-limit sets can have a Σ30-hard language, second, they can contain only α-complex configurations, third, any non-trivial property concerning them is at least Π30-hard. We prove complexity upper bounds, study restrictions of these questions to particular classes of CA, and different types of (non-)convergence of the measure of a word during the evolution.</description><identifier>ISSN: 0022-0000</identifier><identifier>EISSN: 1090-2724</identifier><identifier>DOI: 10.1016/j.jcss.2015.05.004</identifier><language>eng</language><publisher>Elsevier Inc</publisher><subject>Arithmetical hierarchy ; Cellular automata ; Computer Science ; Discrete Mathematics ; Rice theorem ; μ-Limit sets</subject><ispartof>Journal of computer and system sciences, 2015-12, Vol.81 (8), p.1623-1647</ispartof><rights>2015 Elsevier Inc.</rights><rights>Distributed under a Creative Commons Attribution 4.0 International License</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c448t-28f47e5b6dcd6cc08b55ca3cf49effcbf1d32736254d06153de50160f872a81f3</citedby><cites>FETCH-LOGICAL-c448t-28f47e5b6dcd6cc08b55ca3cf49effcbf1d32736254d06153de50160f872a81f3</cites><orcidid>0000-0001-5158-4606 ; 0000-0002-1375-1706 ; 0000-0003-1944-4915</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>230,314,780,784,885,27924,27925</link.rule.ids><backlink>$$Uhttps://hal.science/hal-00866094$$DView record in HAL$$Hfree_for_read</backlink></links><search><creatorcontrib>Boyer, L.</creatorcontrib><creatorcontrib>Delacourt, M.</creatorcontrib><creatorcontrib>Poupet, V.</creatorcontrib><creatorcontrib>Sablik, M.</creatorcontrib><creatorcontrib>Theyssier, G.</creatorcontrib><title>μ-Limit sets of cellular automata from a computational complexity perspective</title><title>Journal of computer and system sciences</title><description>•We characterize the set of μ-limit sets of cellular automata.•We prove that the language of these limit sets can be Σ3-complete.•We prove a Rice theorem for μ-limit sets of cellular automata. This paper concerns μ-limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial μ-random configuration. More precisely, we investigate the computational complexity of these sets and of related decision problems. Main results: first, μ-limit sets can have a Σ30-hard language, second, they can contain only α-complex configurations, third, any non-trivial property concerning them is at least Π30-hard. We prove complexity upper bounds, study restrictions of these questions to particular classes of CA, and different types of (non-)convergence of the measure of a word during the evolution.</description><subject>Arithmetical hierarchy</subject><subject>Cellular automata</subject><subject>Computer Science</subject><subject>Discrete Mathematics</subject><subject>Rice theorem</subject><subject>μ-Limit sets</subject><issn>0022-0000</issn><issn>1090-2724</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2015</creationdate><recordtype>article</recordtype><recordid>eNp9kMFKxDAQhoMouK6-gKdcPbRO0iTtgpdlUVcoetFzyKYJprTbkmQX9918Bp_J1BWPDj8MM8w38P8IXRPICRBx2-atDiGnQHgOScBO0IzAAjJaUnaKZgCUZpDqHF2E0AIQwkUxQ89fn1ntehdxMDHgwWJtum7XKY_VLg69igpbP_RYYT304y6q6Iat6n6mzny4eMCj8WE0Orq9uURnVnXBXP32OXp7uH9drbP65fFptawzzVgVM1pZVhq-EY1uhNZQbTjXqtCWLYy1emNJU9CyEJSzBgThRWN4sgm2KqmqiC3m6Ob49111cvSuV_4gB-XkelnLaQdQCQELtqfplh5vtR9C8Mb-AQTklJ5s5ZSenNKTkAQsQXdHyCQXe2e8DNqZrTaN88mqbAb3H_4NZzZ6CA</recordid><startdate>20151201</startdate><enddate>20151201</enddate><creator>Boyer, L.</creator><creator>Delacourt, M.</creator><creator>Poupet, V.</creator><creator>Sablik, M.</creator><creator>Theyssier, G.</creator><general>Elsevier Inc</general><general>Elsevier</general><scope>6I.</scope><scope>AAFTH</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>1XC</scope><scope>VOOES</scope><orcidid>https://orcid.org/0000-0001-5158-4606</orcidid><orcidid>https://orcid.org/0000-0002-1375-1706</orcidid><orcidid>https://orcid.org/0000-0003-1944-4915</orcidid></search><sort><creationdate>20151201</creationdate><title>μ-Limit sets of cellular automata from a computational complexity perspective</title><author>Boyer, L. ; Delacourt, M. ; Poupet, V. ; Sablik, M. ; Theyssier, G.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c448t-28f47e5b6dcd6cc08b55ca3cf49effcbf1d32736254d06153de50160f872a81f3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2015</creationdate><topic>Arithmetical hierarchy</topic><topic>Cellular automata</topic><topic>Computer Science</topic><topic>Discrete Mathematics</topic><topic>Rice theorem</topic><topic>μ-Limit sets</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Boyer, L.</creatorcontrib><creatorcontrib>Delacourt, M.</creatorcontrib><creatorcontrib>Poupet, V.</creatorcontrib><creatorcontrib>Sablik, M.</creatorcontrib><creatorcontrib>Theyssier, G.</creatorcontrib><collection>ScienceDirect Open Access Titles</collection><collection>Elsevier:ScienceDirect:Open Access</collection><collection>CrossRef</collection><collection>Hyper Article en Ligne (HAL)</collection><collection>Hyper Article en Ligne (HAL) (Open Access)</collection><jtitle>Journal of computer and system sciences</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Boyer, L.</au><au>Delacourt, M.</au><au>Poupet, V.</au><au>Sablik, M.</au><au>Theyssier, G.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>μ-Limit sets of cellular automata from a computational complexity perspective</atitle><jtitle>Journal of computer and system sciences</jtitle><date>2015-12-01</date><risdate>2015</risdate><volume>81</volume><issue>8</issue><spage>1623</spage><epage>1647</epage><pages>1623-1647</pages><issn>0022-0000</issn><eissn>1090-2724</eissn><abstract>•We characterize the set of μ-limit sets of cellular automata.•We prove that the language of these limit sets can be Σ3-complete.•We prove a Rice theorem for μ-limit sets of cellular automata. This paper concerns μ-limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial μ-random configuration. More precisely, we investigate the computational complexity of these sets and of related decision problems. Main results: first, μ-limit sets can have a Σ30-hard language, second, they can contain only α-complex configurations, third, any non-trivial property concerning them is at least Π30-hard. We prove complexity upper bounds, study restrictions of these questions to particular classes of CA, and different types of (non-)convergence of the measure of a word during the evolution.</abstract><pub>Elsevier Inc</pub><doi>10.1016/j.jcss.2015.05.004</doi><tpages>25</tpages><orcidid>https://orcid.org/0000-0001-5158-4606</orcidid><orcidid>https://orcid.org/0000-0002-1375-1706</orcidid><orcidid>https://orcid.org/0000-0003-1944-4915</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0022-0000
ispartof Journal of computer and system sciences, 2015-12, Vol.81 (8), p.1623-1647
issn 0022-0000
1090-2724
language eng
recordid cdi_hal_primary_oai_HAL_hal_00866094v2
source Elsevier
subjects Arithmetical hierarchy
Cellular automata
Computer Science
Discrete Mathematics
Rice theorem
μ-Limit sets
title μ-Limit sets of cellular automata from a computational complexity perspective
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T16%3A47%3A20IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-hal_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=%CE%BC-Limit%20sets%20of%20cellular%20automata%20from%20a%20computational%20complexity%20perspective&rft.jtitle=Journal%20of%20computer%20and%20system%20sciences&rft.au=Boyer,%20L.&rft.date=2015-12-01&rft.volume=81&rft.issue=8&rft.spage=1623&rft.epage=1647&rft.pages=1623-1647&rft.issn=0022-0000&rft.eissn=1090-2724&rft_id=info:doi/10.1016/j.jcss.2015.05.004&rft_dat=%3Chal_cross%3Eoai_HAL_hal_00866094v2%3C/hal_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c448t-28f47e5b6dcd6cc08b55ca3cf49effcbf1d32736254d06153de50160f872a81f3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true