Talk: “Cobham Recursive Set Functions” (M. Mueller, 2015-09-03)

Date: Thursday, September 03, 2015 at 12:oo h.

Where: Faculty of Informatics, 2.2 Seminar room

Organized by: UFI BAILab and LoRea

Speaker: Moritz Mueller

 

Abstract

The set of polynomial time computable functions PTIME is classically defined as operating with finite binary strings or natural numbers. What does it mean for a function on arbitrary sets to be polynomial time computable? In 1965 Cobham characterized PTIME as the closure of a set of certain initial functions under composition and a certain restricted from of recursion. On arbitrary sets we define the class of so-called Cobham Recursive Set Functions as the closure of a certain set of initial functions under composition and an analogously restricted form of epsilon-recursion. The talk offers an introduction to the corresponding theory.

Mini CV Moritz Mueller

From 1998 to 2004 Moritz Mueller studied mathematics and philosophy at the universities of Tuebingen and Freiburg (Germany). From 2004 to 2009, Moritz Mueller were employed as scientific assistant of Joerg Flum at the department of mathematics of the university of Freiburg. In 2009 he defended his doctoral dissertation under supervision of Joerg Flum titled “Parameterized Randomization” on topics in parameterized complexity theory. From 2009 to 2011 Moritz Mueller held a postdoc position under Sy-David Friedman at the Centre de Recerca Matemtica in Bellaterra (Barcelona) on topics in proof complexity. Since 2011 he is working at the Kurt Goedel Research Center headed by Sy-David Friedman in Vienna, first as a postdoc and since 2013 as (a kind of non-tenured) assistant professor. He has several publications in international journals and has given several talks in international conferences and prestigious institutions.

2 iruzkin honentzako: Talk: “Cobham Recursive Set Functions” (M. Mueller, 2015-09-03)

Erantzuna idatzi

 

 

 

HTML etiketa hauek erabil ditzakezu

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>