What Can Be Verified Locally?

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorBalliu, Alkida
dc.contributor.authorD'Angelo, Gianlorenzo
dc.contributor.authorFraigniaud, Pierre
dc.contributor.authorOlivetti, Dennis
dc.contributor.departmentDepartment of Computer Science
dc.contributor.departmentGran Sasso Science Institute
dc.contributor.departmentCNRS
dc.date.accessioned2018-12-10T10:30:01Z
dc.date.available2018-12-10T10:30:01Z
dc.date.embargoinfo:eu-repo/date/embargoEnd/2020-08-13
dc.date.issued2018
dc.description.abstractIn the framework of distributed network computing, it is known that not all Turing-decidable predicates on labeled networks can be decided locally whenever the computing entities are Turing machines (TM). This holds even if nodes are running non-deterministic Turing machines (NTM). In contrast, we show that every Turing-decidable predicate on labeled networks can be decided locally if nodes are running alternating Turing machines (ATM). More specifically, we show that, for every such predicate, there is a local algorithm for ATMs, with at most two alternations, that decides whether the actual labeled network satisfies that predicate. To this aim, we define a hierarchy of classes of decision tasks, where the lowest level contains tasks solvable with TMs, the first level those solvable with NTMs, and the level k>1 contains those tasks solvable with ATMs with k-1 alternations. We characterize the entire hierarchy, and show that it collapses in the second level.en
dc.description.versionPeer revieweden
dc.format.extent106-120
dc.format.mimetypeapplication/pdf
dc.identifier.citationBalliu , A , D'Angelo , G , Fraigniaud , P & Olivetti , D 2018 , ' What Can Be Verified Locally? ' , JOURNAL OF COMPUTER AND SYSTEM SCIENCES , vol. 97 , pp. 106-120 . https://doi.org/10.1016/j.jcss.2018.05.004en
dc.identifier.doi10.1016/j.jcss.2018.05.004
dc.identifier.issn0022-0000
dc.identifier.otherPURE UUID: c737011b-6839-445e-83d3-5d41997c2a9c
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/c737011b-6839-445e-83d3-5d41997c2a9c
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/29691373/SCI_Balliu_What_Can_Be_Verified_JCSS.pdf
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/35266
dc.identifier.urnURN:NBN:fi:aalto-201812106281
dc.language.isoenen
dc.relation.ispartofseriesJOURNAL OF COMPUTER AND SYSTEM SCIENCESen
dc.relation.ispartofseriesVolume 97en
dc.rightsopenAccessen
dc.subject.keywordDistributed computing
dc.subject.keywordDecision problems
dc.subject.keywordLocal model
dc.titleWhat Can Be Verified Locally?en
dc.typeA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessäfi
Files