Page d'accueil > Recherche > Equipes > ESCAPE

ESCAPE: Systèmes complexes, automates et pavages

Web site of the group in English: http://www.lirmm.fr/escape/

L’équipe travaille dans le domaine de l’informatique théorique et est composée de spécialistes de domaines différents mais connexes : calculabilité, complexité, logique. Ses membres se retrouvent dans les objets qu’ils étudient, et typiquement, ces objets sont les pavages, les automates cellulaires, les machines de Turing. Ils se retrouvent aussi dans les paradigmes qu’ils adoptent : la spécialité de l’équipe est de travailler sur ces objets d’un point de vue « modèle de calcul », mais nous nous intéressons aussi largement à la « théorie des jeux algorithmiques ». Nous cherchons à comprendre aussi bien l’émergence de la notion de calcul que la puissance ou à la robustesse des modèles considérés. Nos travaux ont un impact hors de notre champ scientifique propre : en mathématiques dans le domaine des systèmes dynamiques discrets, en logique, et ils commencent à avoir un impact en physique statistique.

Membres

Permanents

Bruno Durand, Professeur des Universités UM
Gregory Lafitte, Maître de Conférences UM
Fabrice Philippe, Maître de Conférences UPV
Victor Poupet, Maître de Conférences UM
Gwenaël Richomme, Professeur des Universités UPV
Andrei Romashchenko, Chargé de Recherche CNRS
Alexander Shen, Directeur de Recherche CNRS
Patrice Séébold, Professeur des Universités UPV

Non permanents

Julien Destombes, Doctorant UM
Ruslan Ishkuvatov, CDD Ingénieur-Technicien CNRS

Thématiques de recherche

Nos objets :

pavages
automates cellulaires
mots (dimension 1 et 2)

Nos approches :

calculabilité
complexité
combinatoire
logique
algorithmique

Principales collaborations

Internationales :

Leonid Levin et Peter Gacs – Boston University, USA
Theodore Slaman – Univ. of California, Berkeley, USA
Jarkko Kari – University of Turku, Finlande
Nikolai Vereshchagin – Moscow University, Russia
Menachem Magidor – Hebrew U. Jérusalem, Israël
Katsunobu Imai – Hiroshima University, Japan

Nationales :

Emmanuel Jeandel – Loria, Nancy
Nicolas Ollinger – LIFO, Orléans
Enrico Formenti – I3S, Nice
Laurent Bienvenu – LIAFA, Paris
Gaëtan Richard – Greyc, Caen

Publications

Voir les publications de l'équipe ESCAPE au LIRMM

Groupe de travail

Notre groupe de travail est composé d'exposés d'orateurs invités et d'orateurs locaux (environ pour moitié). Il est commun avec l'équipe ECO et est organisé par Laurent Imbert et Gwenaël Richomme.

Publications depuis 2014 - Evaluation 2019

Articles de revues internationales

2019

Characterization of infinite LSP words and endomorphisms preserving the LSP property
Gwenaël Richomme

International Journal of Foundations of Computer Science, World Scientific Publishing, 2019, 30 (1), pp.171-196. ⟨10.1142/S0129054119400082⟩. ⟨lirmm-01855460⟩.
On the Structure of Ammann A2 Tilings
Bruno Durand, Alexander Shen, Nikolay Vereshchagin

Discrete and Computational Geometry, Springer Verlag, In press, ⟨10.1007/s00454-019-00074-1⟩. ⟨lirmm-02095674⟩. <10.1007/s00454-019-00074-1>
Markov model of quantum fluctuations at the transition to lasing of semiconductor nanolasers
Arthur Vallet, Laurent Chusseau, Fabrice Philippe, Alain Jean-Marie

Physica E: Low-dimensional Systems and Nanostructures, Elsevier, 2019, 105, pp.97-104. ⟨10.1016/j.physe.2018.08.028⟩. ⟨hal-01888162⟩.

2018

Hilbert’s Error?
Alexander Shen

Mathematical Intelligencer, Springer Verlag, 2018, 40 (4), pp.6-11. ⟨10.1007/s00283-018-9792-8⟩. ⟨lirmm-01982335⟩.
On the Combinatorial Version of the Slepian-Wolf Problem
Daniyar Chumbalov, Andrei Romashchenko

IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (9), pp. 6054 - 6069. ⟨10.1109/TIT.2018.2854589⟩. ⟨lirmm-01233020⟩.
A Conditional Information Inequality and Its Combinatorial Applications
Andrei Romashchenko, Tarik Kaced, Nikolai Vereshchagin

IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (5), pp.3610-3615. ⟨10.1109/TIT.2018.2806486⟩. ⟨lirmm-01793775⟩.
Greedy Palindromic Lengths
Michelangelo Bucci, Gwenaël Richomme

International Journal of Foundations of Computer Science, World Scientific Publishing, 2018, 29 (03), pp.331- 356. ⟨10.1142/S0129054118500077⟩. ⟨lirmm-01796733⟩.
Sturmian images of non Sturmian words and standard morphisms
Patrice Séébold

Theoretical Computer Science, Elsevier, 2018, 711 (8), pp.92-104. ⟨10.1016/j.tcs.2017.11.011⟩. ⟨hal-01645123⟩.
Avoidability of circular formulas
Guilhem Gamard, Pascal Ochem, Gwenaël Richomme, Patrice Séébold

Theoretical Computer Science, Elsevier, 2018, 726, pp.1-4. ⟨10.1016/j.tcs.2017.11.014⟩. ⟨lirmm-01692716⟩.
Dimension 1 sequences are close to randoms
Alexander Shen, Noam Greenberg, Joseph Miller, Linda Brown Westrick

Theoretical Computer Science, Elsevier, 2018, 705, pp.99-112. ⟨10.1016/j.tcs.2017.09.031⟩. ⟨lirmm-01803444⟩.
Algorithmic identification of probabilities is hard
Laurent Bienvenu, Santiago Figueira, Benoit Monin, Alexander Shen

Journal of Computer and System Sciences, Elsevier, 2018, 95, pp.98-108. ⟨10.1016/j.jcss.2018.01.002⟩. ⟨lirmm-01803441⟩.

2017

Layerwise Computability and Image Randomness
Laurent Bienvenu, Mathieu Hoyrup, Alexander Shen

Theory of Computing Systems, Springer Verlag, 2017, 61 (4), pp.1353-1375. ⟨10.1007/s00224-017-9791-8⟩. ⟨hal-01650910⟩.
Coverability and multi-scale coverability on infinite pictures
Guilhem Gamard, Gwenaël Richomme

Journal of Computer and System Sciences, Elsevier, In press, ⟨10.1016/j.jcss.2017.05.001⟩. ⟨lirmm-02018577⟩. <10.1016/j.jcss.2017.05.001>
Diagonally non-computable functions and fireworks
Laurent Bienvenu, Ludovic Patey

Information and Computation, Elsevier, 2017, 253 (Part 1), pp.64-77. ⟨10.1016/j.ic.2016.12.008⟩. ⟨lirmm-01693182⟩.
Periodicity in rectangular arrays
Guilhem Gamard, Gwenaël Richomme, Jeffrey Shallit, Taylor J. Smith

Information Processing Letters, Elsevier, 2017, 118, pp.58-63. ⟨10.1016/j.ipl.2016.09.011⟩. ⟨lirmm-01378894⟩.
Aperiodic tilings and entropy
Bruno Durand, Guilhem Gamard, Anaël Grandjean

Theoretical Computer Science, Elsevier, 2017, 666, pp.36-47. ⟨10.1016/j.tcs.2016.12.013⟩. ⟨lirmm-01480619⟩.
Conditional Probabilities and van Lambalgen’s Theorem Revisited
Bruno Bauwens, Alexander Shen, Hayato Takahashi

Theory of Computing Systems, Springer Verlag, 2017, 61 (4), pp.1315-1336. ⟨10.1007/s00224-017-9789-2⟩. ⟨lirmm-01486477⟩.

2016

Generic algorithms for halting problem and optimal machines revisited
Laurent Bienvenu, Damien Desfontaines, Alexander Shen

Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2016, Logical Methods in Computer Science, 12 (2), pp.1-29. ⟨http://www.lmcs-online.org/⟩. ⟨10.2168/LMCS-12(2:1)2016⟩. ⟨lirmm-01486494⟩.

