Descriptional Complexity of Winning Sets of Regular Languages
: Marcus P., Törmä I.
: Galina Jirásková, Giovanni Pighizzini
: International Conference on Descriptional Complexity of Formal Systems
Publisher: Springer Science and Business Media Deutschland GmbH
: 2020
: Lecture Notes in Computer Science
: Descriptional Complexity of Formal Systems
: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
: 12442
: 130
: 141
: 978-3-030-62535-1
: 978-3-030-62536-8
: 0302-9743
DOI: https://doi.org/10.1007/978-3-030-62536-8_11
: 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
