Séminaire interuniversitaire de logique mathématique (3ème cycle FNRS)

 Sauf mention contraire, le cours de DEA et les séminaires du jeudi après-midi ont lieu à l'ULB, Campus de la Plaine, au local 2NO906. Un itinéraire (bilingue) est disponible. Les accès pour les exposés qui ont lieu à Mons et à Louvain-la-Neuve sont respectivement UMH, Campus de la Plaine et UCL-Collège Mercier

 

Programme du séminaire interuniversitaire de logique mathématique 2009/2010
Pour recevoir le programme par email lors de ses mises à jour, laissez-nous vos coordonnées à l'adresse
http://www.umh.ac.be/math/logic/logicdb/inscription.php

 

Premier semestre

 

Date et lieu des réjouissances

Exposés du matin

Exposés de l'après-midi

Jeudi 8 Octobre
Umons, Bâtiment Vésale

15h30: Andreas Weiermann (UGent)
What makes an Ackermann-like function non primitive recursive? (abstract)

Jeudi 15 Octobre
Umons, Le Pentagone 0A07

15h30: Thomas Brihaye (Umons)
When are timed automata determinizable ?
(Joint work with Ch. Baier, N. Bertrand and P. Bouyer) (abstract)

Résumés:

Andreas Weiermann (UGent): What makes an Ackermann-like function non primitive recursive?

The Ackermann function is a prototype for a recursive function which is not primitive recursive. In our talk we consider slight variants of it and investigate whether the variants are still not primitive recursive. This leads to a fascinating research topic.
To fix the context let f and g be two numbertheoretic functions (with g(n) growing faster than the identity function). Define A_0(n):=g(n), A_{k+1}(n):=A_k^{f(n)}(n) [the upper index denotes number of iterations] and A(n):=A_n(n).
The problem is: Given g classify those f for which the resulting function A is not primitive recursive. This problem is surprisingly rich and a more or less complete solution is available when f and g are not too irregular.
As prerequisites for the talk we assume only familiarity with primitve recursive functions and the Ackermann function.
(joint work with Eran Omri and Wim van Hoof. A partial result appeared recently in APAL, doi:10.1016/j.apal.2007.02.004 )

Thomas Brihaye (Umons): When are timed automata determinizable ? (Joint work with Ch. Baier, N. Bertrand and P. Bouyer)
It is well known that timed automata are not determinizable. In this talk, we present an abstract procedure which, given a timed automaton, produces a language-equivalent deterministic infinite timed tree. We prove that under a certain boundedness condition, the infinite timed tree can be reduced into a classical deterministic timed automaton. The boundedness condition is satisfied by several subclasses of timed automata, some of them were known to be determinizable (event-clock timed automata, automata with integer resets), but some others were not. We prove for instance that strongly non-Zeno timed automata can be determinized. As a corollary of those constructions, we get for those classes the decidability of the universality and of the inclusion problems, and compute their complexities (the inclusion problem is for instance EXPSPACE-complete for strongly non-Zeno timed automata).

 



Second semestre

Date et lieu des réjouissances

Exposés du matin

 

Exposés de l'après-midi

Résumés:


 

Archive des séminaires passés

Retour à la page de garde / Back to the homepage

Page maintenue par Cédric Rivière