lts

Beschriftetes Übergangssystem

Autoren : Enrico Trombetta, Francesco Perrone

In der theoretischen Informatik ist ein Übergangssystem ein Konzept, das beim Studium der Berechnung verwendet wird. Es wird verwendet, um das mögliche Verhalten diskreter Systeme zu beschreiben. Es besteht aus Zuständen und Übergängen zwischen Zuständen, die mit aus einer Menge ausgewählten Bezeichnungen gekennzeichnet werden können; Dieselbe Beschriftung kann bei mehr als einem Übergang erscheinen. Wenn der Etikettensatz ein Singleton ist, ist das System im Wesentlichen unbeschriftet und eine einfachere Definition, bei der die Etiketten weggelassen werden, ist möglich.

Entnommen aus Wikipedia.

Dies ist das Szenario, an dem ich mit der Arbeit begonnen habe:

Das Problem betrifft zwei Agenten, Hal und Carla. Hal, Diabetiker, hat versehentlich sein Insulin verloren und muss dringend etwas nehmen, um am Leben zu bleiben. Er hat nicht genug Zeit, um einen neuen Vorrat zu kaufen, aber er weiß, dass Carla etwas Insulin zu Hause hat, ganz in der Nähe. Hal hat keine Erlaubnis, Carlas Grundstück zu betreten, außerdem weiß Hal, dass Carla ebenfalls Diabetikerin ist und er möglicherweise ihr Leben in Gefahr bringt, indem er ihr Lebensmittel wegnimmt. Andererseits glaubt Hal, dass Carla später vielleicht etwas Insulin kaufen kann.

Eine kurze Diskussion zu diesem Szenario finden Sie in notes/LTS_insulin.pdf (LaTex-Quelle ist im Ordner src verfügbar).

Eine Implementierungsskizze wird in src/LTS.pl in Prolog bereitgestellt (insbesondere haben wir uns für die Übernahme von SWI Prolog entschieden).

Um einen Pfad aufzurufen, laden Sie die Wissensdatenbank im Interpreter, laden Sie den Anfangszustand und führen Sie einen Pfad aus.

Zum Beispiel:

?- [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 .

Der letztere Befehl sollte eine CSV-Liste aller Pfade aufschreiben. Das Format ist in src/LTS.pl dokumentiert, sollte aber (hoffentlich) ziemlich einfach sein.

Meilenstein:

[ ] Beenden Sie die LTS-Implementierung der Baumfunktion.

[ ] Implementieren Sie einen Parser

[ ] Verbessern Sie die Diskussion über das LTS

[ ] Beschriftung zu Übergängen hinzufügen.

[ ] ...