A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Descriptional Complexity of Winning Sets of Regular Languages
Tekijät: Marcus P., Törmä I.
Toimittaja: Galina Jirásková, Giovanni Pighizzini
Konferenssin vakiintunut nimi: International Conference on Descriptional Complexity of Formal Systems
Kustantaja: Springer Science and Business Media Deutschland GmbH
Julkaisuvuosi: 2020
Lehti: Lecture Notes in Computer Science
Kokoomateoksen nimi: Descriptional Complexity of Formal Systems
Tietokannassa oleva lehden nimi: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vuosikerta: 12442
Aloitussivu: 130
Lopetussivu: 141
ISBN: 978-3-030-62535-1
eISBN: 978-3-030-62536-8
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-030-62536-8_11
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/51315723
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
Avainsanat:
Winning sets
Ladattava julkaisu This is an electronic reprint of the original article. |  |
