Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint