[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