2015

Topological Arguments for Kolmogorov Complexity
Andrei Romashchenko, Alexander Shen

Theory of Computing Systems, Springer Verlag, 2015, 56 (3), pp.513-526. ⟨10.1007/s00224-015-9606-8⟩. ⟨hal-01165095⟩.
mu-Limit Sets of Cellular Automata from a Computational Complexity Perspective
Laurent Boyer, Martin Delacourt, Victor Poupet, Mathieu Sablik, Guillaume Theyssier

Journal of Computer and System Sciences, Elsevier, 2015, 81 (8), pp.1623-1647. ⟨hal-00866094v2⟩.

2014

Minimal critical exponent of quasiperiodic words
Gwenaël Richomme

Theoretical Computer Science, Elsevier, 2014, 548, pp.117-122. ⟨10.1016/j.tcs.2014.06.039⟩. ⟨lirmm-01059541⟩.
On the maximal weight of (p,q)-ary chain partitions with bounded parts
Filippo Disanto, Laurent Imbert, Fabrice Philippe

Integers : Electronic Journal of Combinatorial Number Theory, State University of West Georgia, Charles University, and DIMATIA, 2014, 14, pp.A37. ⟨http://www.integers-ejcnt.org/vol14.html⟩. ⟨lirmm-01104898⟩.
Pseudo-Random Graphs and Bit Probe Schemes with One-Sided Error
Andrei Romashchenko

Theory of Computing Systems, Springer Verlag, 2014, 55 (2), pp.313-329. ⟨10.1007/s00224-012-9425-0⟩. ⟨hal-01165099⟩.
Monte Carlo modeling of the dual-mode regime in quantum-well and quantum-dot semiconductor lasers
Laurent Chusseau, Fabrice Philippe, Filippo Disanto

Optics Express, Optical Society of America, 2014, 22 (5), pp.5312-5324. ⟨10.1364/OE.22.005312⟩. ⟨lirmm-01067715⟩.
Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity
Bruno Bauwens, Alexander Shen

The Journal of Symbolic Logic, Association for Symbolic Logic, 2014, 79 (02), pp.620-632. ⟨10.1017/jsl.2014.15⟩. ⟨lirmm-00853082⟩.
The axiomatic power of Kolmogorov complexity
Laurent Bienvenu, Andrei Romashchenko, Alexander Shen, Antoine Taveneaux, Stijn Vermeeren

Annals of Pure and Applied Logic, Elsevier Masson, 2014, 165 (9), pp.1380-1402. ⟨10.1016/j.apal.2014.04.009⟩. ⟨hal-01165098⟩.
Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma
Andrei Rumyantsev, Alexander Shen

Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2014, 132 (1), pp.1-14. ⟨10.3233/FI-2014-1029⟩. ⟨lirmm-01233795⟩.

Communications internationales

2019

How to Use Undiscovered Information Inequalities: Direct Applications of the Copy Lemma
Emirhan Gürpınar, Andrei Romashchenko

ISIT: International Symposium on Information Theory, Jul 2019, Paris, France. ⟨lirmm-01990325⟩. <https://2019.ieee-isit.org/Papers/ViewPaper.asp?PaperNum=1847>
Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension
Gleb Posobin, Alexander Shen

STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. ⟨10.4230/LIPIcs.STACS.2019.57⟩. ⟨lirmm-02084843⟩. <10.4230/LIPIcs.STACS.2019.57>
Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
Andrei Romashchenko, Julien Destombes

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), Mar 2019, Berlin, Germany. ⟨lirmm-01793810⟩. <https://stacs2019.akt.tu-berlin.de/>

2018

Plain stopping time and conditional complexities revisited
Mikhail Andreev, Gleb Posobin, Alexander Shen

MFCS: Mathematical Foundations of Computer Science, Aug 2018, Liverpool, United Kingdom. pp.2:1--2:12, ⟨10.4230/LIPIcs.MFCS.2018.2⟩. ⟨lirmm-01982373⟩.
Algorithms and Geometric Constructions
Vladimir Uspenskiy, Alexander Shen

