Search engine for discovering works of Art, research articles, and books related to Art and Culture
ShareThis
Javascript must be enabled to continue!

Parity games and reachability in infinite-state systems with parameters

View through CrossRef
Jeux de parité et problème d'accessibilité dans des systèmes à infinité d'états avec paramètres Les approches standard de la vérification de modèle se limitent à des spécifications concrètes, par exemple «est-il possible d'atteindre une configuration après que plus de 10 unités de temps se soient écoulées?». Néanmoins, pour certains types de programmes informatiques, comme les technologies embarquées, les contraintes dépendent de l'environnement. De là émerge la nécessité des spécifications paramétriques, par exemple «est-il possible d'atteindre une configuration après que plus de p unités de temps se soient écoulées?» où p désigne un paramètre dont la valeur reste à spécifier.Dans cette thèse nous étudions des variantes paramétriques de trois modèles classique, les automates à pile, à compteur, et temporisés. En plus d'exprimer des contraintes concrètes (sur la pile, le compteur ou les horloges), ces modèles peuvent exprimer des contraintes paramétriques via des comparaisons avec des paramètres. Le problème de l'accessibilité consiste à demander s'il existe une assignation des paramètres telle que il existe une exécution acceptante dans l'automate concret qui en résulte. En plus de ce problème nous étudions des jeux de parités paramétriques, où deux joueurs choisissent une évaluation pour chaque paramètre chacun leur tour, puis déplacent un jeton dans le graphe de l'automate concret résultant. Nous nous intéressons au problème de décider quel joueur dispose d'une stratégie gagnante.Les automates temporisés paramétriques ont été introduit dans les années 90 par Alur, Henzinger et Vardi, qui ont démontré que le problème de l'accessibilité était indécidable, même avec seulement trois horloges pouvant être comparées à des paramètres, ou horloges paramétriques — mais décidable dans le cas d'une seule horloge paramétrique. Des résultats récents de Bundala et Ouaknine démontrent que dans le cas de deux horloges paramétriques et un paramètre, le problème est décidable ainsi que PSPACE^NEXP-dur. Un des principaux résultats de cette thèse consiste à démontrer le caractère EXPSPACE-complet du problème.La borne inférieure EXPSPACE repose sur des résultats récents du domaine de la complexité avancée. Inspirés par Göller, Haase, Ouaknine, et Worrell, nous visualisons la classe EXPSPACE comme un langage de feuille (vision qui repose sur le théorème de Barrington). Nous introduisons un langage de programmation qui peut reconnaître ce genre de langage de feuille. Nous utilisons ensuite une représentation des entiers sous forme de restes chinois dont Chiu, Davida et Litow ont montré qu'elle permettait de calculer en LOGSPACE la représentation binaire, et démontrons grâce à elle que les automates temporisés paramétriques à deux horloges paramétriques et un paramètre peuvent simuler notre langage de programmation.Pour la borne supérieure, à la façon de Bundala et Ouaknine, nous réduisons le problème au problème de l'accessibilité dans un type particulier d'automates à compteur paramétrique. Par une série de techniques de découpage d'une exécution fictive, nous démontrons que ce problème est dans PSPACE. Étant donné que notre réduction se fait en temps exponentiel, cela conduit à une borne supérieure EXPSPACE pour le problème de l'accessibilité dans les automates temporisés paramétriques à deux horloges et un paramètre.En ce qui concerne les jeux de parités paramétriques pour les automates à piles paramétriques, nous démontrons que le problème de déterminer quel joueur a une stratégie gagnante est dans (n+1)-EXP si le nombre de paramètres est fixé à n, mais nonélémentaire sinon. Le caractère nonélémentaire du problème est démontré par réduction du problème de la satisfaisabilité des formules de la logique du premier ordre. La borne supérieure est obtenue via une réduction aux automates à pile de piles, pour lesquels le problème des jeux de parités est n-EXP-complet dans le cas de n niveaux de piles.
Agence Bibliographique de l'Enseignement Supérieur
Title: Parity games and reachability in infinite-state systems with parameters
Description:
Jeux de parité et problème d'accessibilité dans des systèmes à infinité d'états avec paramètres Les approches standard de la vérification de modèle se limitent à des spécifications concrètes, par exemple «est-il possible d'atteindre une configuration après que plus de 10 unités de temps se soient écoulées?».
Néanmoins, pour certains types de programmes informatiques, comme les technologies embarquées, les contraintes dépendent de l'environnement.
De là émerge la nécessité des spécifications paramétriques, par exemple «est-il possible d'atteindre une configuration après que plus de p unités de temps se soient écoulées?» où p désigne un paramètre dont la valeur reste à spécifier.
Dans cette thèse nous étudions des variantes paramétriques de trois modèles classique, les automates à pile, à compteur, et temporisés.
En plus d'exprimer des contraintes concrètes (sur la pile, le compteur ou les horloges), ces modèles peuvent exprimer des contraintes paramétriques via des comparaisons avec des paramètres.
Le problème de l'accessibilité consiste à demander s'il existe une assignation des paramètres telle que il existe une exécution acceptante dans l'automate concret qui en résulte.
En plus de ce problème nous étudions des jeux de parités paramétriques, où deux joueurs choisissent une évaluation pour chaque paramètre chacun leur tour, puis déplacent un jeton dans le graphe de l'automate concret résultant.
Nous nous intéressons au problème de décider quel joueur dispose d'une stratégie gagnante.
Les automates temporisés paramétriques ont été introduit dans les années 90 par Alur, Henzinger et Vardi, qui ont démontré que le problème de l'accessibilité était indécidable, même avec seulement trois horloges pouvant être comparées à des paramètres, ou horloges paramétriques — mais décidable dans le cas d'une seule horloge paramétrique.
Des résultats récents de Bundala et Ouaknine démontrent que dans le cas de deux horloges paramétriques et un paramètre, le problème est décidable ainsi que PSPACE^NEXP-dur.
Un des principaux résultats de cette thèse consiste à démontrer le caractère EXPSPACE-complet du problème.
La borne inférieure EXPSPACE repose sur des résultats récents du domaine de la complexité avancée.
Inspirés par Göller, Haase, Ouaknine, et Worrell, nous visualisons la classe EXPSPACE comme un langage de feuille (vision qui repose sur le théorème de Barrington).
Nous introduisons un langage de programmation qui peut reconnaître ce genre de langage de feuille.
Nous utilisons ensuite une représentation des entiers sous forme de restes chinois dont Chiu, Davida et Litow ont montré qu'elle permettait de calculer en LOGSPACE la représentation binaire, et démontrons grâce à elle que les automates temporisés paramétriques à deux horloges paramétriques et un paramètre peuvent simuler notre langage de programmation.
Pour la borne supérieure, à la façon de Bundala et Ouaknine, nous réduisons le problème au problème de l'accessibilité dans un type particulier d'automates à compteur paramétrique.
Par une série de techniques de découpage d'une exécution fictive, nous démontrons que ce problème est dans PSPACE.
Étant donné que notre réduction se fait en temps exponentiel, cela conduit à une borne supérieure EXPSPACE pour le problème de l'accessibilité dans les automates temporisés paramétriques à deux horloges et un paramètre.
En ce qui concerne les jeux de parités paramétriques pour les automates à piles paramétriques, nous démontrons que le problème de déterminer quel joueur a une stratégie gagnante est dans (n+1)-EXP si le nombre de paramètres est fixé à n, mais nonélémentaire sinon.
Le caractère nonélémentaire du problème est démontré par réduction du problème de la satisfaisabilité des formules de la logique du premier ordre.
La borne supérieure est obtenue via une réduction aux automates à pile de piles, pour lesquels le problème des jeux de parités est n-EXP-complet dans le cas de n niveaux de piles.

