WWW.BOOK.DISLIB.INFO
FREE ELECTRONIC LIBRARY - Books, dissertations, abstract
 
<< HOME
CONTACTS



Pages:   || 2 | 3 | 4 | 5 |   ...   | 37 |

«Learning Communicating and Nondeterministic Automata Carsten Kern ISSN 0935–3232 · Aachener Informatik Berichte · AIB-2009-17 RWTH Aachen · ...»

-- [ Page 1 ] --

Aachen

Department of Computer Science

Technical Report

Learning Communicating and

Nondeterministic Automata

Carsten Kern

ISSN 0935–3232 · Aachener Informatik Berichte · AIB-2009-17

RWTH Aachen · Department of Computer Science · September 2009

Learning Communicating and

Nondeterministic Automata

Von der Fakult¨t f¨r Mathematik, Informatik und

au

Naturwissenschaften der Rheinisch-Westf¨lischen

a

Technischen Hochschule Aachen zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaften genehmigte Dissertation vorgelegt von Diplom-Informatiker Carsten Kern aus Aachen Berichter: Prof. Dr. Ir. Joost-Pieter Katoen Prof. Dr. Bengt Jonsson Tag der m¨ndlichen Pr¨fung: 31. August 2009 u u Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verf¨ gbar.

u Carsten Kern Lehrstuhl Informatik 2 kern@cs.rwth-aachen.de Aachener Informatik-Bericht AIB-2009-17 Herausgeber: Fachgruppe Informatik RWTH Aachen University Ahornstr. 55 52074 Aachen

GERMANY

ISSN 0935–3232 Abstract The results of this dissertation are two-fold. On the one hand, inductive learning techniques are extended and two new inference algorithms for inferring nondeterministic, and universal, respectively, finite-state automata are presented. On the other hand, certain learning techniques are employed and enhanced to semi-automatically infer communicating automata (also called design models in the software development cycle). For both topics, theoretical results on the feasibility of the approaches, as well as an implementation are presented which, in both cases, support our theory.

Concerning the first objective to derive a so-called active online learning algorithm for nondeterministic finite-state automata (NFA), we present, in analogy to Anlguin’s famous learning algorithm L∗ [Ang87a] for deterministic finite-state automata (DFA), a version for inferring a certain subclass of NFA. The automata from this class are called residual finitestate automata (RFSA). It was shown by Denis et al. [DLT02] that there is an exponential gap between the size of minimal DFA and their corresponding minimal RFSA. Even if there are also cases where the canonical (i.e., minimal) RFSA is exponentially larger than a corresponding minimal NFA, we show that the new learning algorithm—called NL∗ — is a great improvement compared to L∗ as the inferred canonical RFSA has always at most the size of the corresponding minimal DFA but is usually even considerably smaller and more easy to learn. Unlike a learning procedure developed by Denis et al.—called DeLeTe2 [DLT04]—our algorithm is capable of deriving canonical RFSA. Like L∗, the new algorithm will be applicable in many fields including pattern recognition, computational linguistics and biology, speech recognition, and verification. From our point of view, NL∗ might especially play a mayor role in the area of formal verification where the size of the models that are processed is of enormous importance and nondeterminism not regarded an unpleasant property.

The second objective of this thesis is to create a method for inferring distributed design models (CFMs) from a given set of requirements specified as scenarios (message sequence charts). The main idea is to extend the L∗ algorithm to cope with valid and invalid sets of system runs and, after some iterations, come up with an intermediate design model (a DFA) which exhibits features that make it distributable into communicating components (or processes) interacting via FIFO channels. Theoretical results on which classes of CFMs are learnable in which time-complexity bounds are presented. We also developed a tool implementation called Smyle, realizing important theoretical results evolving from this part of the thesis. Based on this learning formalism we also derive a software-engineering lifecycle model called the Smyle Modeling Approach in which we embedded our learning approach.

Additionally, we launched a project for a new learning library called libalf which includes most of the learning algorithms (and their extensions) mentioned in this thesis.

We hope that, due to its continuously increasing functionality, libalf will find broad acceptance among researchers, and that it will be the starting point for an extensive project of different research groups which will employ libalf, or augment the library with new algorithms.

Zusammenfassung Die Ergebnisse dieser Arbeit sind zweigeteilt. Einerseits werden existierende induktive Lernverfahren grundlegend erweitert, und zwei neue Lernalgorithmen zur Inferenz nichtdeterministischer bzw. universeller Automaten vorgestellt. Andererseits werden bestimmte Lerntechniken eingesetzt und verbessert, um kommunizierende Automaten (in der Softwareentwicklung auch Designmodelle genannt) semi-automatisch zu inferieren. Es werden sowohl theoretische Resultate bez¨ glich der Durchf¨ hrbarkeit der Ans¨tze als auch zwei u u a Implementierungen vorgestellt, die jeweils unsere theoretische Arbeit untermaueren.

