All reports by Author Frank Stephan:

__
TR04-058
| 28th May 2004
__

John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan#### Identifying Clusters from Positive Data

__
TR04-038
| 27th April 2004
__

John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann#### A Polynomial Time Learner for a Subclass of Regular Patterns

__
TR04-015
| 24th February 2004
__

Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet#### Enumerations of the Kolmogorov Function

__
TR97-013
| 13th February 1997
__

Bernd Borchert, Dietrich Kuske, Frank Stephan#### On Existentially First-Order Definable Languages and their Relation to NP

__
TR96-060
| 19th November 1996
__

Bernd Borchert, Frank Stephan#### Looking for an Analogue of Rice's Theorem in Complexity Theory

__
TR96-033
| 6th March 1996
__

Bernd Borchert, Desh Ranjan, Frank Stephan#### On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions

John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan

The present work studies clustering from an abstract point of view

and investigates its properties in the framework of inductive inference.

Any class $S$ considered is given by a numbering

$A_0,A_1,...$ of nonempty subsets of the natural numbers

or the rational k-dimensional vector space as a hypothesis space.

A clustering ...
more >>>

John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann

Presented is an algorithm (for learning a subclass of erasing regular

pattern languages) which

can be made to run with arbitrarily high probability of

success on extended regular languages generated by patterns

$\pi$ of the form $x_0 \alpha_1 x_1 ... \alpha_m x_m$

for unknown $m$ but known $c$,

more >>>

Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

A recursive enumerator for a function $h$ is an algorithm $f$ which

enumerates for an input $x$ finitely many elements including $h(x)$.

$f$ is an $k(n)$-enumerator if for every input $x$ of length $n$, $h(x)$

is among the first $k(n)$ elements enumerated by $f$.

If there is a $k(n)$-enumerator for ...
more >>>

Bernd Borchert, Dietrich Kuske, Frank Stephan

Pin & Weil [PW95] characterized the automata of existentially

first-order definable languages. We will use this result for the following

characterization of the complexity class NP. Assume that the

Polynomial-Time Hierarchy does not collapse. Then a regular language

L characterizes NP as an unbalanced polynomial-time leaf language

if and ...
more >>>

Bernd Borchert, Frank Stephan

Rice's Theorem says that every nontrivial semantic property

of programs is undecidable. It this spirit we show the following:

Every nontrivial absolute (gap, relative) counting property of circuits

is UP-hard with respect to polynomial-time Turing reductions.

Bernd Borchert, Desh Ranjan, Frank Stephan

The paper analyzes in terms of polynomial time many-one reductions

the computational complexity of several natural equivalence

relations on Boolean functions which derive from replacing

variables by expressions. Most of these computational problems

turn out to be between co-NP and Sigma^p_2.