CiE: Conference on Computability in Europe, Jul 2018, Kiel, Germany. pp.410-420, ⟨10.1007/978-3-319-94418-0_41⟩. ⟨lirmm-01982315⟩.
An operational characterization of mutual information in algorithmic information theory
Andrei Romashchenko, Marius Zimand

45th International Colloquium on Automata, Languages, and Programming (ICALP), Jul 2018, Prague, Czech Republic. pp.95:1-95:14, ⟨10.05984⟩. ⟨lirmm-01618559⟩.
Illustration du passage au seuil des nanolasers par une modélisation markovienne
Arthur Vallet, Laurent Chusseau, Alain Jean-Marie, Fabrice Philippe

OPTIQUE Toulouse, Jul 2018, Toulouse, France. ⟨hal-01891428⟩. <https://www.sfoptique.org/pages/congres-optique/optique-toulouse-2018/>

2017

Automatic Kolmogorov Complexity and Normality Revisited
Alexander Shen

FTC: Fundamentals of Computation Theory, Dec 2017, Bordeaux, France. pp.418-430, ⟨10.1007/978-3-662-55751-8_33⟩. ⟨lirmm-01803449⟩.
On the expressive power of quasiperiodic SFT
Andrei Romashchenko, Bruno Durand

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), Aug 2017, Aalborg, Denmark. pp.5:1-5:14, ⟨10.4230/LIPIcs.MFCS.2017.5⟩. ⟨lirmm-01623207⟩.
A Characterization of Infinite LSP Words
Gwenaël Richomme

DLT: Developments in Language Theory, Aug 2017, Liège, Belgium. pp.320-331, ⟨10.1007/978-3-319-62809-7_24⟩. ⟨lirmm-01587263⟩.
Differences Between 2D Neighborhoods According to Real Time Computation
Anaël Grandjean

DLT: Developments in Language Theory, Aug 2017, Liège, Belgium. pp.198-209, ⟨10.1007/978-3-319-62809-7_14⟩. ⟨lirmm-01693188⟩.
Semiconductor laser Markov models in the micro-canonical, canonical and grand-canonical ensembles
Arthur Vallet, Laurent Chusseau, Fabrice Philippe, Alain Jean-Marie

SigmaPhi 2017 - International Conference on Statistical Physics, Jul 2017, Corfu, Greece. pp.1-42. ⟨hal-01649568⟩.
On shift-invariant maximal filters and hormonal cellular automata
Julien Cervelle, Grégory Lafitte

LICS: Logic in Computer Science, Jun 2017, Reykjavik, Iceland. pp.1-10, ⟨10.1109/LICS.2017.8005145⟩. ⟨hal-01615278⟩.
Infinite Time Busy Beavers
Oscar Defrain, Bruno Durand, Grégory Lafitte

CiE: Conference on Computability in Europe, Jun 2017, Turku, Finland. pp.221-233, ⟨10.1007/978-3-319-58741-7_22⟩. ⟨lirmm-02096207⟩.
Compressibility and Probabilistic Proofs
Alexander Shen

CIE: Computability in Europe, Jun 2017, Turku, Finland. pp.101-111, ⟨10.1007/978-3-319-58741-7_11⟩. ⟨lirmm-01803530⟩.
Admissibles in Gaps
Merlin Carl, Bruno Durand, Grégory Lafitte, Sabrina Ouazzani

CiE: Computability in Europe, Jun 2017, Turku, Finland. pp.175-186, ⟨10.1007/978-3-319-58741-7_18⟩. ⟨lirmm-02020594⟩.
On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables
Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov

STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2017, Hannover, Germany. pp.43:1-43:14, ⟨10.4230/LIPIcs.STACS.2017.43⟩. ⟨lirmm-01487646⟩.

2016

Determining Sets of Quasiperiods of Infinite Words
Guilhem Gamard, Gwenaël Richomme

