A4 Refereed article in a conference publication
Descriptional Complexity of Winning Sets of Regular Languages
Authors: Marcus P., Törmä I.
Editors: Galina Jirásková, Giovanni Pighizzini
Conference name: International Conference on Descriptional Complexity of Formal Systems
Publisher: Springer Science and Business Media Deutschland GmbH
Publication year: 2020
Journal: Lecture Notes in Computer Science
Book title : Descriptional Complexity of Formal Systems
Journal name in source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume: 12442
First page : 130
Last page: 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
Self-archived copy’s web address: 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
Keywords:
Winning sets
Downloadable publication This is an electronic reprint of the original article. |  |
