Descriptional Complexity of Winning Sets of Regular Languages
Törmä I.; Marcus P.
Descriptional Complexity of Winning Sets of Regular Languages
Törmä I.
Marcus P.
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2021042821243
https://urn.fi/URN:NBN:fi-fe2021042821243
Tiivistelmä
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
Kokoelmat
- Rinnakkaistallenteet [19206]