Arbeitsgruppe Mathematische Logik und Theoretische Informatik

Oberseminar Wintersemester 2002/2003

Die Vorträge sind üblicherweise dienstags um 16 Uhr c.t. in Raum 134 des Gebäudes INF 294.
(The talks are usually on Tuesday at 4 p.m. in Room 134 of building INF 294.)


Vorträge / Talks	Mittwoch, 2. Oktober 2002, 10.15 h, INF 294, HS 134 Theodore A. Slaman, University of California $\Sigma_n$-Bounding and $\Delta_n$-Induction
	Freitag, 11. Oktober 2002, 10.15 h, INF 294, HS 134 Sasha Rubin, University of Auckland Techniques proving non-automaticity
	Dienstag 22. Oktober 2002, 17.15 h, INF 294, HS 134 und Freitag 25. Oktober 2002, 9.15 h, INF 294, HS -104 Bakhadyr Khoussainov, University of Auckland Computably Enumerable Algebras, Abstract Data Types, and Specifications
	Mittwoch, 23. Oktober 2002, 17.15 h, INF 294, HS 134 Cristian S. Calude, University of Auckland Computing a Glimpse of Randomness
	5. November 2002 Frank Stephan, Universität Heidelberg Classes with Easily Learnable Subclasses
	12. November 2002 Frank Stephan, Universität Heidelberg Learning Algebraic Structures
	19. November 2002 Frank Stephan, Universität Heidelberg Martin-Löf Random and PA-complete Sets
	Freitag, 29. November 2002, 11.15 h, INF 294, HS 134 Valentina Harizanov, George Washington University, Washington D.C. Algorithmic Complexity of Countable Models
	10. Dezember 2002 Sergey Goncharov, Institute of Mathematics, SBRAS, Novosibirsk Computable Numberings of Definable Relations in Models
	7. Januar 2003 Jan Reimann, Universität Heidelberg Effective Geometric Measure Theory
	14. Januar 2003 Bakhadyr Khoussainov, University of Auckland Games Played on Finite Graphs
	28. Januar 2003 Theodore A. Slaman, University of California Recursion Theoretic Aspects of Ramsey's Theorem
	4. Februar 2003 Daniel Reidenbach, Universität Kaiserslautern Nondeterminism of Extended Pattern Languages and Inductive Inference
	11. Februar 2003 Sandra Zilles, Universität Kaiserslautern Increasing the Power of Uniform Learners
	Donnerstag, 20. Februar 2003, 13.15 h, INF 294, HS 134 Steffen Lempp, University of Wisconsin Computability-theoretic and Proof-theoretic Aspects of Partial and Linear Orderings
	25. Februar 2003, 16.15 h, INF 294, HS -104 Frank Stephan, Universität Heidelberg On the Structures Inside Truth-Table Degrees

