SIKS-seminar at the occasion of Sicco Verwer's PhD defense


On Tuesday March 2th, the day of the PhD defense of Sicco Verwer, some of
his PhD defense committee members will give a short presentation on
related work. It will be an interesting morning as the presenters are
experts in the fields of learning theory, grammatical inference, and
formal methods.

The seminar is part of the Advanced Components part of SIKS educational
program. You are cordially invited to attend both the symposium and the
defense. See below for the location, program, and abstracts of the talks.

Location:

Bordewijkzaal (HB19.130, 19th floor),
EEMCS building
(Mekelweg 4, big red and blue)
TU Delft.


The defense will take place in the Senaatszaal in the Aula (Mekelweg 5) of
the TU Delft.

Program:

10:00 Dr. Cristophe Costa Florêncio -- Finding Consistent Categorial
Grammars of Bounded Value
10:35 Prof. Pieter Adriaans -- The Power and Perils of MDL

11:10 Break

11:30 Prof. Frits Vaandrager -- Learning I/O Automata
12:10 Prof. Pierre Dupont -- State-merging DFA Induction Algorithms with
Mandatory Merge Constraints

12:50 END Symposium

14:30 Small introductory talk (lekenpraatje)
15:00 PhD defense Sicco Verwer, thesis title: Efficient Identification of
Timed Automata
16:00 Reception

-- ABSTRACTS --

title: Finding Consistent Categorial Grammars of Bounded Value: a
Parameterized Approach
by Dr. Christophe Costa Florêncio

abstract unknown, topic: fixed parameter tractability results for inducing
of categorial grammars.

title: The Power and Perils of MDL
by Prof. Pieter Adriaans

abstract:
We point out a potential weakness in the application
of the celebrated Minimum Description Length (MDL) principle
for model selection. Specifically, it is shown that (although the
index of the model class which actually minimizes a two-part code
has many desirable properties) a model which has a shorter two-
part code-length than another is not necessarily better (unless of
course it achieves the global minimum). This is illustrated by an
application to infer a grammar (DFA) from positive examples. We
also analyze computability issues, and robustness under recoding
of the data. Generally, the classical approach is inadequate to
express the goodness-of-fit of individual models for individual
data sets. In practice however, this is precisely what we are
interested in: both to express the goodness of a procedure and
where and how it can fail. To achieve this practical goal, we
paradoxically have to use the, supposedly impractical, vehicle of
Kolmogorov complexity.

title: Learning I/O Automata
by Prof. Frits Vaandrager

abstract:
I/O automata and Mealy machines. We show how any algorithm for active
learning of Mealy machines can be used for learning output deterministic
I/O automata in the sense of Lynch, Tuttle and Jonsson.
The main idea is to place a transducer in between the I/O automata teacher
and the Mealy machine learner, which translates concepts from the world of
I/O automata to the world of Mealy machines, and vice versa.

title: State-merging DFA Induction Algorithms with Mandatory Merge
Constraints
by Prof. Pierre Dupont

abstract:
Standard state-merging DFA induction algorithms, such as RPNI or
Blue-Fringe, aim at inferring a regular language from positive and
negative
strings. In particular, the negative information prevents merging
incompatible states: merging those states would lead to produce an
inconsistent DFA. Whenever available, domain knowledge can also be used to
extend the set of incompatible states. We introduce here mandatory merge
constraints, which form the logical counterpart to the usual
incompatibility constraints. We show how state-merging algorithms can
benefit from these new constraints. Experiments following the
Abbadingo contest protocol illustrate the interest of using mandatory
merge con-straints. As a side effect, this paper also points out an
interesting property of state- merging techniques: they can be extended to
take any pair of DFAs as inputs ratherthan simple strings.