MFCS: Mathematical Foundations of Computer Science, Aug 2016, Cracovie, Poland. pp.40:1-40:13, ⟨10.4230/LIPIcs.MFCS.2016.40⟩. ⟨lirmm-01369373⟩.
A Linear Acceleration Theorem for 2D Cellular Automata on all Complete Neighborhoods
Anaël Grandjean, Victor Poupet

ICALP: International Colloquium on Automata, Languages and Programming, Jul 2016, Roma, Italy. pp.115:1--115:12, ⟨10.4230/LIPIcs.ICALP.2016.115⟩. ⟨lirmm-01476809⟩.
Constant Acceleration Theorem for Extended von Neumann Neighbourhoods
Anaël Grandjean

AUTOMATA, Jun 2016, Zurich, Switzerland. pp.149-158, ⟨10.1007/978-3-319-39300-1_12⟩. ⟨lirmm-01476307⟩.

2015

Quasiperiodicity and non-computability in tilings
Bruno Durand, Andrei Romashchenko

MFCS: Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. ⟨10.1007/978-3-662-48057-1_17⟩. ⟨lirmm-01165314⟩. <10.1007/978-3-662-48057-1_17>
Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem
Daniyar Chumbalov, Andrei Romashchenko

MFCS: Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. pp.235-247, ⟨10.1007/978-3-662-48054-0_20⟩. ⟨lirmm-01233012⟩.
What Percentage of Programs Halt?
Laurent Bienvenu, Damien Desfontaines, Alexander Shen

ICALP: International Colloquium on Automata, Languages and Programming, EATCS, Jul 2015, Kyoto, Japan. pp.219-230, ⟨10.1007/978-3-662-47672-7⟩. ⟨lirmm-01279151⟩.
L-Convex Polyominoes Are Recognizable in Real Time by 2D Cellular Automata
Anaël Grandjean, Victor Poupet

AUTOMATA, Jun 2015, Turku, Finland. pp.127-140, ⟨10.1007/978-3-662-47221-7_10⟩. ⟨hal-01442468⟩.
Comparing 1D and 2D Real Time on Cellular Automata
Anaël Grandjean, Victor Poupet

STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2015, München, Germany. pp.367-378, ⟨10.4230/LIPIcs.STACS.2015.367⟩. ⟨lirmm-01476808⟩.
Coverability in Two Dimensions
Guilhem Gamard, Gwenaël Richomme

LATA: Language and Automata Theory and Applications, Mar 2015, Nice, France. ⟨lirmm-01180026⟩. <http://grammars.grlmc.com/lata2015/>

2014

Algorithmic Identification of Probabilities Is Hard
Laurent Bienvenu, Benoit Monin, Alexander Shen

ALT: Algorithmic Learning Theory, Oct 2014, Bled, Slovenia. pp.85-95, ⟨10.1007/978-3-319-11662-4_7⟩. ⟨hal-01397246⟩.
Aperiodic Tilings and Entropy
Bruno Durand, Guilhem Gamard, Anaël Grandjean

DLT: Developments in Language Theory, Aug 2014, Ekaterinburg, Russia. pp.166-177, ⟨10.1007/978-3-319-09698-8_15⟩. ⟨lirmm-01480693⟩.
5-State Rotation-Symmetric Number-Conserving Cellular Automata are not Strongly Universal
Katsunobu Imai, Hisamichi Ishizaka, Victor Poupet

AUTOMATA, Jul 2014, Himeji, Japan. pp.31-43, ⟨10.1007/978-3-319-18812-6_3⟩. ⟨lirmm-01476796⟩.
Monte Carlo markovian modeling of modal competition in dual-wavelength semiconductor lasers
Laurent Chusseau, Fabrice Philippe, Alain Jean-Marie

Photonics West OPTO: Physics and Simulation of Optoelectronic Devices, Feb 2014, San Francisco, United States. ⟨10.1117/12.2036268⟩. ⟨hal-01095054⟩. <10.1117/12.2036268>

Mots-clés

Calculabilité, Logique, Machines de Turing, Modèles de calcul, Complexité, Pavages, Automates cellulaires, Ordinaux

Dernière mise à jour le 07/01/2019

Département : Informatique

Responsable : Victor POUPET

Site de l'équipe : http://www.lirmm.fr/escape/