Group-Walking Automata

Tietueen suppeat tiedot
dc.contributor.authorVille Salo
dc.contributor.authorIlkka Törmä
dc.contributor.organizationfi=matematiikka|en=Mathematics|
dc.contributor.organization-code1.2.246.10.2458963.20.41687507875
dc.converis.publication-id3179812
dc.converis.urlhttps://research.utu.fi/converis/portal/Publication/3179812
dc.date.accessioned2022-10-27T11:50:57Z
dc.date.available2022-10-27T11:50:57Z
dc.description.abstract<p> In the setting of symbolic dynamics on discrete finitely generated infinite groups, we define a model of multi-headed finite automata that walk on Cayley graphs, and use it to define subshifts. We characterize the torsion groups (also known as periodic groups) as those on which the group-walking automata are strictly weaker than Turing machines.</p>
dc.format.pagerange224
dc.format.pagerange237
dc.identifier.eisbn978-3-662-47221-7
dc.identifier.isbn978-3-662-47220-0
dc.identifier.issn0302-9743
dc.identifier.jour-issn0302-9743
dc.identifier.olddbid172265
dc.identifier.oldhandle10024/155359
dc.identifier.urihttps://www.utupub.fi/handle/11111/30050
dc.identifier.urlhttp://link.springer.com/chapter/10.1007%2F978-3-662-47221-7_17
dc.identifier.urnURN:NBN:fi-fe2021042715099
dc.language.isoen
dc.okm.affiliatedauthorSalo, Ville
dc.okm.affiliatedauthorTörmä, Ilkka
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.internationalcopublicationnot an international co-publication
dc.okm.internationalityInternational publication
dc.okm.typeA4 Conference Article
dc.publisher.placeBerlin
dc.relation.conferenceInternational Workshop on Cellular Automata and Discrete Complex Systems
dc.relation.doi10.1007/978-3-662-47221-7_17
dc.relation.ispartofjournalLecture Notes in Computer Science
dc.relation.ispartofseriesLecture Notes in Computer Science
dc.relation.volume9099
dc.source.identifierhttps://www.utupub.fi/handle/10024/155359
dc.titleGroup-Walking Automata
dc.title.bookCellular Automata and Discrete Complex Systems
dc.year.issued2015

Tiedostot

Näytetään 1 - 1 / 1
Name:
GroupWalkingAutomataFixed.pdf
Size:
381.28 KB
Format:
Adobe Portable Document Format
Description:
Author's Post-print
Lataa

Kokoelmat

Rinnakkaistallenteet