Subshifts, MSO Logic, and Collapsing Hierarchies

Tietueen suppeat tiedot
dc.contributor.authorIlkka Törmä
dc.contributor.organizationfi=matematiikka|en=Mathematics|
dc.contributor.organization-code1.2.246.10.2458963.20.41687507875
dc.converis.publication-id2538826
dc.converis.urlhttps://research.utu.fi/converis/portal/Publication/2538826
dc.date.accessioned2022-10-28T13:30:44Z
dc.date.available2022-10-28T13:30:44Z
dc.description.abstract<p> We use monadic second-order logic to define two-dimensional subshifts, or sets of colorings of the infinite plane. We present a natural family of quantifier alternation hierarchies, and show that they all collapse to the third level. In particular, this solves an open problem of [Jeandel &amp; Theyssier 2013]. The results are in stark contrast with picture languages, where such hierarchies are usually infinite.</p>
dc.format.pagerange111
dc.format.pagerange122
dc.identifier.issn0302-9743
dc.identifier.jour-issn0302-9743
dc.identifier.olddbid182594
dc.identifier.oldhandle10024/165688
dc.identifier.urihttps://www.utupub.fi/handle/11111/39932
dc.identifier.urlhttp://link.springer.com/chapter/10.1007/978-3-662-44602-7_10
dc.identifier.urnURN:NBN:fi-fe2021042714687
dc.language.isoen
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.countryGermanyen_GB
dc.publisher.countrySaksafi_FI
dc.publisher.country-codeDE
dc.publisher.placeBerlin
dc.relation.conferenceIFIP international conference on theoretical computer science
dc.relation.doi10.1007/978-3-662-44602-7_10
dc.relation.ispartofjournalLecture Notes in Computer Science
dc.relation.ispartofseriesLecture Notes in Computer Science
dc.relation.volume1
dc.relation.volume8705
dc.source.identifierhttps://www.utupub.fi/handle/10024/165688
dc.titleSubshifts, MSO Logic, and Collapsing Hierarchies
dc.title.bookTheoretical Computer Science
dc.year.issued2014

Tiedostot

Näytetään 1 - 1 / 1
Name:
submission.pdf
Size:
405.63 KB
Format:
Adobe Portable Document Format
Description:
Author's post-print- The final publication is available at link.springer.com
Lataa

Kokoelmat

Rinnakkaistallenteet