Curriculum Vitae

Personal Data

Born on March, 26th 1970 in Neumünster (Germany), unmarried.
Hobbies: ballroom and swing dancing, waterpolo.

School and Studies

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 (JavaTM).
Apr. '99 - Oct. '02
Software developer at Poet, Hamburg, Germany
Oct. '02 - now
Software developer at ppi Media GmbH, Kiel, Germany.

Research Interests

Keywords: Formal languages, picture languages, finite automata, finite model theory, monadic second-order logic
Before masters

In a programming course I investigated minimization of nondeterministic 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.

After Ph.D
Every now and then, I do some research in my spare time.
Oliver Matz, matz (at) ti (dot) informatik (dot) uni-kiel (dot) de
Last modified: Thu Feb 11 15:20:35 CET 1999