Multidimensional Tilings and MSO Logic

Tietueen suppeat tiedot
dc.contributor.authorPallen, Rémi
dc.contributor.authorTörmä, Ilkka
dc.contributor.organizationfi=matematiikka|en=Mathematics|
dc.contributor.organization-code1.2.246.10.2458963.20.41687507875
dc.converis.publication-id499418099
dc.converis.urlhttps://research.utu.fi/converis/portal/Publication/499418099
dc.date.accessioned2026-01-21T14:48:38Z
dc.date.available2026-01-21T14:48:38Z
dc.description.abstractWe define sets of coulourings of the infinite discrete plane using monadic second order (MSO) formulas. We determine the complexity of deciding whether such a formula defines a subshift, parametrized on the quantifier alternation complexity of the formula. We also study the complexities of languages of MSO-definable sets, giving either an exact classification or upper and lower bounds for each quantifier alternation class.
dc.embargo.lift2026-06-20
dc.format.pagerange365
dc.format.pagerange379
dc.identifier.eisbn978-3-031-95908-0
dc.identifier.isbn978-3-031-95907-3
dc.identifier.issn0302-9743
dc.identifier.jour-issn0302-9743
dc.identifier.olddbid213729
dc.identifier.oldhandle10024/196747
dc.identifier.urihttps://www.utupub.fi/handle/11111/55834
dc.identifier.urlhttps://doi.org/10.1007/978-3-031-95908-0_26
dc.identifier.urnURN:NBN:fi-fe202601215915
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.internationalcopublicationinternational co-publication
dc.okm.internationalityInternational publication
dc.okm.typeA4 Conference Article
dc.publisher.countrySwitzerlanden_GB
dc.publisher.countrySveitsifi_FI
dc.publisher.country-codeCH
dc.relation.conferenceComputability in Europe
dc.relation.doi10.1007/978-3-031-95908-0_26
dc.relation.ispartofjournalLecture Notes in Computer Science
dc.relation.volume15764
dc.source.identifierhttps://www.utupub.fi/handle/10024/196747
dc.titleMultidimensional Tilings and MSO Logic
dc.title.bookCrossroads of Computability and Logic: Insights, Inspirations, and Innovations: 21st Conference on Computability in Europe, CiE 2025, Lisbon, Portugal, July 14–18, 2025, Proceedings
dc.year.issued2025

Tiedostot

Kokoelmat

Rinnakkaistallenteet