All reports by Author Sebastian Seibert:

__
TR00-076
| 24th August 2000
__

Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert#### Measures of Nondeterminism in Finite Automata

__
TR99-031
| 2nd September 1999
__

Hans-Joachim BĂ¶ckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger#### Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem

Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert

While deterministic finite automata seem to be well understood, surprisingly

many important problems

concerning nondeterministic finite automata (nfa's) remain open.

One such problem area is the study of different measures of nondeterminism in

finite automata and the

estimation of the sizes of minimal nondeterministic finite automata. In this

paper the ...
more >>>

Hans-Joachim BĂ¶ckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger

The investigation of the possibility to efficiently compute

approximations of hard optimization problems is one of the central

and most fruitful areas of current algorithm and complexity theory.

The aim of this paper is twofold. First, we introduce the notion of

stability of approximation algorithms. This notion is shown to ...
more >>>