Related Results

Schule und Spiel – mehr als reine Wissensvermittlung
Schule und Spiel – mehr als reine Wissensvermittlung
Die öffentliche Schule Quest to learn in New York City ist eine Modell-Schule, die in ihren Lehrmethoden auf spielbasiertes Lernen, Game Design und den Game Design Prozess setzt. I...
Backward Reachability of Array-based Systems by SMT solving: Termination and Invariant Synthesis
Backward Reachability of Array-based Systems by SMT solving: Termination and Invariant Synthesis
The safety of infinite state systems can be checked by a backward reachability procedure. For certain classes of systems, it is possible to prove the termination of the procedure a...
Playing Pregnancy: The Ludification and Gamification of Expectant Motherhood in Smartphone Apps
Playing Pregnancy: The Ludification and Gamification of Expectant Motherhood in Smartphone Apps
IntroductionLike other forms of embodiment, pregnancy has increasingly become subject to representation and interpretation via digital technologies. Pregnancy and the unborn entity...
Serious games for environmental education
Serious games for environmental education
AbstractSerious games are increasingly popular in multiple fields, including education and environmental engagement. We conducted a systematic review to examine the reasons for thi...
THE EVOLUTION OF THE WINTER PARALYMPIC GAMES AND SPORTS
THE EVOLUTION OF THE WINTER PARALYMPIC GAMES AND SPORTS
Purpose: The aim of this research was to record and the evolution of the winter paralympic games and sports since 1976 until 2010. The history of the Winter Paralympic Games is rel...
Effect of parity and lactation stage on milk yield, udder and teat morphometric traits of Friesian-Bunaji crossed cows
Effect of parity and lactation stage on milk yield, udder and teat morphometric traits of Friesian-Bunaji crossed cows
Abstract. Data for this study were collected from 40 multiparous (F1) Friesian x Bunaji cows at the dairy herd of the National Animal Production Research Institute (NAPRI) Shika, N...
Serious games to study the influence of wildlife devaluation strategies on hunter behaviour
Serious games to study the influence of wildlife devaluation strategies on hunter behaviour
<p>The international illegal wildlife trade (IWT) threatens countless species globally. Many solutions to the IWT have been proposed and implemented, the most common being in...
Ethnography in Play: Didactic Games of Russian Germans
Ethnography in Play: Didactic Games of Russian Germans
This article presents the case of creating educational games with linguistic, ethnic and cultural components. Games are viewed as a means of conveying important cultural informatio...

Back to Top