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

Non permanents

Thématiques de recherche

Nos objets :

  • pavages
  • automates cellulaires
  • mots (dimension 1 et 2)

Nos approches :

  • calculabilité
  • complexité
  • combinatoire
  • logique
  • algorithmique

Principales collaborations

Internationales :

Nationales :

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

  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.
  2. 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>
  3. 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>

2018

  1. Hilbert’s Error?
    Alexander Shen
    Mathematical Intelligencer, Springer Verlag, 2018, 40 (4), pp.6-11. &#x27E8;10.1007/s00283-018-9792-8&#x27E9;. &#x27E8;lirmm-01982335&#x27E9;.
  2. 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.
  3. 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.
  4. Greedy Palindromic Lengths
    Michelangelo Bucci, Gwenaël Richomme
    International Journal of Foundations of Computer Science, World Scientific Publishing, 2018, 29 (03), pp.331- 356. &#x27E8;10.1142/S0129054118500077&#x27E9;. &#x27E8;lirmm-01796733&#x27E9;.
  5. Sturmian images of non Sturmian words and standard morphisms
    Patrice Séébold
    Theoretical Computer Science, Elsevier, 2018, 711 (8), pp.92-104.
  6. 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.
  7. Avoidability of circular formulas
    Guilhem Gamard, Pascal Ochem, Gwenaël Richomme, Patrice Séébold
    Theoretical Computer Science, Elsevier, 2018, 726, pp.1-4.
  8. 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. &#x27E8;10.1016/j.jcss.2018.01.002&#x27E9;. &#x27E8;lirmm-01803441&#x27E9;.

2017

  1. Layerwise Computability and Image Randomness
    Laurent Bienvenu, Mathieu Hoyrup, Alexander Shen
    Theory of Computing Systems, Springer Verlag, 2017, 61 (4), pp.1353-1375.
  2. 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>
  3. Diagonally non-computable functions and fireworks
    Laurent Bienvenu, Ludovic Patey
    Information and Computation, Elsevier, 2017, 253 (Part 1), pp.64-77.
  4. Periodicity in rectangular arrays
    Guilhem Gamard, Gwenaël Richomme, Jeffrey Shallit, Taylor J. Smith
    Information Processing Letters, Elsevier, 2017, 118, pp.58-63.
  5. Aperiodic tilings and entropy
    Bruno Durand, Guilhem Gamard, Anaël Grandjean
    Theoretical Computer Science, Elsevier, 2017, 666, pp.36-47.
  6. Conditional probabilities and van Lambalgen theorem revisited
    Bruno Bauwens, Hayato Takahashi, Alexander Shen
    Theory of Computing Systems, Springer Verlag, 2017, 61 (4), pp.1315-1336.
  7. Layerwise computability and image randomness
    Laurent Bienvenu, Mathieu Hoyrup, Alexander Shen
    Theory of Computing Systems, Springer Verlag, 2017, 61 (4), pp.1315-1336. &#x27E8;https://link.springer.com/&#x27E9;. &#x27E8;10.1007/s00224-017-9789-2&#x27E9;. &#x27E8;lirmm-01486486&#x27E9;.

2016

  1. 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.

2015

  1. Topological Arguments for Kolmogorov Complexity
    Alexander Shen, Andrei Romashchenko
    Theory of Computing Systems, Springer Verlag, 2015, 56 (3), pp.513-526.
  2. 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.

2014

  1. Minimal critical exponent of quasiperiodic words
    Gwenaël Richomme
    Theoretical Computer Science, Elsevier, 2014, 548, pp.117-122.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.

Communications internationales

2019

  1. Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension
    Gleb Posobin, Alexander Shen
    Rolf Niedermeier; Christophe Paul. STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 36th International Symposium on Theoretical Aspects of Computer Science, 126, 2019, Leibniz International Proceedings in Informatics (LIPIcs). <10.4230/LIPIcs.STACS.2019.57>
  2. 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. <https://stacs2019.akt.tu-berlin.de/>

2018

  1. Plain stopping time and conditional complexities revisited
    Alexander Shen
    MFCS: Mathematical Foundations of Computer Science, Aug 2018, Liverpool, United Kingdom. 43rd International Symposium on Mathematical Foundations of Computer Science, 2018. <10.4230/LIPIcs.MFCS.2018.2>
  2. Algorithms and Geometric Constructions
    Vladimir Uspenskiy, Alexander Shen
    CiE: Conference on Computability in Europe, Jul 2018, Kiel, Germany. 14th Conference on Computability in Europe, LNCS (10936), pp.410-420, 2018, Sailing Routes in the World of Computation.
  3. 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, 2018, LIPIcs 107, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2018.
  4. 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. 2018. <https://www.sfoptique.org/pages/congres-optique/optique-toulouse-2018/>

