[FM-India] Post doc proposal, Paris in logic and algebra

Madhavan Mukund madhavan at cmi.ac.in
Sat Dec 1 20:30:49 IST 2012


Objet: [gdr-im] Post doc proposal, Paris in logic and algebra
Date: 2012-12-01 02:50
De: Thomas Colcombet <thomas.colcombet at liafa.univ-paris-diderot.fr>

POST-DOCTORAL POSITION: ERC GRANT GALE (GAMES, AUTOMATA AND LOGIC'S 
EXTENSIONS)

SUBJECT: ALGEBRAIC MODELING OF TEMPORAL LOGICS

 The decidability of the monadic second-order theory of order is now 
quite well understood [Rabin69,Shelah75]. However, though these methods 
provide decidability, they do not give a deep insight on the exact 
expressive power of the logic. Following the seminal work on 
Schutzenberger [Sch75], an algebraic description of the expressiviy has 
been pursued, that yield a complete understanding of the expressive 
power of monadic second-order logic over infinite linear orderings of 
countable domain [CCP11].

 The goal of this Post-Doc is to extend this notion to infinite linear 
orderings (in a careful way since the theory of the real line is 
undecidable), and use this new formalism for characterising the 
expressive power of several sub-logics.

[Sch65] Marcel-Paul Schutzenberger. On finite monoids having only 
trivial subgroups. Information and Control, 8:190-194, 1965.

 [Rab69] Michael O. Rabin. Decidability of second-order theories and 
automata on infinite trees. Trans. Amer. Math. soc., 141:1-35, 1969.

 [She75] Shaharon Shelah. The monadic theory of order. Annals of Math., 
102:379-419, 1975.

 [CCP11] Olivier Carton, Thomas Colcombet, and Gabriele Puppis. Regular 
languages of words over countable linear orderings. In ICALP (2), volume 
6756 of Lecture Notes in Computer Science, pages 125-136. Springer, 
2011.

BACKGROUND

 The candidate should have a strong background in theoretical computer 
science. In particular he/she should have a knowledge in one or more 
subjects among

 	* formal language theory,
 	* algebra,
 	* logic,

FUNDING

 The post-doctoral position will be paid around 2000 euros, free of 
charges, per month.

LOCATION

Liafa (http://www.liafa.jussieu.fr/), Paris.

DATES OF THE POSITION

 The start of the position is to be decided with the applicant, and the 
duration is a priori of one year, also subject to discussion.

APPLICATION PROCEDURE

The applicants should send in electronic form:

 	* a Curriculum Vitae
 	* title and summary of the PHD
 	* list of publications
 	* official reports on PHD (preferably in French or English or German)
 	* list of persons to contact

 Any particular situation (PHD not yet defended, starting date too 
early , etc ...) should be clearly explained by a joint letter. The 
applications should be sent, by email, to T. Colcombet 
(thomas.colcombet at liafa.univ-paris-diderot.fr).

 	* application before the 15th of January 2011.
 	* decision before the 1st of February 2011



More information about the FMIndia mailing list