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.
matz (at) ti (dot) informatik (dot) uni-kiel (dot) de
Last modified: Thu Feb 11 15:20:35 CET 1999