Home

09-10
2019

Home

Le projet consiste en trois tâches :

Modélisation des algorithmes. The theory of Abstract State Machines can be extended. Subjects related to universality, relation with the Moschovakis model of algorithms and representation of other models of computation, are of a great interest to extend the theory of ASM.
Complétude des modèles de calcul. Is the ASM model the only operationally complete model? Other computational models (sequential and parallel) and programming languages can also allow a stepwise emulation of any algorithm. Assuming Gurevich sequential and parallel thesis, this reduces to deciding whether such computational models or programming language allow stepwise emulation of any ASM. This will provide a theoretical foundation for algorithmically-complete programming languages or models of computation.
Aspects physiques des algorithmes classiques et quantiques. To what extent can the sequential thesis be backed on physical arguments? On the one hand, arguments ˆ la Gandy show that a small set of well-established postulates on physical ground is enough to justify the Church-Turing thesis. Hence it seems that a refined version of the argument may serve to justify the thesis of Gurevich. On the other hand, quantum computing introduces algorithms that are radically new.

Le projet s’étalera sur la période 2012–2016.

Le projet sur le site de l’ANR.

Événements

Séminaire TARMAC

Séminaire régulier, LACL.

À venir, séminaire délocalisé: Juin, Octobre, Décembre 2015.

Rencontre TARMAC - Spatial Computing

Mercredi 15 Avril – 10h30–18h30, LIAFA Salle Marcel-Paul Schützenberger.
Participants prévus : Jean-Louis Giavitto, Frédéric Gruau, Luidnel Maignan, Antoine Spicher, Jean-Baptiste Yunès

Journées TARMAC

Vendredi 23 Janvier 2015 – 9h30–17h00, INRIA, Place d’Italie.
Participants : Patrick Cégielski, Julien Cervelle, Gilles Dowek, Serge Grigorieff, Irène Guessarian, Luidnel Maignan, Yoann Marquer, Pascal Vanier, Pierre Valarcher, Jean-Baptiste Yunès

Membres

Les membres du projet sont:

Pablo Arrighi (LIF)
Alexis Bès (LACL)
Patrick Cégielski (LACL)
Julien Cervelle (LACL)
Gilles Dowek (INRIA)
Serge Grigorieff (IRIF)
Irène Guessarian (IRIF)
Luidnel Maignan (LACL)
Yoann Marquer (LACL)
Pierre Valarcher (LACL)
Pascal Vanier (LACL)
Jean-Baptiste Yunès (IRIF)

Publications

En cours...

Soumis à Journal of Cellular Automata. 2015.

Luidnel Maignan, Jean-Baptiste Yunès. "Finitization of Infinite Field-based Multi-general FSSP Solution."

Soumis à Fundamenta Informaticæ. 2014.

Yoan Marquer. "Algorithmic completeness of imperative programming languages."

2015

À paraître dans International Journal of Number Theory.

Patrick Cegielski, Serge Grigorieff, Irène Guessarian. "Newton representation of functions over natural integers having integral difference ratios."

À venir. Communication à DICE, Developments in Implicit Computational Complexity London, UK, April 11--12, 2015.

Yoan Marquer, Pierre Valarcher. "An algorithmic complete programming language for a large class of algorithms computable in polynomial time."

2014

ACRI 2014 Cellular Automata for Research and Industry, September 22-25, 2014, Kraków, Poland. LNCS 8751.

Luidnel Maignan, Jean-Baptiste Yunès. "Experimental Finitization of Infinite Field-based Generalized FSSP Solution."

AUTOMATA 2014 20th International Workshop on Cellular Automata and Discrete Complex Systems, Himeji, Japan, July 7th-9th, 2014.

Luidnel Maignan, Jean-Baptiste Yunès. "Generalized FSSP on Hexagonal Tiling: Towards Arbitrary Regular Spaces."

In Computing with New Resources, LNCS 8808

Patrick Cegielski, Serge Grigorieff, Irène Guessarian. "Integral Difference Ratio Functions on Integers."

Automata, Languages, and Programming 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, Lecture Notes in Computer Science Volume 8573

Alex Borello, Julien Cervelle, Pascal Vanier. "Turing Degrees of Limit Sets of Cellular Automata."

2013

AFCA'13 International Workshop on Applications and Fundamentals of Cellular Automata, in Honor of Pr. Morita's retirement. In conjunction with CANDAR'13, Matsuyama, Japan, December 4—6, 2013.

Luidnel Maignan, Jean-Baptiste Yunès. "Moore and Von Neumann Neighborhood n-Dimensional Generalized Firing Squad Solutions Using Fields."