Logo: to the web site of Uppsala University

uu.sePublications from Uppsala University
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Learning of Timed Systems
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
2008 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Regular inference is a research direction in machine learning. The goal of regular inference is to construct a representation of a regular language in the form of deterministic finite automaton (DFA) based on the set of positive and negative examples. DFAs take strings of symbols (words) as input, and produce a binary classification as output, indicating whether the word belongs to the language or not. There are two types of learning algorithms for DFAs: passive and active learning algorithms. In passive learning, the set of positive and negative examples is given and not chosen by inference algorithm. In contrast, in active learning, the learning algorithm chooses examples from which a model is constructed.

Active learning was introduced in 1987 by Dana Angluin. She presented the L* algorithm for learning DFAs by asking membership and equivalence queries to a teacher who knows the regular language accepted by DFA to be learned. A membership query checks whether a word belongs to the language or not. An equivalence query checks whether a hypothesized model is equivalent to the DFA to be learned.The L* algorithm has been found to be useful in different areas, including black box checking, compositional verification and integration testing. There are also other algorithms similar to L* for regular inference. However, the learning of timed systems has not been studied before. This thesis presents algorithms for learning timed systems in an active learning framework.

As a model of timed system we choose event-recording automata (ERAs), a determinizable subclass of the widely used timed automata. The advantages of ERA in comparison with timed automata, is that it is known priori the set of clocks of an ERA and when clocks are reset. The contribution of this thesis is four algorithms for learning deterministic event-recording automaton (DERA). Two algorithms learn a subclass of DERA, called event-deterministic ERA (EDERA) and two algorithms learn general DERA.

The problem with DERAs that they do not have canonical form. Therefore we focus on subclass of DERAs that have canonical representation, EDERA, and apply the L* algorithm to learn EDERAs. The L* algorithm in timed setting requires a procedure that learns clock guards of DERAs. This approach constructs EDERAs which are exponentially bigger than automaton to be learned. Another procedure can be used to lean smaller EDERAs, but it requires to solve NP-hard problem.

We also use the L* algorithm to learn general DERA. One drawback of this approach that inferred DERAs have a form of region graph and there is blow-up in the number of transitions. Therefore we introduce an algorithm for learning DERA which uses a new data structure for organising results of queries, called a timed decision tree, and avoids region graph construction. Theoretically this algorithm can construct bigger DERA than the L* algorithm, but in the average case we expect better performance.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis , 2008. , p. 44
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 434
Keywords [en]
learning regular languages, timed systems, event-recording automata
Identifiers
URN: urn:nbn:se:uu:diva-8763ISBN: 978-91-554-7207-8 (print)OAI: oai:DiVA.org:uu-8763DiVA, id: diva2:172086
Public defence
2008-05-23, polhemsalen, Ångström Laboratory, Uppsala University, Uppsala, 13:15
Opponent
Supervisors
Available from: 2008-04-29 Created: 2008-04-29 Last updated: 2022-01-28Bibliographically approved
List of papers
1. Learning of Event-Recording Automata
Open this publication in new window or tab >>Learning of Event-Recording Automata
2008 (English)Report (Other academic)
Abstract [en]

In regular inference, a regular language is inferred from answers to a finite set of membership queries, each of which asks whether the language contains a certain word. One of the most well-known regular inference algorithms is the L* algorithm due to Dana Angluin. However, there are almost no extensions of these algorithms to the setting of timed systems. We extend Angluin's algorithm for on-line learning of regular languages to the setting of timed systems. Since timed automata can freely use an arbitrary number of clocks, we restrict our attention to systems that can be described by deterministic event-recording automata (DERAs). We present three algorithms, TLsg*, TLnsg* and TLs*, for inference of DERAs. In TLsg* and TLnsg*, we further restrict event-recording automata to be event-deterministic in the sense that each state has at most one outgoing transition per action; learning such an automaton becomes significantly more tractable. The algorithm TLnsg* builds on TLsg*, by attempts to construct a smaller (in number of locations) automaton. Finally, TLs* is a learning algorithm for a full class of deterministic event-recording automata, which infers a so called simple DERA, which is similar in spirit to the region graph.

Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2008-013
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:uu:diva-97239 (URN)
Available from: 2008-04-29 Created: 2008-04-29 Last updated: 2024-05-30Bibliographically approved
2. Inference of Event-Recording Automata using Timed Decision Trees
Open this publication in new window or tab >>Inference of Event-Recording Automata using Timed Decision Trees
2008 (English)Report (Other academic)
Abstract [en]

In regular inference, the problem is to infer a regular language, typically represented by a deterministic finite automaton (DFA) from answers to a finite set of membership queries, each of which asks whether the language contains a certain word. There are many algorithms for learning DFAs, the most well-known being the L* algorithm due to Dana Angluin. However, there are almost no extensions of these algorithms to the setting of timed systems. We present an algorithm for inferring a model of a timed system using Angluin's setup. One of the most popular model for timed system is timed automata. Since timed automata can freely use an arbitrary number of clocks, we restrict our attention to systems that can be described by event-recording automata (DERAs). In previous work, we have presented an algorithm for inferring a DERA in the form of a region graph. In this paper, we present a novel inference algorithm for DERAs, which avoids constructing a (usually prohibitively large) region graph. We must then develop techniques for inferring guards on transitions of a DERA. Our construction deviates from previous work on inference of DERAs in that it first constructs a so called timed decision tree from observations of system behavior, which is thereafter folded into an automaton.

Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2008-014
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:uu:diva-97240 (URN)
Available from: 2008-04-29 Created: 2008-04-29 Last updated: 2024-05-30Bibliographically approved

Open Access in DiVA

fulltext(1217 kB)1335 downloads
File information
File name FULLTEXT01.pdfFile size 1217 kBChecksum MD5
a3f48bbe0bbfb661fcd04f1e55cf684e70c5a4c46b5b739228b6d57d803b60a0b6be8b34
Type fulltextMimetype application/pdf
cover(768 kB)164 downloads
File information
File name COVER01.pdfFile size 768 kBChecksum MD5
216ebceb83001d6d75d5097357f40fa80c71580a87a54a72871ae9668b49b77b703f9806
Type coverMimetype application/pdf

Search in DiVA

By author/editor
Grinchtein, Olga
By organisation
Division of Computer SystemsComputer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 1339 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 2447 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf