ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 32/9-10 - 2013  - pp.931-949  - doi:10.3166/tsi.32.931-949
TITRE
Les jeux d’accessibilité généralisée

TITLE
Generalized reachability games

RÉSUMÉ

Dans cet article, nous étudions les jeux d’accessibilité généralisée : ce sont des jeux à deux joueurs à somme nulle, pour lesquels l’objectif du premier joueur, Ève, est donné par une conjonction d’objectifs d’accessibilité. Dans un premier temps, nous montrons que le problème de décider si Ève a une stratégie gagnante est PSPACE -complet, mais polynomial en fixant pour paramètre le nombre d’objectifs. De plus, nous montrons que pour les deux joueurs, les stratégies gagnantes nécessitent beaucoup de mémoire : des bornes supérieures et inférieures sont présentées. Dans un second temps, nous nous intéressons à des restrictions de ces jeux pour lesquels nous cherchons des algorithmes efficaces pour décider du gagnant et construire des stratégies gagnantes.



ABSTRACT

In this paper, we consider two-player zero-sum games with generalized reachability objectives, defined as conjunctions of reachability objectives. We first prove that deciding the winner in such games is PSPACE-complete, although it is fixed-parameter tractable with the number of reachability objectives as parameter. Moreover, we consider the memory requirements for both players and give matching upper and lower bounds on the size of winning strategies. In order to construct more efficient algorithms, we consider subclasses of generalized reachability games.



AUTEUR(S)
Nathanaël FIJALKOW, Florian HORN

MOTS-CLÉS
jeux sur les graphes, jeux d’accessibilité, jeux pour la vérification, conjonctions d’objectifs

KEYWORDS
games on graphs, reachability games, games for verification, conjunction of objectives

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (192 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier