PSPACE-completeness of majority automata networks

Tietueen suppeat tiedot
dc.contributor.authorEric Goles
dc.contributor.authorPedro Montealegre
dc.contributor.authorVille Salo
dc.contributor.authorIlkka Törmä
dc.contributor.organizationfi=Turun tietotekniikan tutkimuskeskus TUCS|en=Turku Centre for Computer Science (TUCS)|
dc.contributor.organizationfi=matematiikka|en=Mathematics|
dc.contributor.organization-code1.2.246.10.2458963.20.41687507875
dc.converis.publication-id2545782
dc.converis.urlhttps://research.utu.fi/converis/portal/Publication/2545782
dc.date.accessioned2022-10-28T13:47:38Z
dc.date.available2022-10-28T13:47:38Z
dc.description.abstract<p> We study the dynamics of majority automata networks when the vertices are updated according to a block sequential updating scheme. In particular, we show that the complexity of the problem of predicting an eventual state change in some vertex, given an initial configuration, is PSPACE-complete. (C) 2015 Elsevier B.V. All rights reserved.</p>
dc.format.pagerange118
dc.format.pagerange128
dc.identifier.eissn1879-2294
dc.identifier.jour-issn0304-3975
dc.identifier.olddbid184363
dc.identifier.oldhandle10024/167457
dc.identifier.urihttps://www.utupub.fi/handle/11111/41787
dc.identifier.urlhttp://www.sciencedirect.com/science/article/pii/S0304397515008294?np=y
dc.identifier.urnURN:NBN:fi-fe2021042714692
dc.language.isoen
dc.okm.affiliatedauthorSalo, Ville
dc.okm.affiliatedauthorTörmä, Ilkka
dc.okm.affiliatedauthorDataimport, Turun tietotekniikan tutkimuskeskus TUCS
dc.okm.discipline111 Mathematicsen_GB
dc.okm.discipline113 Computer and information sciencesen_GB
dc.okm.discipline111 Matematiikkafi_FI
dc.okm.discipline113 Tietojenkäsittely ja informaatiotieteetfi_FI
dc.okm.internationalcopublicationinternational co-publication
dc.okm.internationalityInternational publication
dc.okm.typeA1 ScientificArticle
dc.publisherELSEVIER SCIENCE BV
dc.publisher.countryNetherlandsen_GB
dc.publisher.countryAlankomaatfi_FI
dc.publisher.country-codeNL
dc.relation.doi10.1016/j.tcs.2015.09.014
dc.relation.ispartofjournalTheoretical Computer Science
dc.relation.issuePart 1
dc.relation.volume609
dc.source.identifierhttps://www.utupub.fi/handle/10024/167457
dc.titlePSPACE-completeness of majority automata networks
dc.year.issued2016

Tiedostot

Näytetään 1 - 1 / 1
Name:
1501.03992v1.pdf
Size:
247.32 KB
Format:
Adobe Portable Document Format
Lataa

Kokoelmat

Rinnakkaistallenteet