Hobbies: ballroom and swing dancing, waterpolo.

- June '89
- ``Abitur'' (high school final examination) at the Immanuel-Kant school Neumünster (Germany);
- Jul. '89 - Sep. '90
- ``Zivildienst'' (civil service, i.e. military exchange service) as a paramedic at the Malteser Hilfsdienst Neumünster;
- Oct. '90 - Mar. '92
- studies in computer science at the Christian-Albrechts-Universität Kiel (Germany) with minor subject mathematics;
- Mar. '96
- Masters of computer computer science; masters thesis in formal language theory, honored with annual award 1996 of the computer science department; (title of the thesis: ``Classification of Picture Languages with Rational Expressions, Grammars, and Logic Formulas'')
- Apr. '99
- Ph.D. at the RWTH Aachen

- Oct. '92 - Mar. '96
- ``Wissenschaftliche Hilfskraft'' (teaching assistant) at the computer science department; Tasks: supervision of exercise groups, corrections of students' homework, documentation of and support for the C-Program AMoRE.
- May '96 - Aug. '98
- research and teaching assistant in the group around Prof. Wolfgang Thomas (theoretical computer science) in Kiel; Tasks: organisation and supervision of exercise groups and programming courses (C++), participation at the design of the C++-project omega.
- Aug. '98 - Mar. '99
- research and teaching assistant in same
group, but now at the RWTH
Aachen; Tasks: organisation and supervision of exercise
groups, seminars and programming courses (Java
^{TM}). - Apr. '99 - Oct. '02
- Software developer at Poet, Hamburg, Germany
- Oct. '02 - now
- Software developer at ppi Media GmbH, Kiel, Germany.

In a programming course I investigated minimization of
*non*deterministic finite automata (NFA).
This gave rise to a paper at TACAS '95.
The paper is about two particular types of canonical forms of
NFA, among which minimal NFA can be found.

In my masters thesis, I
investigated *picture languages*. A *picture* is a
matrix over a finite alphabet and thus the two-dimensional
analogue to a word. A picture language is a set of pictures.
This thesis is chiefly concerned with the transfer of the known
definitions and results of regular word languages to this
two-dimensional case. A few of these ideas were presented STACS '97.

After my masters thesis, I investigated *monadic
second-order logic* on pictures and other structures, in
particular the potential increase of expressiveness when allowing
more and more monadic quantifier alternations. There is certain
relationship to the subject of my masters thesis: the existential
fragment of monadic second-order logic over pictures coincides
with the notion of *recognizability*.

My supervisor and I showed that more quantifier alternations
give strictly more power. This fact is known as the
``*strictness of the monadic quantifier alternation
hierarchy*'' answering an open question of Fagin (see list
of open problems in Finite Model Theory).
The strictness of this hierarchy is related to the (un-proven)
strictness of polynomial hierarchy.

I also have further results that give a finer analysis of the
monadic quantifier alternation hierarchy, in particular
concerning the *first-order closure* introduced by Ajtai,
Fagin, and Stockmeyer in a Research Report and at
STOC '98. Parts of these
results are published in a technical report.

Apart from these results on ``finite model theory'', I am still
interested in questions motivated from formal language theory.
A few results (about *starfree* picture languages)
solving open problems of Giammarresi/Restivo and my
masters thesis have been published in the proceedings of FoSSaCS '98.

Oliver Matz,

`matz (at) ti (dot) informatik (dot) uni-kiel (dot) de`

Last modified: Thu Feb 11 15:20:35 CET 1999