2017

  1. Automatic Kolmogorov Complexity and Normality Revisited
    Alexander Shen
    FTC: Fundamentals of Computation Theory, Dec 2017, Bordeaux, France. 21st International Symposium on Fundamentals of Computation Theory, LNCS (10472), pp.418-430, 2017.
  2. 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. 83, pp.5:1-5:14, 2017, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017).
  3. Differences Between 2D Neighborhoods According to Real Time Computation
    Anaël Grandjean
    DLT: Developments in Language Theory, Aug 2017, Liège, Belgium. International Conference on Developments in Language Theory, LNCS (10396), pp.198-209, 2017, Developments in Language Theory.
  4. A Characterization of Infinite LSP Words
    Gwenaël Richomme
    DLT: Developments in Language Theory, Aug 2017, Liège, Belgium. Springer, 21st International Conference on Developments in Language Theory (DLT 2017), LNCS (10396), pp.320-331, 2017.
  5. Semiconductor laser Markov models in the micro-canonical, canonical and grand-canonical ensembles
    Arthur Vallet, Laurent Chusseau, Fabrice Phillippe, Alain Jean-Marie
    SigmaPhi 2017 - International Conference on Statistical Physics, Jul 2017, Corfu, Greece. pp.1-42, 2017.
  6. On shift-invariant maximal filters and hormonal cellular automata
    Julien Cervelle, Grégory Lafitte
    LICS: Logic in Computer Science, Jun 2017, Reykjavik, Iceland. 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, pp.1-10, 2017.
  7. Compressibility and Probabilistic Proofs
    Alexander Shen
    CIE: Computability in Europe, Jun 2017, Turku, Finland. Springer, 13th Conference on Computability in Europe, LNCS (10307), pp.101-111, 2017, Unveiling Dynamics and Complexity.
  8. Admissibles in Gaps
    Merlin Carl, Bruno Durand, Grégory Lafitte, Sabrina Ouazzani
    CiE: Computability in Europe, Jun 2017, Turku, Finland. 13th Conference on Computability in Europe, LNCS (10307), pp.175-186, 2017.
  9. Infinite Time Busy Beavers
    Oscar Defrain, Bruno Durand, Grégory Lafitte
    CiE: Conference on Computability in Europe, Jun 2017, Turku, Finland. 13th Conference on Computability in Europe, LNCS (10307), pp.221-233, 2017, Unveiling Dynamics and Complexity.
  10. 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. 34th Symposium on Theoretical Aspects of Computer Science, 66, pp.43:1-43:14, 2017, Leibniz International Proceedings in Informatics (LIPIcs).

2016

  1. Determining Sets of Quasiperiods of Infinite Words
    Guilhem Gamard, Gwenaël Richomme
    Piotr Faliszewski; Anca Muscholl; Rolf Niedermeier. MFCS: Mathematical Foundations of Computer Science, Aug 2016, Cracovie, Poland. 41st International Symposium on Mathematical Foundations of Computer Science, 58, pp.40:1-40:13, 2016, Leibniz International Proceedings in Informatics (LIPIcs).
  2. 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. 43rd International Colloquium on Automata, Languages, and Programming, 55, pp.115:1--115:12, 2016, Leibniz International Proceedings in Informatics (LIPIcs).
  3. Constant Acceleration Theorem for Extended von Neumann Neighbourhoods
    Anaël Grandjean
    Matthew Cook; Turlough Neary. AUTOMATA, Jun 2016, Zurich, Switzerland. Springer, 22th International Workshop on Cellular Automata and Discrete Complex Systems, LNCS (9664), pp.149-158, 2016, Cellular Automata and Discrete Complex Systems.

2015

  1. 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, &#x27E8;10.1007/978-3-662-48054-0_20&#x27E9;. &#x27E8;lirmm-01233012&#x27E9;.
  2. Quasiperiodicity and non-computability in tilings
    Bruno Durand, Andrei Romashchenko
    MFCS: Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. MFCS'2015: 40th International Symposium on Mathematical Foundations of Computer Science, 2015. <10.1007/978-3-662-48057-1_17>
  3. What Percentage of Programs Halt?
    Laurent Bienvenu, Damien Desfontaines, Alexander Shen
    ICALP: International Colloquium on Automata, Languages and Programming, Jul 2015, Kyoto, Japan. Springer, 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, LNCS (9134), pp.219-230, 2015, Automata, Languages, and Programming.
  4. L-Convex Polyominoes Are Recognizable in Real Time by 2D Cellular Automata
    Anaël Grandjean, Victor Poupet
    Jarkko Kari. AUTOMATA, Jun 2015, Turku, Finland. 21st Workshop on Cellular Automata and Discrete Complex Systems, LNCS (9099), pp.127-140, 2015, Cellular Automata and Discrete Complex Systems.
  5. 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. 32nd International Symposium on Theoretical Aspects of Computer Science, 30, pp.367-378, 2015.
  6. Coverability in Two Dimensions
    Guilhem Gamard, Gwenaël Richomme
    Adrian Horia Dediu; Enrico Formenti; Carlos Martín-Vide; Bianca Truthe. LATA: Language and Automata Theory and Applications, Mar 2015, Nice, France. Springer, 9th International Conference on Language and Automata Theory and Applications, 8977, 2015, LNCS. <http://grammars.grlmc.com/lata2015/>

2014

  1. Algorithmic Identification of Probabilities Is Hard
    Laurent Bienvenu, Benoit Monin, Alexander Shen
    ALT: Algorithmic Learning Theory, Oct 2014, Bled, Slovenia. LNCS (8776), pp.85-95, 2014, Algorithmic Learning Theory.
  2. Aperiodic Tilings and Entropy
    Bruno Durand, Guilhem Gamard, Anaël Grandjean
    DLT: Developments in Language Theory, Aug 2014, Ekaterinburg, Russia. 18th International Conference on Developments in Language Theory, LNCS (8633), pp.166-177, 2014.
  3. 5-State Rotation-Symmetric Number-Conserving Cellular Automata are not Strongly Universal
    Katsunobu Imai, Hisamichi Ishizaka, Victor Poupet
    AUTOMATA, Jul 2014, Himeji, Japan. 20th International Workshop on Cellular Automata and Discrete Complex Systems, LNCS (8996), pp.31-43, 2015.
  4. 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. SPIE, SPIE Physics and Simulation of Optoelectronic Devices XXII (Photonics West OPTO 2014), 2014. <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