F¨ r das erste Ziel, n¨mlich einen sogenannten aktiven online Lernalgorithms f¨ r nichtu a u deterministische, endliche Automaten (NFA) zu entwerfen, wird in Analogie zu Angluins ber¨ hmtem Lernalgorithmus L∗ [Ang87a] f¨ r determinisitische, endliche Automaten u u (DFA) eine Version eines Algorithmus entwickelt, der eine bestimmte Teilklasse nichtdeterministischer, endlicher Automaten inferieren kann. Die Automaten dieser Klasse werden residuelle, endliche Automaten (RFSA) genannt. Denis et al. haben in [DLT02] gezeigt, dass es eine exponentielle Kluft zwischen der Gr¨ße minimaler DFA und ¨quivao a lenter kanonischer RFSA gibt. Auch in F¨llen in denen der kanonische RFSA exponentiell a gr¨ßer ist als ein ¨quivalenter minimaler NFA, zeigen wir, dass unser neuer Lernalgoritho a mus NL∗ eine große Verbesserung im Vergleich zu dem schon existierenden Algorithmus L∗ darstellt, da der kanonische RFSA im schlimmsten Fall die gleiche Gr¨ße wie der o ¨quivalente minimale DFA besitzt, im Regelfall jedoch wesentlich kleiner und leichter zu a lernen ist. Im Gegensatz zu dem von Denis et al. in [DLT04] vorgestellten Lernverfahren ist unser Algorithmus in der Lage kanonische RFSA zu lernen. Wie L∗ so wird auch unser Algorithmus NL∗ in vielen Bereichen Einsatz finden: z.B. in der Mustererkennung, in der maschinellen Linguistik und Biologie sowie in der Spracherkennung und formalen Verifikation. Unserer Meinung nach k¨nnte NL∗ vor allem im Bereich der formalen Verio fikation eine Hauptrolle spielen, in der die Gr¨ße der zu pr¨fenden Modelle von essentieller o u Bedeutung und Nichtdeterminismus nur von untergeordnetem Interesse ist.





Das zweite Ziel dieser Arbeit lautet, einen Ansatz zur Inferenz verteilter Designmodelle (CFMs) basierend auf Anforderungen zu kreieren, die als Systemszenarios (Message Sequence Charts) spezifiziert sind. Die Hauptidee besteht darin, den Algorithmus von Angluin dahingehend zu erweitern, dass er mit g¨ ltigen und ung¨ ltigen Systeml¨ufen u u a umzugehen weiß und nach einigen Iterationen mit einem Zwischenmodell (einem DFA) aufwartet, das Eigenschaften aufweist, die es in uber FIFO Kan¨le kommunizierende Kom¨ a ponenten (oder Prozesse) verteilen lassen. Es werden theoretische Ergebnisse hergeleitet, die Aussagen dar¨ ber liefern, welche Klassen verteiler Automaten (CFMs) mit welchen u Komplexit¨tsschranken lernbar sind. In diesem Zusammenhang wird außerdem eine Ima plementierung mit Namen Smyle vorgestellt, die die Durchf¨ hrbarkeit des Lernens einiger u in dieser Arbeit vorgestellter Klassen aufzeigt. Aufbauend auf diesem theoretischen Lernformalismus wird ein softwaretechnisches Lebenszyklusmodell, genannt der Smyle Modeling Approach, entwickelt, in das unsere Lernanwendung Smyle integriert wird.

Zus¨tzlich wurde ein Projekt ins Leben gerufen, das aktuell die meisten der in dieser a Arbeit vorgestellten Lernverfahren und deren Erweiterungen implementiert. Die entstandene Lernbibliothek tr¨gt den Namen libalf. Wir hoffen, dass diese Bibliothek aufa grund ihres kontinuierlich ansteigenden Umfangs an Lernverfahren großen Anklang unter Wissenschaftlern finden wird, und dass sie der Startpunkt eines weitl¨ufigen Projektes a unterschiedlicher Universit¨ten wird, die diese Bibliothek nutzen und dazu beitragen, sie a mit neuen Algorithmen an zu reichern.

Acknowledgments My first and utmost thanks go to my supervisor Professor Dr. Ir. Joost-Pieter Katoen for being, at all times, a pleasant, motivating, and challenging employer, colleague, and mentor, and always encouraging me to present research results at international conferences.

