Titelaufnahme

Titel
A practical view of answer-set programming transformations / von Mikołaj Koziarkiewicz
VerfasserKoziarkiewicz, Mikołaj
Begutachter / BegutachterinTompits, Hans
Erschienen2011
UmfangVI, 70 Bl. : graph. Darst.
HochschulschriftWien, Techn. Univ., Dipl.-Arb., 2011
Anmerkung
Zsfassung in dt. Sprache
SpracheEnglisch
DokumenttypDiplomarbeit
Schlagwörter (DE)Answer Set Programming / Logikorientierte Programmierung / Optimierung
Schlagwörter (EN)answer set programming / logic programming / optimization
URNurn:nbn:at:at-ubtuw:1-39312 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
A practical view of answer-set programming transformations [0.95 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Diese Arbeit beschäftigt sich mit der Untersuchung des praktisches Nutzens von formalen Transformationen in der Answer-Set Programmen. Answer-Set Programmierung (ASP) ist ein für deklaratives Problemlösen bestimmter Formalismus, der auf Prinzipien des nichtmonotonen Schließens aufbaut.

Wir beginnen mit einer Übersicht des heutigen Stands in dem Feld. Unsere Unter- suchungen basieren auf zwei unterschiedlichen Transformationssysteme - eines, dass auf bestimmten syntaktischen Transformationen basiert; und ein zweites, welches auf semantischen Bedingungen aufbaut und redundante Regeln so wie Literale entfernt.

Anschließend wird eine Diskussion über die Implementierung von Algorithmen zur Bestimmung der Anwendbarkeit von Regeln für diese zwei Systeme durchgeführt. Danach zeigen wir mit Hilfe der Interaktionseigenschaften der Transformationen, wie die Eingabedaten intern effektiv behandelt werden können.

Eine Implementierung in Python wird benutzt, um eine Untersuchung der Anwend- barkeit der Transformationen bezüglich unterschiedlichen Beispielprogrammen durchzuführen. Analysiert werden, unter anderem, Studentenprogramme, zufallsgenerierte Programme, und automatisch generierte Programme erzeugt von verschiedenen Frontends für deklaratives Problemlösen.

Die Resultate zeigen, dass die betrachteten Transformationen nur eine geringe Anwendbarkeit besitzen. Außer für den Fall von Zufallsprogrammem wird nur eine kleine Anzahl von Anwendungsinstanzen gefunden. Folgen von anwendbaren Transformationen sind praktisch nicht existent.

Somit ist der praktische Nutzen für diese in der Literatur diskutierten Transformationen für Online- oder Offline-Optimierung gering.

Zusammenfassung (Englisch)

The focus of this thesis is the examination of the practicality of applying known formal transformations of answer-set programs.

Answer-set programming (ASP) is a formalism for declarative problem solving, based on the principles of non-monotonic reasoning. The research is started by constructing an overview of well-defined transformations existing in the scientific literature. We consider two systems of transformations -- one composed of certain syntactic transformations; the other of the semantic removal of rules and literals. This work then discusses algorithms for implementing applicability checking within the two systems, either existing ones from the literature, or new ones. Next, it is shown how to effectively process input data within the defined frameworks, utilizing properties related to the interactions between the transformations. With the help of a Python implementation, several data sets composed of answer-set programs are checked for transformation applicability, including: student-written programs, randomly-generated programs, and programs created by various front-ends for declarative problem solving.

The results obtained show that the utility of applying the considered program transformations is quite low. Barring random input, only a small number of applicable transformation instances is found. Moreover, sequences of transformation applications are almost non-existent. Hence, there is little gain in using the considered transformation for online or offline optimization.