Abstracts der Forschungsberichte Abstracts of the Research Reports
1 
K. AMBOSSPIES, D. DING: Abstract. We construct an r.e. degree a which possesses a greatest aminimal pair b0, b1, i.e., r.e. degrees b0 and b1 such that b0,b1 > a, b0 meet b1 = a, and, for any other pair c0 and c1 with these properties, c0 less or equal bi and c1 less or equal b1i for some i less or equal 1. By extending this result, we show that there are strongly nonbranching degrees which are not strongly noncappable. Finally, by introducing a new genericity concept for r.e. sets, we prove a jump theorem for the strongly nonbranching and strongly noncappable r.e. degrees. 


2 
A. NIES: Abstract. The theory of the r.e. mdegrees has the same computational complexity as true arithmetic. In fact, it is possible to define without parameters a standard model of arithmetic in this degree structure. 


3 
B. BORCHERT: Abstract. The notion of the maximal number of mind changes for a Boolean function was defined and applied in several contexts. An application in complexity theory is the result of Wagner and Wechsung that the classes of the Boolean closure of NP are exactly the classes of the Boolean hierarchy over NP. The aim of this paper is to study the complexity of determining the maximal number of mind changes of a Boolean function if the function is represented as a circuit. 


4 
A. NIES: Abstract. We introduce a general framework to prove undecidability of fragments. This is applied to fragments of theories arising in algebra and recursion theory. For instance, the forallexistforalltheory of the class of finite distributive lattices and of the p.o. of recursively enumerable manyone degrees are shown to be undecidable. 


5 
V. L. SELIVANOV: Abstract. We consider fine hierarchies in recursion theory, descriptive set theory, logic, and complexity theory. Main results state that sets of values of different Boolean terms coincide with levels of suitable fine hierarchies. This gives new short descriptions of these hierarchies and shows that collections of sets of values of Boolean terms are almost wellordered by inclusion. For the sake of completeness we mention also some earlier results demonstrating usefulness of fine hierarchies. 


6 
B. BORCHERT: Abstract. Hertrampf, Lautemann, Schwentick, Vollmer and Wagner 1993 looked at complexity classes characterized by a regular acceptance language for the words of output bits produced by nondeterministic polynomialtime computations. Here the partial order from Zachos 1988 on relativizable complexity classes is considered which reflects the idea of oracle independent inclusion. The main result will be that this partial order on the complexity classes characterized by regular languages is atomic and therefore not dense. The atoms correspond to the classes NP, coNP and MODpP for p prime. 


7 
B. BORCHERT: Abstract. Considering computation trees produced by polynomial time nondeterministic computations one can define a complexity class by any predicate on computation trees, such classes will be called predicate classes. It will be shown that these classes are exactly the principal ideals of the polynomial time manyone reducibility. Additionally, the set of classes  which will be called promise classes  definable by promise functions instead of predicates will be shown to be equal to the set of countable ideals. 


8 
S. LEMPP, A. NIES: Abstract. We show that the Pi4theory of the partial order of recursively enumerable weak truthtable degrees is undecidable, and give a new proof of the similar fact for r.e. Tdegrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters. 


9 
V. SELIVANOV: Abstract. By a result of J.Kadin the difference hierarchy over NP does not collapse if the polynomial hierarchy does not collapse. We extend this to a natural refinement of the polynomial hierarchy of length omega exp. omega. This refinement is generated from the levels of the polynomial hierarchy by the addition modulo 2 and is called here the plushierarchy. We consider also two refinements of the plushierarchy and discuss their possible applicability to the classification of some languages. 


10 
V. SELIVANOV: Abstract. We state some general facts on r.e. structures, e.g. we show that the free countable structures in quasivarieties are r.e. and construct acceptable numerations and universal r.e. structures in quasivarieties. The last facts are similar to the existence of acceptable numerations of r.e. sets and creative sets. We state a universality property of the acceptable numerations, classify some index sets and discuss their relation to other decision problems. These results show that the r.e. structures behave in some respects better than the recursive structures. 


11 
K. AMBOSSPIES, H.C. NEIS, S. A. TERWIJN: Abstract. Recently Lutz introduced a polynomial time bounded version of Lebesgue measure. He and others used this concept to investigate the quantitative structure of Exponential Time (E=DTIME(2 exp. lin)). Previously, AmbosSpies, Fleischhack and Huwig introduced polynomial time bounded genericity concepts and used them for the investigation of structural properties of NP (under appropriate assumptions) and E. Here we relate these concepts to each other. We show that, for any c greate or equal 1, the class of (n exp. c)generic sets has pmeasure 1. This allows us to simplify and extend certain pmeasure 1results. To illustrate the power of generic sets we take the Small Span Theorem of Juedes and Lutz as an example and prove a generalization for bounded query reductions. 