2. Oktober	Theodore A. Slaman, University of California $\Sigma_n$-Bounding and $\Delta_n$-Induction Working in the base theory of $P^- + I\Sigma_0 + EXP$, we show that for all $n\in\omega$, the bounding principle for $\Sigma_n$ formulas ($B\Sigma_n$) is equivalent to the induction principle for $\Delta_n$ formulas ($I\Delta_n$).
11. Oktober	Sasha Rubin, University of Auckland Techniques proving non-automaticity We will review the known methods of proving that a particular structure is not automatic. In particular, we prove the following results: 1. The random graph has no automatic presentation. 2. Every automatic scattered linear ordering has finite VD-rank. 3. Every automatic finitely branching tree with countably many infinite paths has finite CB-rank.
22/25. Oktober	Bakhadyr Khoussainov, University of Auckland Computably Enumerable Algebras, Abstract Data Types, and Specifications In these two talks we discuss long standing open problems of Bergstra and Tucker about specifications of abstract data types by equations and quasi equations. The thesis that identifies abstract data types with the isomorphism types of computably enumerable (c.e.) algebras turns the problems into problems about c.e. algebras. We develop a theory of c.e. algebras, provide some new techniques, ideas, and views needed for the study and solution of the specification problems.
23. Oktober	Cristian S. Calude, University of Auckland Computing a Glimpse of Randomness Chaitin Omega Numbers are halting probabilities of universal self-delimiting Turing machines. They have been described as numbers which "can be known of, but not known, through human reason." The talk will review the main properties of Omega Numbers and will describe the main steps (mathematical and programming) leading to the computation of 64 exact bits of a (natural) Omega Number.
5. November	Frank Stephan, Universität Heidelberg Classes with Easily Learnable Subclasses Let Ex denote the explanatory model of learning. Various more restrictive models have been studied in the literature, an example is identification. The topics of the present paper are the natural variants (a) and (b) below of the classical question whether a given learning criterion is more restrictive than Ex-learning. (a) Does every infinite Ex-identifiable class have an infinite subclass which can be identified according to a given restrictive criterion? (b) If an infinite Ex-identifiable class S has an infinite finitely identifiable subclass, does it necessarily follow that some appropriate learner Ex-identifies S as well as finitely identifies an infinite subclass of S? These questions are also treated in the context of ordinal mind change bounds. Joint work with Sanjay Jain and Wolfram Menzel.
12. November	Frank Stephan, Universität Heidelberg Learning Algebraic Structures The talk gives an introduction to the speaker's work on learning substructures of given algebraic structures. Such substructures are for example the class of all ideals of a Noetherian recursive ring or the class of all recursively enumerable subspaces of a given vector space. It turns out that there are strong connections between learnability properties of the class of substructures and effective algebraic properties of the considered structure. In the case of recursive rings, behaviourally correct learnability of all ideals corresponds to the ring being Noetherian while explanatory learnability with a constant number of mind changes corresponds to the ring being Artinian. For vector spaces, besides learnability from text also behaviourally correct learnability by switching type of information (introduced by Jain and Stephan 2001) is considered and corresponds to the effective algegraic property that the vector space is finite dimensional, 0-thin or 1-thin. Joint work with Valentina Harizanov, Sanjay Jain and Yuri Ventsov.
19. November	Frank Stephan, Universität Heidelberg Martin-Löf Random and PA-complete Sets A set A is Martin-Löf random iff it is contained in a class of Sigma^0_1-measure 0. A set A is PA-complete if one can compute relative to A a consistent and complete extension of Peano Arithmetic. It is shown that every Martin-Löf random set either permits to solve the halting problem K or is not PA-complete. This result implies a negative answer to the question of Ambos-Spies and Kucera whether there is a Martin-Löf random set not above K which is also PA-complete.
29. November	Valentina Harizanov, George Washington University, Washington D.C. Algorithmic Complexity of Countable Models For a countable structure in a computable language, we define the n--diagram to be the set of all true $\Sigma _{n}^{0}$ sentences in the language expanded by constants for elements of the domain. The (n+1)-diagram is c.e. in and above its n-diagram, uniformly in n. A structure is n-decidable if its n-diagram is computable. Hence 0-decidable structures are the computable ones. A structure is decidable if its elementary diagram is computable. For every n, there are n-decidable structures, which do not have (n+1)-decidable isomorphic copies. There are also structures that are n-decidable for every n, but do not have decidable isomorphic copies. We give general definability conditions, which in all isomorphic copies, guarantee that the elementary diagram and the n-diagram are Turing equivalent. We establish a similar result for the n-diagram and (n+1)-diagram. We show that every countable structure has an isomorphic copy in which the atomic diagram and the elementary diagram are Turing equivalent. We are especially interested in the sequences of Turing degrees of the n-diagrams of isomorphic copies of a given structure. Joint work with Julia Knight and Andrei Morozov.
10. Dezember	Sergey Goncharov, Institute of Mathematics, SBRAS, Novosibirsk Computable Numberings of Definable Relations in Models We will discuss some problems in the theory of computable numberings. We will consider the classical case of computable numberings of c.e. sets and some generalizations of definable relations on models. We will study algebraic and elementary properties of Roger's semilattices of $\Sigma$-computable numberings, in particular, the problem of cardinality, existence of minimal elements, number of minimal elements, cover of elements, limit property of principal numberings, decidability of elementary theories, elementary and isomorphic types of Roger's semilattices of arithmetical computable numberings. Joint work with Serikzhan Badaev (Almaty) and Andrea Sorbi (Siena).
7. Januar	Jan Reimann, Universität Heidelberg Effective Geometric Measure Theory Geometric measure theory studies the geometry of sets by measure theoretic means. It became prominent as the mathematical foundation of fractal geometry, i.e. the study of non-rectifiable sets. A basic approach consists in employing measures with geometric scaling factors, yielding for instance the fundamental concept of Hausdorff measures. While connections and applications of geometric measure theory to the calculus of variations, to dynamical systems and even to number theory were known for quite some time, work by Staiger, Ryabko, Cai and Hartmanis and recently by Lutz shed light on a close relationship between Hausdorff measure and Kolmogorov complexity, leading also to an introduction of effective notions of geometric measure theory. In this talk, these effective notions will be studied in a general setting, provided by semimeasures. We introduce the notion of Hausdorff dimension and its effective counterpart. We will give some examples of fractal sets stemming from the realm of computability, complexity, and number theory. Finally, we present a first classification of sets of effective fractal dimension, in the sense that they can be understood as sequences which allow to a certain degree the extraction of randomness.
14. Januar	Bakhadyr Khoussainov, University of Auckland Games Played on Finite Graphs We introduce McNaughton games played on finite graphs. McNaughton games can be used to model computational problems and study some important concepts (e.g. reactive systems) that arise in computer science. Questions related to realization and correctness of specifications, correct control synthesis, and optimization of control can all be studied using McNaughton games. These games are also of interest in logic because of their close connection to the monadic second order logic of the full binary tree (S2S) and the temporal logic. In this talk we discuss some algorithms that decide certain natural classes of games and pose a couple of known open questions in the area. The work is joint with Dinneen (Auckland), Boadlander (Utrecht) and Ishihara (JAIST).
28. Januar	Theodore A. Slaman, University of California Recursion Theoretic Aspects of Ramsey's Theorem The infinite form of Ramsey's Theorem asserts the following. For all natural numbers n and e, and for all functions F from the size e subsets of the natural numbers into {0,...,n-1}, there is an infinite homogeneous set H such that for any two size e subsets s_1 and s_2 of H, F(s_1)=F(s_2). Even in the simplest instance (e=n=2), Ramsey's Theorem is not effective. There is a recursive F defined on pairs such that no infinite recursive set H is homogeneous for F. (Even stronger statements are true.) In contrast, we will show that for every such F there is an infinite homogeneous set H such that H is low-2. To the extent that time permits, we will discuss applying the proof to theory of fragments of second order arithmetic.
4. Februar	Daniel Reidenbach, Universität Kaiserslautern Nondeterminism of Extended Pattern Languages and Inductive Inference Pattern languages have been a focus of attention of both formal language theory and algorithmic learning theory. One of the major unresolved problems deriving from these studies was that of the learnability of extended (or: erasing) pattern languages. In the lecture the definition of pattern languages, Gold's learning model and Angluin's criteria on language learning are explained. As main result the question of learnability of extended pattern languages is answered in a negative way presenting a non-learnable subclass. In order to achieve this result the impact of certain ambiguous words in extended pattern languages and of the size of the corresponding terminal alphabet is analysed. Furthermore a glance is taken at some additional positive results, new conjectures and open questions concerning inductive inference of extended pattern languages.
11. Februar	Sandra Zilles, Universität Kaiserslautern Increasing the Power of Uniform Learners The analysis of theoretical learning models is basically concerned with the comparison of identification capabilities in different models. Modifications of the formal constraints affect the quality of the corresponding learners on the one hand and regulate the quantity of learnable classes on the other hand. For many inductive inference models - such as Gold's identification in the limit - the corresponding relationships of learning potential provided by the compatible learners are well-known. Recent work even corroborates the relevance of these relationships by revealing them still in the context of uniform Gold-style learning. Uniform learning is rather concerned with the synthesis of successful learners instead of their mere existence. The scope of the talk is to show how to further strengthen the results regarding uniform learning, particularly aiming at the design of methods for increasing the potential of the relevant learners. This demonstrates how to improve given learning strategies instead of just verifying the existence of more powerful uniform learners.
20. Februar	Steffen Lempp, University of Wisconsin Computability-theoretic and Proof-theoretic Aspects of Partial and Linear Orderings Szpilrajn's Theorem states that any partial order P = (S, <P) has a linear extension L = (S, <L). This is a central result in the theory of partial orderings, allowing one to define, for instance, the dimension of a partial ordering. It is now natural to ask questions like "Does a well-partial ordering always have a well-ordered linear extension?" Variations of Szpilrajn's Theorem state, for various (but not for all) linear order types tau, that if P does not contain a subchain of order type tau, then we can choose L so that L also does not contain a subchain of order type tau. In particular, a well-partial ordering always has a well-ordered extension.
20. Februar	Frank Stephan, Universität Heidelberg On the Structures Inside Truth-Table Degrees The following theorems on the structure inside nonrecursive truth-table degrees are established: Degtev's result that the number of bounded truth-table degrees inside a truth-table degree is at least two is improved by showing that this number is infinite. There are even infinite chains and antichains of bounded truth-table degrees inside every truth-table degree. The latter implies an affirmative answer to the following question of Jockusch: does every truth-table degree contain an infinite antichain of many-one degrees? Some but not all truth-table degrees have a least bounded truth-table 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 hyperimmune-free truth-table degrees) which consist only of 2-subjective sets and therefore do not contain any objective set. Furthermore, a truth-table degree consisting of three positive degrees is constructed where one positive degree consists of enumerable semirecursive sets, one of co-enumerable semirecursive sets and one of sets, which are neither enumerable nor co-enumerable nor semirecursive. So Jockusch's result that there are at least three positive degrees inside a truth-table degree is optimal. The number of positive degrees inside a truth-table degree can also be some other odd integer as for example nineteen, but it is never an even finite number.

Zurück

Startseite der Arbeitsgruppe

Verantwortlich: Jan Reimann

Letzte Änderung: 21. Februar 2002

Arbeitsgruppe Mathematische Logik und Theoretische Informatik

Vorträge / Talks

2. Oktober

11. Oktober

22/25. Oktober

23. Oktober

5. November

12. November

19. November

29. November

10. Dezember

7. Januar

14. Januar

28. Januar

4. Februar

11. Februar

20. Februar

20. Februar