lts

Système de transition labellisé

Auteurs : Enrico Trombetta, Francesco Perrone

En informatique théorique, un système de transition est un concept utilisé dans l'étude du calcul. Il est utilisé pour décrire le comportement potentiel des systèmes discrets. Il se compose d'états et de transitions entre états, qui peuvent être étiquetés avec des étiquettes choisies dans un ensemble ; la même étiquette peut apparaître sur plusieurs transitions. Si le jeu d'étiquettes est un singleton, le système est essentiellement sans étiquette et une définition plus simple omettant les étiquettes est possible.

Tiré de Wikipédia.

Voici le scénario sur lequel j'ai commencé à travailler :

Le problème implique deux agents, Hal et Carla. Hal, diabétique, a perdu son insuline par accident et a un besoin urgent d'en prendre pour rester en vie. Il n'a pas assez de temps pour acheter une nouvelle réserve, mais il sait que Carla garde de l'insuline chez elle, tout près. Hal n'a pas la permission d'accéder à la propriété de Carla, et Hal sait que Carla est également diabétique et qu'il pourrait mettre sa vie en danger en lui prenant ses provisions. D’un autre côté, Hal pense que Carla pourra peut-être acheter de l’insuline plus tard.

Une brève discussion sur ce scénario peut être trouvée dans notes/LTS_insulin.pdf (la source LaTex est disponible dans le dossier src ).

Un croquis d'implémentation est fourni dans src/LTS.pl dans Prolog (en particulier, nous avons décidé d'adopter SWI Prolog).

Pour invoquer un chemin, chargez la base de connaissances dans l'interpréteur, chargez l'état initial et exécutez un chemin.

Par exemple:

?- [LTS].
initial_state ( InitialState ), path( InitialState , Path ) .
InitialState = . ..
Path = . ..
[And a bunch of alternative paths]
true .

?- initial_state(InitialState), export_tree("tree.csv", InitialState).
InitialState = . ..
true .

Cette dernière commande doit écrire une liste CSV de chaque chemin. Le format est documenté dans src/LTS.pl , mais devrait (espérons-le) être assez simple.

Jalon:

[ ] Terminez l'implémentation LTS de la fonction d'arborescence.

[ ] Implémenter un analyseur

[ ] Améliorer la discussion sur le LTS

[ ] Ajoutez un étiquetage aux transitions.

[ ]...