I am equally beholden to my former diploma thesis supervisor, current coauthor, and friend Dr. Benedikt Bollig who always elated me for starting and continuing the challenge of doing a PhD, even when I was facing difficult situations.

I am grateful to Professor Dr. Bengt Jonsson for immediately agreeing on being the second supervisor for this dissertation.

Moreover, I would like to unendingly thank my coauthors Professor Dr. Ir. Joost-Pieter Katoen, Dr. Benedikt Bollig, Professor Dr. Martin Leucker, and Dr. Peter Habermehl for sharing their knowledge and expertise with me, for the great, pleasant but at the same time professional and inspiring research atmosphere, for interesting discussions, and for all the memorable moments we lived through during my PhD time. They all greatly contributed to the successful completion of this dissertation.

Furthermore, I want to express my gratitude towards the Ecole Normale Sup´rieure de e Cachan and the researchers from the Laboratoire Sp´cification et V´rification for making e e two incredible one-month research visits in Paris possible, and, moreover, to the German Academic Exchange Service (DAAD) within the Egide/DAAD Project Procope 08/09 and the DFG Research Training Group AlgoSyn for their financial support during that unforgettable time.

My special thanks go to my officemate Stefan Rieger for all the exciting moments we had during our office time in Aachen and in several conference locations, and for always being a great, helpful, and cooperative friend. I am also grateful to all other colleagues from Lehrstuhl f¨ r Informatik 2 for the nice research environment, which contributed a u lot to this dissertation.

I am especially indebted to Dr. Benedikt Bollig who reviewed major parts of this dissertation in all stages of maturity, and provided helpful feedback and many valuable suggestions for improvements. Great thanks also belong to all the other people—especially Professor Dr. Martin Leucker, Dr. Peter Habermehl, Cathrin Niebel, Daniel Retkowitz, David Piegdon, and Stefan Schulz—for revising substantial parts of this dissertation, discussing enhancements, and proposing useful changes.

Many thanks go to my student assistants David Piegdon and Stefan Schulz who greatly contributed to creating the learning library libalf and the learning application Smyle presented in this dissertation.

Last, but certainly not least, my special thanks go to my parents Dr. Wolfgang and Christa Kern, and my girlfriend Cathrin for always giving me so much love, support, and strength throughout all these fascinating and demanding years.

–  –  –

Index 211 1 Introduction Nowadays, everyday life is almost totally dependent on software driven devices. Many of them are extremely safety-critical (also called life-critical) applications. Life-critical software is omnipresent. As such they can be found everywhere in daily life, e.g., within intensive care devices, safety devices in the automotive- or avionics sector, e.g., cruise controls, autonomous automobiles and autopilots, etc. Their malfunction could cause deep impact on our life, e.g., severe injuries or even death, but might also result in fatal damage to, or loss of, machinery, e.g., on extremely cost intensive space missions, or global environmental harm in case of a defective nuclear power plant, or misdirected nuclear or biochemical weapons. Therefore, strong attention must be payed to develop faultless software.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 37 |


Similar works:

«TECHNISCHE UNIVERSITÄT MÜNCHEN Inhaltsverzeichnis Lehrstuhl für Siedlungswasserwirtschaft Untersuchung des Einflusses von Oberflächeneigenschaften verschiedener Kunststoffe auf die Besiedlung durch und die Umsatzleistung von PSEUDOMONAS PUTIDA MT2 Dipl. Biol. Univ. Dominik Montag Vollständiger Abdruck der von der Fakultät für Bauingenieurund Vermessungswesen der Technischen Universität München zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaften (Dr. rer. nat.)...»

«Seen in a different light. Icons in Byzantine museums and churches Gianna Stavroulaki and John Peponis National Technical University of Athens, Greece, Georgia institute of technology, USA gstav 1@otenet.gr, john.peponis@arch.gatech.edu Abstract We analyze the principles that govern the visibility of icons in churches and museums. We develop methods for enriching visibility analysis by taking into consideration not only the arrangement but also the illumination of space. Finally, we suggest...»

