All reports by Author Bernhard Schwarz:

__
TR04-037
| 14th April 2004
__

Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner#### Generation Problems

Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner

Given a fixed computable binary operation f, we study the complexity of the following generation problem: The input consists of strings a1,...,an,b. The question is whether b is in the closure of {a1,...,an} under operation f.

For several subclasses of operations we prove tight upper and lower bounds for the ... more >>>