论文标题
普通语言获胜集的描述复杂性
Descriptional Complexity of Winning Sets of Regular Languages
论文作者
论文摘要
我们调查了具有可变转订单的某些单词构建游戏。在这些游戏中，爱丽丝（Alice）和鲍勃（Bob）轮流选择连续的固定长度字母，如果结果以预定的目标语言为单位，则爱丽丝（Alice）获胜。导致爱丽丝赢得胜利的转弯命令形成了一种二进制语言，每当目标语言是常规的，我们根据目标语言的状态复杂性证明了其状态复杂性的某些上限和下限。
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.
