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
Anglo-Belgian Workshop on Model Theory and Applications (Mons 2-3/12/2009)
Date et lieu des réjouissances |
Exposés du matin |
Exposés de l'après-midi |
Jeudi 8 Octobre |
15h30: Andreas Weiermann (UGent) |
|
Jeudi 15 Octobre |
15h30: Thomas Brihaye (Umons) |
|
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