SciDok

Eingang zum Volltext in SciDok

Lizenz

Dissertation zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-58256
URL: http://scidok.sulb.uni-saarland.de/volltexte/2014/5825/


Labelled superposition

Fietzke, Arnaud

pdf-Format:
Dokument 1.pdf (2.059 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Entscheidungsverfahren , Automatisches Beweisverfahren , Verifikation
Freie Schlagwörter (Deutsch): Superposition
Freie Schlagwörter (Englisch): superposition , splitting , timed automata , probabilistic timed automata
CCS - Klassifikation: I.2.3 I.2.
Institut: Fachrichtung 6.2 - Informatik
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Hauptberichter: Weidenbach, Christoph (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 05.06.2014
Erstellungsjahr: 2013
Publikationsdatum: 16.07.2014
Kurzfassung auf Englisch: The work presented in this thesis consists of two parts:
The first part presents a formalization of the splitting rule for case analysis in superposition and a proof of its correctness, as well as the integration into splitting of a novel approach to lemma learning, which allows the derivation of non-ground lemmas.
The second part deals with the application of hierarchic superposition, and in particular superposition modulo linear arithmetic SUP(LA), to the verification of timed and probabilistic timed systems. It contains the following three main contributions: Firstly, a SUP(LA) decision procedure for reachability in timed automata, which is among the first decision procedures for free first-order logic modulo linear arithmetic; secondly, an automatic induction rule for SUP(LA) based on loop detection, whose application allows a generalization of the decidability result for timed automata to timed automata with unbounded integer variables; and thirdly, a formalism for modelling probabilistic timed systems with first-order background theories, as well as a novel approach for the analysis of such systems based on a reduction to model checking using SUP(LA) proof enumeration.
Kurzfassung auf Deutsch: Diese Arbeit besteht aus zwei Teilen:
Im ersten Teil wird die Splitting-Regel zur Fallunterscheidung im Superpositionskalkül formalisiert und die Korrektheit der Formalisierung bewiesen. Ausserdem wird die Splitting-Regel mit einem neuartigen Verfahren zum Lernen von Lemmata erweitert, welches das Lernen von nicht-grund Lemmata erlaubt.
Der zweite Teil befasst sich mit der Anwendung des hierarchischen Superpositionskalküls, insbesondere von Superposition modulo linearer Arithmetik SUP(LA), zur Verifikation von Echtzeit- und probabilistischen Echtzeitsystemen. Die drei wichtigsten Beiträge in diesem Teil sind: Erstens, ein SUP(LA)-basiertes Entscheidungsverfahren für Timed Automata, welches zu den ersten Entscheidungsverfahren für die hierarchische Kombination der freien Logik erster Stufe mit linear Arithmetik gehört; zweitens, eine Regel zur automatischen Induktion in SUP(LA), die auf der Erkennung von Schleifen basiert, und dank derer das Entscheidbarkeitsresultat für Timed Automata hin zu Timed Automata mit unbeschränkten Integer-Variablen verallgemeinert wird; und drittens, ein Formalismus zur Modellierung probabilistischer Echtzeitsysteme mit Hintergrundtheorien erster Stufe, sowie ein neuartiges Verfahren zur Analyse ebensolcher Systeme, welches auf einer Aufzählung von Erreichbarkeitsbeweisen in SUP(LA) sowie einer Zurückführung auf das Model Checking-Verfahren basiert.
Lizenz: Veröffentlichungsvertrag für Dissertationen und Habilitationen

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English