KIT | KIT-Bibliothek | Impressum | Datenschutz

Effective strategies for enumeration games

Kummer, Martin; Ott, Matthias

Abstract:


We study the existence of effective winning strategies in certain
infinite games, so called enumeration games. Originally, these were
introduced by Lachlan (1970) in his study of the lattice of recursively
enumerable sets. We argue that they provide a general and interesting
framework for computable games and may also be well suited for modelling
reactive systems. Our results are obtained by reductions of enumeration
games to regular games. For the latter effective winning strategies exist
by a classical result of Buechi and Landweber. This provides more
perspicuous proofs for several of Lachlan's results as well as a key
for new results. It also shows a way of how strategies for regular
games can be scaled up such that they apply to much more general games.


Volltext §
DOI: 10.5445/IR/12995
Cover der Publikation
Zugehörige Institution(en) am KIT Fakultät für Informatik – Institut für Logik, Komplexität und Deduktionssysteme (ILKD)
Publikationstyp Buch
Publikationsjahr 1995
Sprache Englisch
Identifikator urn:nbn:de:swb:90-AAA129955
KITopen-ID: 12995
Erscheinungsvermerk Karlsruhe 1995. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1995,41.)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page