Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

How to Play Optimally for Regular Objectives?

Uproszczony widok
dc.abstract.enThis paper studies two-player zero-sum games played on graphs and makes contributions toward the following question: given an objective, how much memory is required to play optimally for that objective? We study regular objectives, where the goal of one of the two players is that eventually the sequence of colors along the play belongs to some regular language of finite words. We obtain different characterizations of the chromatic memory requirements for such objectives for both players, from which we derive complexity-theoretic statements: deciding whether there exist small memory structures sufficient to play optimally is NP-complete for both players. Some of our characterization results apply to a more general class of objectives: topologically closed and topologically open sets.
dc.affiliationUniwersytet Warszawski
dc.conference.countryNiemcy
dc.conference.datefinish2023-07-14
dc.conference.datestart2023-07-10
dc.conference.placePadeborn
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesshortcutICALP
dc.conference.shortcutICALP 2023
dc.conference.weblinkhttps://icalp2023.cs.upb.de/
dc.contributor.authorVandenhove, Pierre
dc.contributor.authorRandour, Mickael
dc.contributor.authorFijalkow, Nathanaël
dc.contributor.authorBouyer, Patricia
dc.date.accessioned2024-01-25T03:30:36Z
dc.date.available2024-01-25T03:30:36Z
dc.date.copyright2023-07-05
dc.date.issued2023
dc.description.accesstimeAT_PUBLICATION
dc.description.financePublikacja bezkosztowa
dc.description.versionFINAL_PUBLISHED
dc.identifier.doi10.4230/LIPICS.ICALP.2023.118
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/108711
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2023/18170/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages1-18
dc.rightsCC-BY
dc.sciencecloudnosend
dc.titleHow to Play Optimally for Regular Objectives?
dc.typeJournalArticle
dspace.entity.typePublication