Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Small Strategies for Safety Games
verfasst von : Daniel Neider
Erschienen in: Automated Technology for Verification and Analysis
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider safety games on finite, edge-labeled graphs and present an algorithm based on automata learning to compute small strategies. Our idea is as follows: we incrementally learn regular sets of winning plays until a winning strategy can be derived. For this purpose we develop a modified version of Kearns and Vazirani’s learning algorithm. Since computing a minimal strategy in this setting is hard (we prove that the corresponding decision problem is NP-complete), our algorithm, which runs in polynomial time, is an interesting and effective heuristic that yields small strategies in our experiments.