arXiv
Open Access
2020
Descriptional Complexity of Winning Sets of Regular Languages
Pierre Marcus
Ilkka Törmä
Abstrak
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.
Topik & Kata Kunci
Penulis (2)
P
Pierre Marcus
I
Ilkka Törmä
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2020
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