12 
K. AMBOSSPIES: Abstract. Safe and unsafe polynomial time approximations were introduced by Meyer and Paterson [4] and Yesha [8], respectively. The question of which sets have optimal safe approximations was investigated by several authors (see e.g. [3,6,7]). Recently Duris and Rolim [2] considered the unsafe case and compared the existence of optimal polynomial time approximations for both cases. They left open the question, however, whether there are intractable sets with optimal unsafe approximations and whether there are sets with optimal unsafe approximations but without optimal safe approximations. Here we answer these questions affirmatively. Moreover, we consider a variant of Duris and Rolim's Deltalevelability concept related to the nonexistence of optimal unsafe approximations. 


13 
V.SELIVANOV: Abstract. We survey the current stage in the investigation of precomplete numerations and of some their subclasses. Recent results show that many naturally arising numerations are in a sense universal in a suitable class of precomplete numerations. This remarkable fact leads to deep manyfold connections and applications of precomplete numerations to other topics e.g. to hierarchies, index sets, degree structures and fixed point free degrees. We describe these applications in detail, so the paper is also a partial survey of the listed topics. 


14 
V. SELIVANOV: Abstract. By applying descriptive set theory we get several facts on the fine structure of regular omegalanguages considered by K.Wagner. We present quite different, shorter proofs for main his results and get new results. Our description of the fine structure is new, very clear and automatafree. We prove also a closure property of the fine structure under Boolean operations. Our results demonstrate deep interconnections between descriptive set theory and theory of omegalanguages. 


15 
K. AMBOSSPIES, S. A. TERWIJN, X. ZHENG: Abstract. We introduce and study resource bounded random sets based on Lutz«s concept of resource bounded measure. We concentrate on (n exp. c)randomness (c greater or equal 1) which corresponds to the polynomial time bounded (p) measure and which is adequate for studying the internal and quantitative structure of E=DTIME(2 exp. lin). However we will also comment on E2 = DTIME(2 exp. poly) and its corresponding (p2) measure. First we show that the class of (n exp. c)random sets has pmeasure 1. This provides a new, simplified approach to pmeasure 1results. Next we compare randomness with genericity (in the sense of AmbosSpies, Fleischhack and Huwig) and we show that (n exp. (c+1))random sets are (n exp. c)generic whereas the converse fails. From the former we conclude that (n exp. c)random sets are not pbttcomplete for E. Our technical main results describe the distribution of the (n exp. c)random sets under pmreducibility. We show that every (n exp. c)random set in E has (n exp. k)random predecessors in E for any k greater or equal 1 whereas the amount of randomness of the successors is bounded. We apply this result to answer a question raised by Lutz: We show that the class of weakly complete sets has measure 1 in E and that there are weakly complete problems which are not pbttcomplete for E. 


16 
K. AMBOSSPIES: Abstract. Resourcebounded genericity concepts have been introduced by AmbosSpies, Fleischhack and Huwig [AFH84], [AFH88], Lutz [Lu90], and Fenner [Fe91]. Though it was known that some of these concepts are incompatible, the relations among these notions were not fully understood. Here we survey these notions and clarify the relations among them by specifying the types of diagonalizations captured by the individual concepts. Moreover, we introduce two new, stronger resourcebounded genericity concepts corresponding to fundamental diagonalization concepts in complexity theory. First we define general genericity, which generalizes all of the previous concepts and captures both, standard finite extension arguments and slow diagonalizations. The second new concept, extended genericity, actually is a hierarchy of genericity concepts for a given complexity class which extends general genericity and in addition captures delayed diagonalizations. Moreover, this hierarchy will show that in general there is no strongest genericity concept for a complexity class. A similar hierarchy of genericity concepts was independently introduced by Fenner [Fe95]. Finally we study some properties of the Baire category notions on E induced by the genericity concepts and we point out some relations between resourcebounded genericity and resourcebounded randomness. 


17 
B. BORCHERT, A. LOZANO: Abstract. This note connects two topics of Complexity Theory: The topic of succinct circuit representations initiated by Galperin and Wigderson [GW83], and the topic of leaf languages initiated by Bovet et al. [BCS92]. A graph with n nodes can  in the obvious way  be represented more succinctly by a circuit with 2logn input variables which assumes that the nodes are encoded and describes which nodes are connected by edges. This idea can be generalized from graphs to words, so that a circuit describes a word which is possibly exponentially longer. In this note the concept is slightly modified by shifting the length indicator from the circuit output to the problem input. This way, each language A determines its succinct version S(A) consisting of the coded pairs where c is a circuit and m is a binary number such that the lengthm prefix of the word described by c is in A. In Bovet et al. [BCS92] it is shown how any language A (the leaf language) determines a complexity class C(A). It will be shown for any language A that its succinct version S(A) is polynomialtime manyone complete for C(A). 


18 
B. BORCHERT, D. RANJAN, F. STEPHAN: Abstract. The paper analyzes in terms of polynomial time manyone 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 coNP and Sigmap2. 