«TECHNICKÝ A ZKUŠEBNÍ ÚSTAV STAVEBNÍ PRAHA, s.p. Aut orizován a no tif i k ov án podl e článku 10 Směrnice Rady Prosecká 811/76a 89/106/EC z 21. prosince CZ-190 00 Praha 9 1988 o sbližování zákonů, p ře dpi s ů a sp rá vn í c h Tel.: +420 286 019 458 post upů členských zemí Internet: www.tzus.cz týkajících se staveb ních výrobků. EOTA Mitglied Europäische Technische Zulassung ETA-12/0080 (Deutsche Übersetzung, der Original-Zulassungsbescheid ist in tschechischer...»

«Hochschuldidaktisches Zentrum der Technischen Universität Dortmund Franziska Eder, Bianca Roters, Antonia Scholkmann, Maria Paula Valk-Draad Wirksamkeit problembasierten Lernens als hochschuldidaktische Methode Ergebnisbericht einer Pilotstudie mit Studierenden in der Schweiz und Deutschland Wirksamkeit problembasierten Lernens als hochschuldidaktische Methode F. Eder, B.Roters, A. Scholkmann, M. Valk-Draad Ergebnisbericht einer Pilotstudie im Rahmen des Forschungsprojekts “Wirksamkeit...»

«Bachelor Physikalische Ingenieurwissenschaft Wintersemester 2009 / 2010 01. Mathematische Grundlagen (34 LP) Analysis I für Ingenieure Seite 1 Analysis II für Ingenieure Seite 3 Differentialgleichungen für Ingenieure Seite 5 Integraltransformationen und partielle Differentialgleichungen für Ingenieure Seite 7 Lineare Algebra für Ingenieure Seite 9 Numerische Mathematik I für Ingenieure Seite 11 02. Technisch-methodische Grundlagen (18 LP) Einführung in die Informationstechnik für...»

«Entwicklung und Evaluierung eines kooperativen Interaktionskonzepts an Entscheidungspunkten für die teilautomatisierte, manöverbasierte Fahrzeugführung Vom Fachbereich Maschinenbau an der Technischen Universität Darmstadt zur Erlangung des Grades eines Doktor-Ingenieurs (Dr.-Ing.) genehmigte Dissertation vorgelegt von Dipl.-Ing. Sebastian Geyer aus München Berichterstatter: Prof. Dr. rer. nat. Hermann Winner Mitberichterstatter: Prof. Dr. phil. Klaus Bengler Tag der Einreichung: 14. März...»

«Sicherheit und Privatsphäre in RFID-Systemen Dirk Henrici, Jochen Müller, Paul Müller AG Integrierte Kommunikationssysteme Technische Universität Kaiserslautern Gottlieb-Daimler-Straße 67663 Kaiserslautern {henrici,jmueller,pmueller}@informatik.uni-kl.de Zusammenfassung: RFID-Systeme sind in aller Munde: Sie sollen Warenwirtschaftssysteme revolutionieren und auch in einer Vielzahl anderer Anwendungsbereiche hilfreiche Dienste leisten. Für die damit verbundene Kostenersparnis und die neuen...»

«Ermächtigt und notifiziert g em äß A rti kel 10 der Richtlinie des Rates vom 21. Dezember 1988 zur Angleichung der Rechtsund Verwaltungsvorschriften d er M i t g li e d s t aa t en über B auprodukte (89/106/EWG) Europäische Technische Zulassung ETA-06/0259 Handelsbezeichnung TOGE Deckennagel TDN Trade name TOGE ceiling anchor TDN Zulassungsinhaber TOGE-DÜBEL Holder of approval A. Gerhard KG Illesheimer Straße 10 90431 Nürnberg DEUTSCHLAND Zulassungsgegenstand Wegkontrolliert spreizender...»

«Lehrstuhl für Werkzeugmaschinen der Technischen Universität München Methode zur Kompensation betriebsabhängiger Einflüsse auf die Absolutgenauigkeit von Industrierobotern Thomas Bongardt Vollständiger Abdruck der von der Fakultät für Maschinenwesen der Technischen Universität München zur Erlangung des akademischen Grades eines Doktor-Ingenieurs (Dr.-Ing.) genehmigten Dissertation. Vorsitzender: Univ.-Prof. Dr.-Ing. Udo Lindemann Prüfer der Dissertation: 1. Univ.-Prof. Dr.-Ing....»

«Modification and Application of Carbon Nanotubes Dissertation Zur Erlangung des Grades eines Doktors der Naturwissenschaften Vorgelegt von Dheeraj Jain Aus Gaya, Indien Genehmigt von der Fakultät für Naturund Materialwissenschaften Der Technischen Universität Clausthal 31 Juli, 2007 Modification and Application of Carbon Nanotubes Dissertation Zur Erlangung des Grades eines Doktors der Naturwissenschaften Vorgelegt von Dheeraj Jain Aus Gaya, Indien Genehmigt von der Fakultät für Naturund...»





 
<<  HOME   |    CONTACTS
2016 www.book.dislib.info - Free e-library - Books, dissertations, abstract

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.