A4 Vertaisarvioitu artikkeli konferenssijulkaisussa

Descriptional Complexity of Winning Sets of Regular Languages




TekijätMarcus P., Törmä I.

ToimittajaGalina Jirásková, Giovanni Pighizzini

Konferenssin vakiintunut nimiInternational Conference on Descriptional Complexity of Formal Systems

KustantajaSpringer Science and Business Media Deutschland GmbH

Julkaisuvuosi2020

JournalLecture Notes in Computer Science

Kokoomateoksen nimiDescriptional Complexity of Formal Systems

Tietokannassa oleva lehden nimiLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Vuosikerta12442

Aloitussivu130

Lopetussivu141

ISBN978-3-030-62535-1

eISBN978-3-030-62536-8

ISSN0302-9743

DOIhttps://doi.org/10.1007/978-3-030-62536-8_11

Rinnakkaistallenteen osoitehttps://research.utu.fi/converis/portal/detail/Publication/51315723


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


Ladattava julkaisu

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 22:43