19 
F. STEPHAN: Abstract. A learner noisily infers a function or set, if every correct item is presented infinitely often while in addition some incorrect data ("noise") is presented a finite number of times. It is shown that learning from a noisy informant is equal to finite learning with Koracle from a usual informant. This result has several variants for learning from text and using different oracles. Furthermore, partial identification of all r.e. sets can cope also with noisy input. 


20 
F. STEPHAN: Abstract. Inductive inference considers two types of queries: Queries to a teacher about the function to be learned and queries to a nonrecursive oracle. This paper combines these two types  it considers three basic models of queries to a teacher (QEX[Succ], QEX[<] and QEX[+]) together with membership queries to some oracle. The results for each of these three models of queryinference are the same: If an oracle is omniscient for queryinference then it is already omniscient for EX. There is an oracle of trivial EXdegree, which allows nontrivial queryinference. Furthermore, queries to a teacher can not overcome differences between oracles and the queryinference degrees are a proper refinement of the EXdegrees. In the case of finite learning, the queryinference degrees coincide with the Turing degrees. Furthermore oracles can not close the gap between the different types of queries to a teacher. 


22 
K. AMBOSSPIES, E. MAYORDOMO: Abstract. We survey recent results on resourcebounded measure and randomness in structural complexity theory. In particular, we discuss applications of these concepts to the exponential time complexity classes $\mbbe$ and $\mbbe_2$. Moreover, we treat timebounded genericity and stochasticity concepts which are weaker than timebounded randomness but which suffice for many of the applications in complexity theory. 


23 
B. BORCHERT, F. STEPHAN: Abstract. 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 UPhard with respect to polynomialtime Turing reductions. 


24 
W. MERKLE: Abstract. In an attempt to give a unified account of common properties of various resource bounded reducibilities, we introduce conditions on a binary relation \le_{r} between subsets of the natural numbers where \le_{r} is meant as a resource bounded reducibility. The conditions are a formalization of basic features shared by most resource bounded reducibilities which can be found in the literature. As our main technical result, we show that these conditions imply a result about exact pairs which has been previously shown by AmbosSpies in a setting of polynomial time bounds: given some recursively presentable \le_{r}ideal \cal{I} and some recursive \le_{r}hard set B for \cal{I} which is not contained in \cal{I}, there is some recursive set C where B and C are an exact pair for \cal{I}, that is, \cal{I} is equal to the intersection of the lower \le_{r}cones of B and C where C is not in \cal{I}. In particular, if the relation \le_{r} is in addition transitive and there are least sets, then every recursive set which is not in the least degree is half of a minimal pair of recursive sets. 


25 
F. STEPHAN: Abstract. Onesided classifiers are computable devices which read the characteristic function of a set and output a sequence of guesses which converges to 1 iff the set on the input belongs to the given class. Such a classifier is twosided if the sequence of its output in addition converges to 0 on sets not belonging to the class. The present work obtains the below mentioned results for onesided classes (= $\Sigma^0_2$ classes) w.r.t.\ four areas: Turing complexity, 1reductions, index sets and measure. There are onesided classes which are not twosided. This can have two reasons: (1) the class has only high Turing complexity. Then there are some oracles which allow to construct noncomputable twosided classifiers. (2) The class is difficult because of some topological constraints and then there are also no nonrecursive twosided classifiers. For case (1), several results are obtained to localize the Turing complexity of certain types of onesided sets. The concepts of 1reduction, 1completeness and simple sets is transferred to onesided classes: There are 1complete classes and simple classes, but no class is at the same time 1complete and simple. The onesided classes have a natural numbering. Most of the common index sets relative to this numbering have the high complexity $\Pi^1_1$: the index sets of the class $\{0,1\}^{\infty}$, the index set of the equality problem and the index set of all twosided classes. On the other side the index set of the empty class has complexity $\Pi^0_2$; $\Pi^0_2$ and $\Sigma^0_2$ are the least complexities any nontrivial index set can have. Any onesided class is measurable. It is shown that a onesided class has effective measure 0 if it has measure 0, but that there are onesided classes having measure 1 without having measure 1 effectively. The measure of a twosided class can be computed in the limit. 


26 
S. KAUFMANN, F. STEPHAN: Abstract. The present work investigates Gold style algorithmic learning from inputoutput examples whereby the learner has access to oracles as additional information. Furthermore this access has to be robust, that means that a single learning algorithm has to succeed with every oracle which meets a given specification. The first main result considers oracles of the same Turing degree: Robust learning with any oracle from a given degree does not achieve more than learning without any additional information. The further work considers learning from function oracles which describe the whole class of functions to be learned in one of the following four ways: the oracle is a list of all functions in this class or a predictor for this class or a onesided classifier accepting just the functions in this class or a martingale succeeding on this class. It is shown that for learning in the limit (Ex), lists are the most powerful additional information, the powers of predictors and classifiers are incomparable and martingales are of no help at all. Similar results are obtained for the criteria of predicting the next value, finite, Popperian and finite Popperian learning. Lists are omniscient for the criterion of predicting the next value but some classes can not be Exlearned with any of these types of additional information. The class REC of all recursive functions is Exlearnable with the help of a list, a predictor or a classifier. 


