Descriptional Complexity of Winning Sets of Regular Languages

Tietueen suppeat tiedot
dc.contributor.authorMarcus P.
dc.contributor.authorTörmä I.
dc.contributor.organizationfi=matematiikan ja tilastotieteen laitos|en=Department of Mathematics and Statistics|
dc.contributor.organization-code1.2.246.10.2458963.20.46717060993
dc.converis.publication-id51315723
dc.converis.urlhttps://research.utu.fi/converis/portal/Publication/51315723
dc.date.accessioned2025-08-27T20:41:57Z
dc.date.available2025-08-27T20:41:57Z
dc.description.abstract<p>We investigate certain word-construction games with variable turn orders. In these games, Alice and Bob take turns on choosing consecutive letters of a word of fixed length, with Alice winning if the result lies in a predetermined target language. The turn orders that result in a win for Alice form a binary language that is regular whenever the target language is, and we prove some upper and lower bounds for its state complexity based on that of the target language<br /></p>
dc.format.pagerange130
dc.format.pagerange141
dc.identifier.eisbn978-3-030-62536-8
dc.identifier.isbn978-3-030-62535-1
dc.identifier.issn0302-9743
dc.identifier.jour-issn0302-9743
dc.identifier.olddbid200060
dc.identifier.oldhandle10024/183087
dc.identifier.urihttps://www.utupub.fi/handle/11111/45542
dc.identifier.urnURN:NBN:fi-fe2021042821243
dc.language.isoen
dc.okm.affiliatedauthorTörmä, Ilkka
dc.okm.discipline111 Mathematicsen_GB
dc.okm.discipline112 Statistics and probabilityen_GB
dc.okm.discipline111 Matematiikkafi_FI
dc.okm.discipline112 Tilastotiedefi_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.conferenceInternational Conference on Descriptional Complexity of Formal Systems
dc.relation.doi10.1007/978-3-030-62536-8_11
dc.relation.ispartofjournalLecture Notes in Computer Science
dc.relation.volume12442
dc.source.identifierhttps://www.utupub.fi/handle/10024/183087
dc.titleDescriptional Complexity of Winning Sets of Regular Languages
dc.title.bookDescriptional Complexity of Formal Systems
dc.year.issued2020

Tiedostot

Näytetään 1 - 1 / 1
Name:
proof.pdf
Size:
572.69 KB
Format:
Adobe Portable Document Format
Description:
Final draft
Lataa

Kokoelmat

Rinnakkaistallenteet