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
15. Mai 2012, Lutz Büch, Universität Heidelberg 


22. Mai 2012, 16 Uhr c.t., HS 134, AM Klaus AmbosSpies, Universität Heidelberg 

29. Mai 2012, 16 Uhr c.t., HS 134, AM Klaus AmbosSpies, Universität Heidelberg 

5. Juni 2012, 16 Uhr c.t., HS 134, AM Frank Stephan, National University of Singapore 

19. Juni 2012, 16 Uhr c.t., HS 134, AM Andrey Morozov, Sobolev Institute of Mathematics, Novosibirsk 

26. Juni 2012, 16 Uhr c.t., HS 134, AM Serikzhan Badaev, Kazakh State University Almaty 

3. Juli 2012, 16 Uhr c.t., HS 134, AM Serikzhan Badaev, Kazakh State University Almaty 


22./29. Mai 2012 
On the strongly bounded Turing degrees of c.e. sets: Degrees inside degrees (Part 1: On the c.e. cldegrees inside a single c.e. wttdegree) We consider two variants of strongly bounded Turing reductions (sbTreductions for short): An identity bounded Turing reduction (ibTreduction for short) is a Turing reduction where no oracle query is greater than the input while a computable Lipschitz reduction (clreduction for short) is a Turing reduction where the oracle queries on input x are bounded by x+c for some constant c. Since ibTreducibility is stronger than clreducibility and clreducibility is stronger than wttreducibility (where a weak truthtable (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.) ibTdegrees inside a single c.e. cldegree of $A$ and, similarly, at the partial ordering of the c.e. cldegrees inside a single c.e. wttdegree. In our first talk we consider the partial orderings $(\mathbf{R}_{cl}(deg_{wtt}(A)), \leq)$ of the c.e. cldegrees inside the wttdegrees 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 antichain 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 semilattice. In our second talk we discuss the corresponding questions for the partial orderings $(\mathbf{R}_{ibT}(deg_{cl}(A)), \leq)$ of the c.e. ibTdegrees inside the cldegrees 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) 
19. Juni 2012 
On Sigmadefinability 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 