27 
W. MERKLE: Abstract. We introduce the notion bounded relation which comprises most resource bounded reducibilities to be found in the literature, including nonuniform reducibilities such as $\le ^{{\cal P}/poly}$. We state conditions on bounded relations which imply that every countable partial ordering can be embedded into every proper interval of the recursive sets, respectively functions. As corollaries, e obtain that every countable partial ordering can be embedded into every proper interval of $(REC,\le^{{\cal P}/poly}$, as well as into every proper interval between two maximization, respectively two minimization problems in the structures $(NPO,\le_E)$ and $(NPO,\le_L)$. We derive the results on the two latter structures by first representing maximization and minimization problems, respectively, by functions in $\omega^\omega$, then showing that the reducibilities induced on $\omega^\omeg$ by the relations $\le_L$ and $\le_E$ satisfy our assumptions. For these relations, we show further that the result about partial order embeddings extends to lattice embeddings of arbitrary countable distributive lattices where in addition the least or the greatest element of the lattice can be preserved. Among other corollaries, we obtain from the result on lattice embedding that every nontrivial $\cal NP$ optimization problem bounds a minimal pair. 


28 
K. AMBOSSPIES, J. REIMANN: Abstract. Mehlhorn (1973) introduced an effective Baire category concept designed for measuring the size of classes of computable sets. This concept is based on effective extension functions. By considering partial extension functions, we introduce a stronger concept. Similar resourcebounded concepts have been previously introduced by AmbosSpies et al. (1988) and AmbosSpies (1996). By defining a new variant of the BanachMazur game, we give a game theoretical characterization of our category concept. 


29 
F. STEPHAN: Abstract. The following theorems on the structure inside nonrecursive truthtable degrees are established: D\"egtev's result that the number of bounded truthtable degrees inside a truthtable degree is at least two is improved by showing that this number is infinite. There are even infinite chains and antichains of bounded truthtable degrees inside the truthtable degrees which implies an affirmative answer to a question of Jockusch whether every truthtable degree contains an infinite antichain of manyone degrees. Some but not all truthtable degrees have a least bounded truthtable degree. The technique to construct such a degree is used to solve an open problem of Beigel, Gasarch and Owings: there are Turing degrees (constructed as hyperimmunefree truthtable degrees) which consist only of 2subjective sets and do therefore not contain any objective set. Furthermore a truthtable degree consisting of three positive degrees is constructed where one positive degree consists of enumerable semirecursive sets, one of coenumerable semirecursive sets and one of sets, which are neither enumerable nor coenumerable nor semirecursive. So Jockusch's result that there are at least three positive degrees inside a truthtable degree is optimal. The number of positive degrees inside a truthtable degree can also be some other odd integers as for example nineteen, but it is never an even finite number. 


30 
K. AMBOSSPIES, L. BENTZIEN:
Abstract. Lutz[16] proposed the study of the structure of the class NP=NTIME(poly) under the hypothesis that NP does not have pmeasure 0 (with respect to Lutz's resource bounded measure [15]). Lutz and Mayordomo [18] showed that, under this hypothesis, NPmcompleteness and NPTcompleteness differ, and they conjectured that further NPcompleteness notions can be separated. Here we prove this conjecture for the boundedquery reducibilities. In fact we consider a new weaker hypothesis, namely the assumption that NP is not pmeager with respect to the resource bounded Baire category concept of AmbosSpies et al. [2]. We show that this category hypothesis is sufficient to get: 


31 
A.S. MOROZOV:
Abstract. We study the interplay between Turing degrees $\bd$ and nontrivial factors of groups of all $\bd$recursive permutations. We prove that the isomorphism type of any such factor group completely determines the degree $\bd$ and describe the definability of Turing degrees by elementary properties of these groups. 


32 
W. GASARCH, F. STEPHAN: Abstract. The present work gives an overview on the field of Bounded Queries including the subfields of frequency computation and verboseness. The main topic is finding quantitative notions for the complexity of nonrecursive sets in terms of the local complexity of computing the nfold characteristic function. This work presents in particular the various proof methods popular in this field. 


33 
W. MERKLE: Abstract. We give an abstract account of resource bounded reducibilities as exemplified by the polynomial time or logarithmically space bounded reudcibilities of Turing, truthtable, and many one type. We introduce a small set of axioms which are satisfied for most of the specific resource bounded reducibilities which appear in the literature. Some of the axioms are of a more algebraic nature, such as the requirement that the reducibility under consideration is a reflexive relation, while others are formulated in terms of recursion theory and for example are related to delayed computations of arbitrary recursive sets. We discuss basic consequences of these axioms and their relation to previous axiomatic approaches by Mehlhorn [31], Schmidt [41], Mueller [37], and, in a context of relativized Blum measure, by Lynch et al. [26]. As main technical result we show that for every reducibility which satisfies our axioms, every countable distributive lattice can be embedded into every proper interval of the structure induced on the recursive sets. This result extends a corresponding result for polynomial time bounded reducibilities due to AmbosSpies [1], as well as work by Mehlhorn [31]. Mehlhorn shows from an apparently more restricitve set of assumptions that the recursive sets form a dense structure and claims that in fact every countable partial ordering can be embedded into every proper interval of the recusive sets. 


34 
F. STEPHAN, Y. VENTSOV:
Abstract. The present work investigates the learnability of classes of substructures of some algebraic structure: submonoids and subgroups of some given group, ideals of some given commutative ring, subfields of a vector space. The learner sees all positive data but no negative one and converges to a program enumerating or computing the set to be learned. Besides semantical (BC) and syntactical (Ex) convergence also the more restrictive ordinal bounds on the number of mind changes are considered. The following is shown: 


35 
A. NIES: 


36 
A. MOROZOV: Abstract. We consider the groups of Sigmapresentable permutations of recursively listed locally countable admissible sets. We prove that such groups are not Sigmapresentable over their admissible sets, prove all their automorphisms to be inner, and describe the normal structure of these groups. 


37 
A. MOROZOV:
Abstract. We suggest a notion of Sigmadefinability of an admissible set in another admissible set, prove the correctness of this notion, and give the grouptheoretic criterion of Sigmadefinability of one admissible set in another, for some class of admissible sets. Considering an admissible set as some computational capacity, we can say that the groups introduced in the paper as invariants are uniform measures of the computational power for admissible sets. 


38 
K. AMBOSSPIES: Abstract. In [1] Weihrauch and Zheng compare some notions of recursively approximable real numbers. Their two main results  stated in the terminology of [1]  are: There is a weakly computable real number which is not semicomputable, and there is a recursively enumerable real number which is not weakly computable. In [1] these theorems are directly proved by finiteinjury arguments, where the proof of the first result uses the observation that the real corresponding to a dr.e. set is weakly comutable. Here, by further exploring the relations between the computability properties of a real number and the location of the corresponding set in the difference hierarchy over the r.e. sets, we show that the two main results in [1] can be obtained from theorems on the r.e., dr.e., and omegar.e. degrees in the literature. 


39 
F. STEPHAN, S.A. TERWIJN: Abstract. The present work deals with language learning from text. It considers universal learners for classes of languages in models of additional information and analyzes their complexity in terms of Turingdegrees. The following is shown: If the additional information is given by a set containing at least one index for each language from the class to be learned but no index for any language outside the class then there is a universal learner having the same Turing degree as the inclusion problem for recursively enumerable sets. This result is optimal in the sense that any further learner has the same or higher Turing degree. If the additional information is given by the index set of the class of languages to be learned then there is a computable universal learner. Furthermore, if the additional information is presented as an upper bound on the size of some grammar that generates the language then a high oracle is necessary and sufficient. Finally, it is shown that for the concepts of finite learning and learning from good examples, the index set of the class to be learned gives insufficient information: these criteria need due to the restrictive convergenceconstraints the jump of the index set instead of the index set itself. So they have infinite access to the information of the index set in finite time. 


40 
J. CASE, S. JAIN, S. KAUFMANN, A. SHARMA, F. STEPHAN: Abstract. Concept drift means that the concept about which data is obtained may shift from time to time, each time after some minimum permanence. Except for this minimum permanence, the concept shifts may not have to satisfy any further requirements and may occur infinitely often. Within this work is studied to what extent it is still possible to predict or learn values for a data sequence produced by drifting concepts. Various ways to measure the quality of such predictions, including martingale betting strategies and density and frequency of correctness, are introduced and compared with one another. For each of these measures of prediction quality, for some interesting concrete classes, usefully established are (nearly) optimal bounds on permanence for attaining learnability. The concrete classes, from which the drifting concepts are selected, include regular languages accepted by finite automata of bounded size, polynomials of bounded degree, and exponentially growing sequences defined by recurrence relations of bounded size. Some important, restricted cases of drifts are also studied, for example, the case where the intervals of permanence are computable. In the case where the concepts shift only among finitely many possibilities from certain infinite, arguably practical classes, the learning algorithms can be considerably improved. 


41 
K. AMBOSSPIES, L. BENTZIEN, P. A. FEJER, W. MERKLE, F. STEPHAN: Abstract. For reducibilities r and s such that r is weaker than s, we say that the rdegree of A, i.e., the class of sets which are requivalent to A, collapses to the sdegree of A if both degrees coincide. We investigate for the polynomialtime bounded manyone, bounded truthtable, truthtable, and Turing reducibilities whether and under which conditions such collapses can occur. While we show that such collapses do not occur for sets which are hard for exponential time, we have been able to construct a recursive set such that its bounded truthtable degree collapses to its manyone degree. The question whether there is a set such that its Turing degree collapses to its manyone degree is still open; however, we show that such a set  if it exists  must be recursive. 


42 
W. MERKLE, Y. WANG: Abstract. Let C be the class of all sets (of natural numbers) and let $\le_r$ and $\le_s$ be two binary relations on C which are meant as reducibilities. Let both relations be closed under finite variation (of their set arguments) and consider the uniform distribution on C, which is obtained by choosing elements of C by independent tosses of a fair coin. Then we might ask for the probability that the lower $\le_r$cone of a randomly chosen set X, that is, the class of all sets A with $A \le_r X$, differs from the lower $\le_s$cone of X. By closure under finite variation, the Kolmogorov 01 law yields immediately that this probability is either 0 or 1; in case it is 1, the relations are said to be separable by random oracles. Again by closure under finite variation, for every given set A, the probability that a randomly chosen set X is in the upper cone of A w.r.t. $\le_r$ is either 0 or 1. Let $Almost_r$ be the class of sets for which the upper cone w.r.t. $\le_r$ has measure 1. In the following, results about separations by random oracles and about Almost classes are obtained in the context of generalized reducibilities, that is, for binary relations on C which can be defined by a countable set of total continuous functionals on C in the same way as the usual resource bounded reducibilities are defined by an enumeration of appropriate oracle Turing machines. The concept of generalized reducibility comprises all natural resource bounded reducibilities, but is more general; in particular, it does not involve any kind of specific machine model or even effectivity. The results on generalized reducibilities yields corollaries about specific resource bounded reducibilities, including several results which have been shown previously in the setting of time or space bounded Turing machine computations. 


43 
B. BORCHERT, R. SILVESTRI: Abstract. Wellknown examples of dot operators are the existential, the counting, and the BPoperator. We will generalize this notion of a dot operator so that every language A will determine an operator A dot. In fact we will introduce the more general notion of promise dot operators for which the BPoperator is an example. Dot operators are a refinement of the leaf language concept because the class determined by a leaf language A equals A dot P. Moreover we are able to represent not only classes but reducibilities, in fact most of the known polynomialtime reducibilities can be represented by dot operators. We show that two languages determine the same dot operator if and only if they are reducible to each other by polylogtime computable monotone projections. 


44 
K. AMBOSSPIES, B. BORCHERT, W. MERKLE, J. REIMANN, F. STEPHAN: Abstract. The report contains the program and 10 research abstracts of talks given on that workshop. 


45 
K. HO, F. STEPHAN: Abstract. We study connections between strong reducibilities and properties of computably enumerable sets such as simplicity. We call a class S of computably enumerable sets bounded iff there is an mincomplete computably enumerable set A such that every set in S is mreducible to A. For example, we show that the class of effectively simple sets is bounded; but the class of maximal sets is not. Furthermore, the class of computably enumerable sets Turing reducible to a computably enumerable set B is bounded iff B is low2. For r = bwtt, tt, wtt and T, there is a bounded class intersecting every computably enumerable rdegree; for r = c, d and p, no such class exists. 


46 
F. STEPHAN:
Abstract. The present work focuses on oracles, in particular on computation and learning with the help of an oracle. Oracles allow the analysis of the difficulty of learning and computing problems. For example, the difficulty to check whether an enumerable set W given by its index e is infinite needs an oracle capable to compute the halting problem relative to the halting problem K. In learning theory, Adleman and Blum (AB91) showed that exactly the high oracles allow to Exlearn the class REC of all total recursive functions. Also the difference between learning models has been analyzed in terms of the oracles necessary to make a problem S learnable with respect to some more pretentious Model 2 provided that the S is already learnable without the help of any oracle with respect to a less pretentious Model 1. The usefulness of the oracles with respect to a computation or learning task induces canonically a degreestructure on the oracles. Such degreestructures are research topics in their own right and there are numerous results on the degreestructures induced by computing (mostly on Turing, enumeration and manyone degrees). The present work (in particular in Chapter 2) gives an overview on the results about the degreestructures induced by learning. 


47 
K. AMBOSSPIES, A. KUCERA: Abstract. We discuss some aspects of algorithmic randomness and state some open problems in this area. The first part is devoted to the question "What is a computably random sequence?" Here we survey some of the approaches to algorithmic randomness and address some questions on these concepts. In the second part we look at the Turing degrees of MartinLöf random sets. Finally, in the third part we deal with relativized randomness. Here we look at oracles which do not change randomness. 


48 
K. AMBOSSPIES, W. MERKLE, J. REIMANN, S.A. TERWIJN: Abstract. We show that there is a set which is almost complete but not complete under polynomialtime manyone (pm) reductions for the class E of sets computable in deterministic time $2^{lin}$. Here a set A in a complexity class C is almost complete for C under some reducibility r if the class of the problems in C which do not rreduce to A has measure 0 in C in the sense of Lutz's resourcebounded measure theory. We also show that the almost complete sets for E under polynomialtime bounded oneone lengthincreasing reductions and truthtable reductions of norm 1 coincide with the almost pmcomplete sets for E. Moreover, we obtain similar results for the class EXP of sets computable in deterministic time $2^{poly}$. 


49 
E. MARTIN, A. SHARMA, F. STEPHAN:
Abstract. The topic of the present work is to study the relationship between the power of the learning algorithms on the one hand, and the expressive power of the logical language which is used to represent the problems to be learned on the other hand. The central question is whether enriching the language results in more learning power. In order to make the question relevant and nontrivial, it is required that both texts (sequences of data) and hypotheses (guesses) be translatable from the ``rich'' language into the ``poor'' one. 


50 
K. AMBOSSPIES, J. REIMANN (Hg.): Abstract. The report contains program, abstracts, and the list of participants of the Workshop Computability and Models, which was held at Heidelberg, 18.20. Januar 2001. 


51 
S. JAIN, F. STEPHAN:
Abstract. The main question addressed in the present work is how to find effectively a recursive function separating two sets drawn arbitrarily from a given collection of disjoint sets. In particular, it is investigated in which cases it is possible to satisfy the following additional constraints: confidence where the learner converges on all datasequences; conservativeness where the learner abandons only definitely wrong hypotheses; consistency where also every intermediate hypothesis is consistent with the data seen so far; setdriven learners whose hypotheses are independent of the order and the number of repetitions of the dataitems supplied; learners where either the last or even all hypotheses are programs of total recursive functions. 


52 
W. MERKLE, F. STEPHAN:
Abstract. We consider, within the framework of inductive inference, the concept of refuting learning as introduced by Mukouchi and Arikawa, where the learner is not only required to learn all concepts in a given class but also has to explicitly refute concepts outside the class. 


53 
S. JAIN, F. STEPHAN: Abstract. Barzdins conjectured that only recursively enumerable classes of functions can be learned robustly. This conjecture, which was finally refuted by Falk, initiated the study of notions of robust learning. The present work surveys research on robust learning and focusses on the recently introduced variants of uniformly robust and hyperrobust learning. Proofs are included for the (already konwn) results that uniformly robust Exlearning is more restictive than robust Exlearning, that uniformly robustly Exlearnable classes are consistently learnable, that hyperrobustly Exlearnable classes are in Num and that some hyperrobustly BClearnable class is not in Num. 


54 
S. JAIN, F. STEPHAN, S.A. TERWIJN: Abstract. Let BC be the model of behaviourally correct function learning as introduced by Barzdins and Case and Smith. We introduce a mind change hierarchy for BC, counting the number of extensional differences in the hypotheses of a learner. We compare the resulting models BC_n to models from the literature and discuss confidence, team learning, and finitely defective hypotheses. Among other things, we prove that there is a tradeoff between the number of semantic mind changes and the number of anomalies in the hypotheses. We also discuss consequences for language learning. In particular we show that, in contrast to the case of function learning, the family of classes that are confidently BClearnable from text is not closed under finite unions. 


55 
V.S. HARIZANOV, F. STEPHAN: Abstract. The central topic of the paper is the learnability of the recursively enumerable subspaces of $V_{\infty }/V$, where $V_{\infty }$ is the standard recursive vector space over the rationals with countably infinite dimension, and $V$ is a given recursively enumerable subspace of $V_{\infty }$. It is shown that certain types of vector spaces can be characterized in terms of learnability properties: $V_{\infty }/V$ is behaviourally correct learnable from text iff $V$ is finite dimensional, $V_{\infty }/V$ is behaviourally correct learnable from switching the type of information iff $V$ is finite dimensional, $0$thin, or $1$thin. On the other hand, learnability from informant does not correspond to similar algebraic properties of a given space. There are $0$thin spaces $W_{1}$ and $W_{2}$ such that $W_{1}$ is not explanatorily learnable from informant and the infinite product $(W_{1})^{\infty }$ is not behaviourally correct learnable, while $W_{2}$ and the infinite product $(W_{2})^{\infty }$ are both explanatorily learnable from informant. 


56 
S. JAIN, F. STEPHAN: Abstract. The present work is dedicated to the study of modes of datapresentation in the range between text and informant within the framework of inductive inference. In this study, the learner alternatingly requests sequences of positive and negative data. We define various formalizations of valid data presentations in such a scenario. We resolve the relationships between these different formalizations, and show that one of these is equivalent to learning from informant. We also show a hierarchy formed (for each of the formalizations studied) by considering the number of switches between requests for positive and negative data. 


57 
W. MERKLE, F. STEPHAN: Abstract. We characterize FIN, EX and BClearning, as well as the corresponding notions of team learning, in terms of isolated branches on effectively given sequences of trees. The more restrictive models of FINlearning and strongmonotonic BClearning are characterized in terms of isolated branches on a single tree. Furthermore, we discuss learning with additional information where the learner receives an index for a strongly recursive tree such that the function to be learned is isolated on this tree. We show that EXlearning with this type of additional information is strictly more powerful than EXlearning. 


58 
F. STEPHAN: Abstract. A set A is MartinLöf random iff the class {A} does not have Sigma^0_1measure 0. A set A is PAcomplete if one can compute relative to A a consistent and complete extension of Peano Arithmetic. It is shown that every MartinLöf random set either permits to solve the halting problem K or is not PAcomplete. This result implies a negative answer to the question of AmbosSpies and Kucera whether there is a MartinLoef random set not above K which is also PAcomplete. 


59 
S. JAIN, W. MENZEL, F. STEPHAN: Abstract. It is wellknown that infinite recursively enumerable sets have infinite recursive subsets. Similarly, one can study the relation between identifiable classes and subclasses which are identifiable under a more restrictive criterion. The chosen framework is inductive inference, in particular the criterion of explanatory learning (Ex) of recursive functions as introduced in Gold in 1967. Among the more restrictive criteria is finite learning, where the learner outputs on every function to be learned exactly one hypthesis which has to be correct. The topic of the present paper are the natural variants (a) and (b) below of the classical question whether a given learning criterion like finite learning is more restrictive than Exlearning. (a) Does every infinite Exidentifiable class have an infinite finitely identifiable subclass? (b) If an infiite Exidentifiable class S has an infinite finitely identifiable subclass, does it necessarily follow that some appropriate learner Exidentifies S as well as finitely identifies an infinte subclass of S? These questions are also treated in the context of ordinal mind change bounds. 


60 
R.G. DOWNEY, D.R. HIRSCHFELDT, A. NIES, F. STEPHAN: Abstract. Solovay showed that there are noncomputable reals $\alpha$ such that $H( \alpha \upharpoonright n) \leq H(1^n)+O(1)$, where $H$ the prefixfree Kolmogorov complexity. Such $H$trivialreals are interesting due to the connection between algorithmic complexity and effective randomness. We give a new, easier construction of an $H$trivial real. We also analyze various computabilitytheoretic properties of the $H$trivial reals, showing for example that no $H$trivial real can compute the halting problem. Therefore, our construction of an $H$trivial computably enumerable set is an easy, injuryfree construction of an incomplete computably enumerable set. Finally, we relate the $H$trivials to other classes of "highly nonrandom" reals that have been previously studied. 


61 
K. AMBOSSPIES, E. BUSSE: Abstract. Algorithmic and resourcebounded Baire category and corresponding genericity concepts introduced in computability theory and computational complexity theory, respectively, have become elegant and powerful tools in these settings. Here we introduce some new genericity notions based on extension functions computable by finite automata which are tailored for capturing diagonalizations over regular sets and functions. We show that the generic sets obtained either by the partial regular extension functions of any given fixed constant length or by all total regular extension of constant length are just the sets with saturated (also called disjunctive) characteristic sequences. Here a sequence $\alpha$ is saturated if every string occurs in $\alpha$ as a substring. We also show that these automatic generic sets are not regular but may be context free. Furthermore, we introduce stronger automatic genericity notions based on regular extension functions of nonconstant length and we show that the corresponding generic sets are biimmune for the classes of regular and context free languages. 


62 
R. BEIGEL, L. FORTNOW, F. STEPHAN: Abstract. A set A is autoreducible if one can compute, for all x, the value A(x) by querying A only at places y different from x. Furthermore, A is infinitelyoften autoreducible if, for infinitely many x, the value A(x) can be computed by querying A only at places y different from x; for all other x, the computation outputs a special symbol to signal that the reduction is undefined. It is shown that for polynomial time Turing and truthtable autoreducibility there are sets A, B, C in EXP such that A is not infinitelyoften Turing autoreducible, B is Turing autoreducible but not infinitelyoften truthtable autoreducible, C is truthtable autoreducible with g(n)+1 queries but not infinitelyoften Turing autoreducible with g(n) queries. Here n is the length of the input, g is nondecreasing and there exists a polynomial p in n that bounds the computation time and values of g. Furthermore, connections between notions of infinitelyoften autoreducibility and notions of approximability are investigated. The Hausdorffdimension of the class of sets which are not infinitelyoften autoreducible is shown to be 1. 


63 
A. NIES, J. REIMANN: Abstract. For any rational number r, we show that there exists a set A (weak truthtable reducible to the halting problem) such that any set B weak truthtable reducible to it has effective Hausdorff dimension at most r, where A itself has dimension at least r. This implies, for any rational r, the existence of a wttlower cone of effective dimension r. 


64 
D. R. HIRSCHFELDT, A. NIES, F. STEPHAN: Abstract. Let R be a notion of algorithmic randomness for individual subsets of the natural numbers. We say B is a base for Rrandomness if there is a Z such that Z is Rrandom relative to B and B is Turing reducible to Z.We show that the bases for 1randomness are exactly the Ktrivial sets and discuss several consequences of this result. We also show that the bases for computable randomness include every set Turing reducible to the halting problem that is not diagonally noncomputable, but no set of PAdegree. As a consequence, we conclude that any difference of finitely computably enumerable set is a base for computable randomness iff it is Turing incomplete. 