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


Die Seite befindet sich im Aufbau

 

Vorträge

15. Mai 2012, 15:50 Uhr, HS 134, AM

Lutz Büch, Universität Heidelberg
\Pi^0_1-Klassen und Turinggrade


22. Mai 2012, 16 Uhr c.t., HS 134, AM

Klaus Ambos-Spies, Universität Heidelberg
On the strongly bounded Turing degrees of c.e. sets: Degrees inside degrees (Part 1: On the c.e. cl-degrees inside a single c.e. wtt-degree)


29. Mai 2012, 16 Uhr c.t., HS 134, AM

Klaus Ambos-Spies, Universität Heidelberg
On the strongly bounded Turing degrees of c.e. sets: Degrees inside degrees (Part 2: On the c.e. ibT-degrees inside a single c.e. cl-degree)


5. Juni 2012, 16 Uhr c.t., HS 134, AM

Frank Stephan, National University of Singapore
The Complexity of Verbal Languages over Groups


19. Juni 2012, 16 Uhr c.t., HS 134, AM

Andrey Morozov, Sobolev Institute of Mathematics, Novosibirsk
On Sigma-definability of structures over the reals


26. Juni 2012, 16 Uhr c.t., HS 134, AM

Serikzhan Badaev, Kazakh State University Almaty
Computable numberings in the Ershov hierarchy


3. Juli 2012, 16 Uhr c.t., HS 134, AM

Serikzhan Badaev, Kazakh State University Almaty
Computable numberings in the Ershov hierarchy (Part 2)


22./29. Mai 2012

On the strongly bounded Turing degrees of c.e. sets: Degrees inside degrees (Part 1: On the c.e. cl-degrees inside a single c.e. wtt-degree)

We consider two variants of strongly bounded Turing reductions (sbT-reductions for short): An identity bounded Turing reduction (ibT-reduction for short) is a Turing reduction where no oracle query is greater than the input while a computable Lipschitz reduction (cl-reduction for short) is a Turing reduction where the oracle queries on input x are bounded by x+c for some constant c. Since ibT-reducibility is stronger than cl-reducibility and cl-reducibility is stronger than wtt-reducibility (where a weak truth-table (wtt-) reduction is a Turing reduction where the oracle queries are computably bounded in the inputs) we may look at the partial ordering of the computably enumerable (c.e.) ibT-degrees inside a single c.e. cl-degree of $A$ and, similarly, at the partial ordering of the c.e. cl-degrees inside a single c.e. wtt-degree.

In our first talk we consider the partial orderings $(\mathbf{R}_{cl}(deg_{wtt}(A)), \leq)$ of the c.e. cl-degrees inside the wtt-degrees of single noncomputable c.e. sets $A$. For instance, we show that, for any noncomputable c.e.\ set $A$, the p.o. $(\mathbf{R}_{cl}(deg_{wtt}(A)), \leq)$ has neither maximal nor minimal elements and is closed under meets, and that in this partial ordering no finite anti-chain is maximal, and that any countable distributive lattice can be embedded. We also show, however, that, in general, the theory of $(\mathbf{R}_{cl}(deg_{wtt}(A)), \leq)$ depends on the choice of $A$. So there are c.e. sets $A$ such that $(\mathbf{R}_{cl}(deg_{wtt}(A)), \leq)$ is a dense distributive lattice but there are also c.e. sets $A$ such that $(\mathbf{R}_{cl}(deg_{wtt}(A)), \leq)$ is not dense, not closed under joins, not distributive, and neither an upper nor a lower semi-lattice.

In our second talk we discuss the corresponding questions for the partial orderings $(\mathbf{R}_{ibT}(deg_{cl}(A)), \leq)$ of the c.e. ibT-degrees inside the cl-degrees of single noncomputable c.e. sets $A$, and we explore the existence of elementary differences between $(\mathbf{R}_{ibT}(deg_{cl}(A)), \leq)$ and $(\mathbf{R}_{cl}(deg_{wtt}(A)), \leq)$.

5. Juni 2012

The Complexity of Verbal Languages over Groups

(Sanjay Jain, Alexei Miasnikov and Frank Stephan)

This paper investigates the complexity of verbal languages and pattern languages of Thurston automatic groups in terms of the Chomsky hierarchy. Here the language generated by a pattern is taken as the set of representatives of all strings obtained when chosing values for the various variables. For noncommutative free groups, it is shown that the complexity of the verbal and pattern languages (in terms of level on the Chomsky hierarchy) does not depend on the Thurston automatic representation and that verbal languages cannot be context-free (unless they are either the empty word or the full group). They can however be indexed languages. Furthermore, it is shown that in the general case, it might depend on the exactly chosen Thurston automatic representation which level a verbal language takes in the Chomsky hierarchy. There are examples of groups where, in an appropriate representation, all pattern languages are regular or context-free, respectively.

19. Juni 2012

On Sigma-definability of structures over the reals


We give a brief survey of the results on structures $\Sigma$--definable over $HF(R)$ and present some results on the number of non-$\Sigma$-isomorphic presentations of the ordered field R of reals and of its ordering. In particular, we will discuss