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
- Emirhan Gürpinar, 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
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
- An Operational Characterization of Mutual Information in Algorithmic Information TheoryAndrei Romashchenko, Marius ZimandJournal of the ACM (JACM), Association for Computing Machinery, 2019, 66 (5), pp.1-42.
- Coverability and multi-scale coverability on infinite picturesGuilhem Gamard, Gwenaël RichommeJournal of Computer and System Sciences, Elsevier, 2019, 104, pp.258-277.
- On the Structure of Ammann A2 TilingsBruno Durand, Alexander Shen, Nikolay VereshchaginDiscrete and Computational Geometry, Springer Verlag, In press. <10.1007/s00454-019-00074-1>
- Markov model of quantum fluctuations at the transition to lasing of semiconductor nanolasersArthur Vallet, Laurent Chusseau, Fabrice Philippe, Alain Jean-MariePhysica E: Low-dimensional Systems and Nanostructures, Elsevier, 2019, 105, pp.97-104.
- Владимир Андреевич Успенский (27.11.1930-27.06.2018)Alexander Shen, Сергей Иванович Адян, Sergei Ivanovich Adian, Николай Николаевич Андреев, Nikolai Nikolaevich Andreev, Лев Дмитриевич Беклемишев, Lev Dmitrievich Beklemishev, Сергей Савостьянович Гончаров, Sergey Savostyanovich Goncharov, Юрий Леонидович Ершов, Yurii Leonidovich Ershov, Юрий Владимирович Матиясевич, Yuri Vladimirovich Matiyasevich, Юрий Сергеевич Осипов, Yurii Sergeevich Osipov, Мати Рейнович Пентус, Mati Reinovich Pentus, Владимир Александрович Плунгян, Vladimir Alexandrovich Plungyan, Екатерина Владимировна Рахилина, Ekaterina Vladimirovna Rahilina, Виктор Антонович Садовничий, Victor Antonovich Sadovnichii, Алексей Львович Семeнов, Aleksei l'Vovich Semenov, Сергей Георгиевич Татевосов, Sergey Georgievich Tatevosov, Владимир Михайлович Тихомиров, Vladimir Mikhailovich Tikhomirov, Александр Ханиевич Шень, Alexander Khanievich Shen'Russian Mathematical Surveys, Turpion, 2019, 74 (4(448)), pp.165-180.
- Characterization of infinite LSP words and endomorphisms preserving the LSP propertyGwenaël RichommeInternational Journal of Foundations of Computer Science, World Scientific Publishing, 2019, 30 (1), pp.171-196.
2018
- Hilbert’s Error?Alexander ShenMathematical Intelligencer, Springer Verlag, 2018, 40 (4), pp.6-11.
- On the Combinatorial Version of the Slepian-Wolf ProblemDaniyar Chumbalov, Andrei RomashchenkoIEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (9), pp. 6054 - 6069.
- A Conditional Information Inequality and Its Combinatorial ApplicationsAndrei Romashchenko, Tarik Kaced, Nikolai VereshchaginIEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (5), pp.3610-3615.
- Greedy Palindromic LengthsMichelangelo Bucci, Gwenaël RichommeInternational Journal of Foundations of Computer Science, World Scientific Publishing, 2018, 29 (03), pp.331- 356.
- Sturmian images of non Sturmian words and standard morphismsPatrice SééboldTheoretical Computer Science, Elsevier, 2018, 711 (8), pp.92-104.
- Dimension 1 sequences are close to randomsAlexander Shen, Noam Greenberg, Joseph Miller, Linda Brown WestrickTheoretical Computer Science, Elsevier, 2018, 705, pp.99-112.
- Avoidability of circular formulasGuilhem Gamard, Pascal Ochem, Gwenaël Richomme, Patrice SééboldTheoretical Computer Science, Elsevier, 2018, 726, pp.1-4.
- Algorithmic identification of probabilities is hardLaurent Bienvenu, Santiago Figueira, Benoit Monin, Alexander ShenJournal of Computer and System Sciences, Elsevier, 2018, 95, pp.98-108.
2017
- Layerwise Computability and Image RandomnessLaurent Bienvenu, Mathieu Hoyrup, Alexander ShenTheory of Computing Systems, Springer Verlag, 2017, 61 (4), pp.1353-1375.
- Diagonally non-computable functions and fireworksLaurent Bienvenu, Ludovic PateyInformation and Computation, Elsevier, 2017, 253 (Part 1), pp.64-77.
- Periodicity in rectangular arraysGuilhem Gamard, Gwenaël Richomme, Jeffrey Shallit, Taylor J. SmithInformation Processing Letters, Elsevier, 2017, 118, pp.58-63.
- Aperiodic tilings and entropyBruno Durand, Guilhem Gamard, Anaël GrandjeanTheoretical Computer Science, Elsevier, 2017, 666, pp.36-47.
- Conditional Probabilities and van Lambalgen’s Theorem RevisitedBruno Bauwens, Alexander Shen, Hayato TakahashiTheory of Computing Systems, Springer Verlag, 2017, 61 (4), pp.1315-1336.
2016
- Generic algorithms for halting problem and optimal machines revisitedLaurent Bienvenu, Damien Desfontaines, Alexander ShenLogical Methods in Computer Science, Logical Methods in Computer Science Association, 2016, Logical Methods in Computer Science, 12 (2), pp.1-29.
2015
- Topological Arguments for Kolmogorov ComplexityAndrei Romashchenko, Alexander ShenTheory of Computing Systems, Springer Verlag, 2015, 56 (3), pp.513-526.
- μ-Limit Sets of Cellular Automata from a Computational Complexity PerspectiveLaurent Boyer, Martin Delacourt, Victor Poupet, Mathieu Sablik, Guillaume TheyssierJournal of Computer and System Sciences, Elsevier, 2015, 81 (8), pp.1623-1647.
2014
- Minimal critical exponent of quasiperiodic wordsGwenaël RichommeTheoretical Computer Science, Elsevier, 2014, 548, pp.117-122.
- On the maximal weight of (p,q)-ary chain partitions with bounded partsFilippo Disanto, Laurent Imbert, Fabrice PhilippeIntegers : Electronic Journal of Combinatorial Number Theory, State University of West Georgia, Charles University, and DIMATIA, 2014, 14, pp.A37.
- Pseudo-Random Graphs and Bit Probe Schemes with One-Sided ErrorAndrei RomashchenkoTheory of Computing Systems, Springer Verlag, 2014, 55 (2), pp.313-329.
- Monte Carlo modeling of the dual-mode regime in quantum-well and quantum-dot semiconductor lasersLaurent Chusseau, Fabrice Philippe, Filippo DisantoOptics Express, Optical Society of America, 2014, 22 (5), pp.5312-5324.
- Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexityBruno Bauwens, Alexander ShenThe Journal of Symbolic Logic, Association for Symbolic Logic, 2014, 79 (02), pp.620-632.
- The axiomatic power of Kolmogorov complexityLaurent Bienvenu, Andrei Romashchenko, Alexander Shen, Antoine Taveneaux, Stijn VermeerenAnnals of Pure and Applied Logic, Elsevier Masson, 2014, 165 (9), pp.1380-1402.
- Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local LemmaAndrei Rumyantsev, Alexander ShenFundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2014, 132 (1), pp.1-14.
Communications internationales
2019
- Two Characterizations of Finite-State DimensionAlexander Kozachinskiy, Alexander ShenFCT: Fundamentals of Computation Theory, Aug 2019, Copenhagen, Denmark. pp.80-94.
- An algorithmic approach to characterizations of admissiblesBruno Durand, Grégory LafitteCiE: Computability in Europe, Jul 2019, Durham, United Kingdom. pp.181-192.
- Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional ShiftsAndrei Romashchenko, Julien DestombesSTACS: Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. pp.23:1--23:17.
- Random Noise Increases Kolmogorov Complexity and Hausdorff DimensionGleb Posobin, Alexander ShenSTACS: Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. pp.57:1--57:14.
- How to Use Undiscovered Information Inequalities: Direct Applications of the Copy LemmaEmirhan Gürpınar, Andrei Romashchenko2019 IEEE International Symposium on Information Theory (ISIT), Jul 2019, Paris, France. pp.1377-1381.
2018
- An operational characterization of mutual information in algorithmic information theoryAndrei Romashchenko, Marius ZimandICALP: International Colloquium on Automata, Languages, and Programming, Jul 2018, Prague, Czech Republic. pp.95:1-95:14.
- Algorithms and Geometric ConstructionsVladimir Uspenskiy, Alexander ShenCiE: Conference on Computability in Europe, Jul 2018, Kiel, Germany. pp.410-420.
- Plain stopping time and conditional complexities revisitedMikhail Andreev, Gleb Posobin, Alexander ShenMFCS: Mathematical Foundations of Computer Science, Aug 2018, Liverpool, United Kingdom. pp.2:1--2:12.
- Illustration du passage au seuil des nanolasers par une modélisation markovienneArthur Vallet, Laurent Chusseau, Alain Jean-Marie, Fabrice PhilippeOPTIQUE Toulouse, Jul 2018, Toulouse, France. <https://www.sfoptique.org/pages/congres-optique/optique-toulouse-2018/>
2017
- On the expressive power of quasiperiodic SFTAndrei Romashchenko, Bruno DurandMFCS: Mathematical Foundations of Computer Science, Aug 2017, Aalborg, Denmark. pp.5:1-5:14.
- A Characterization of Infinite LSP WordsGwenaël RichommeDLT: Developments in Language Theory, Aug 2017, Liège, Belgium. pp.320-331.
- Infinite Time Busy BeaversOscar Defrain, Bruno Durand, Grégory LafitteCiE: Conference on Computability in Europe, Jun 2017, Turku, Finland. pp.221-233.
- On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of VariablesDmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry SokolovSTACS: Symposium on Theoretical Aspects of Computer Science, Mar 2017, Hannover, Germany. pp.43:1-43:14.
- Differences Between 2D Neighborhoods According to Real Time ComputationAnaël GrandjeanDLT: Developments in Language Theory, Aug 2017, Liège, Belgium. pp.198-209.
- Semiconductor laser Markov models in the micro-canonical, canonical and grand-canonical ensemblesArthur Vallet, Laurent Chusseau, Fabrice Philippe, Alain Jean-MarieSigmaPhi, Jul 2017, Corfu, Greece. pp.1-42.
- Admissibles in GapsMerlin Carl, Bruno Durand, Grégory Lafitte, Sabrina OuazzaniCiE: Computability in Europe, Jun 2017, Turku, Finland. pp.175-186.
- Compressibility and Probabilistic ProofsAlexander ShenCIE: Computability in Europe, Jun 2017, Turku, Finland. pp.101-111.
- Automatic Kolmogorov Complexity and Normality RevisitedAlexander ShenFTC: Fundamentals of Computation Theory, Dec 2017, Bordeaux, France. pp.418-430.
- On shift-invariant maximal filters and hormonal cellular automataJulien Cervelle, Grégory LafitteLICS: Logic in Computer Science, Jun 2017, Reykjavik, Iceland. pp.1-10.
2016
- Determining Sets of Quasiperiods of Infinite WordsGuilhem Gamard, Gwenaël RichommeMFCS: Mathematical Foundations of Computer Science, Aug 2016, Cracovie, Poland. pp.40:1-40:13.
- A Linear Acceleration Theorem for 2D Cellular Automata on all Complete NeighborhoodsAnaël Grandjean, Victor PoupetICALP: International Colloquium on Automata, Languages and Programming, Jul 2016, Roma, Italy. pp.115:1--115:12.
- Constant Acceleration Theorem for Extended von Neumann NeighbourhoodsAnaël GrandjeanAUTOMATA, Jun 2016, Zurich, Switzerland. pp.149-158.
2015
- Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf ProblemDaniyar Chumbalov, Andrei RomashchenkoMFCS: Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. pp.235-247.
- Quasiperiodicity and non-computability in tilingsBruno Durand, Andrei RomashchenkoMFCS: Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. pp.218-230.
- What Percentage of Programs Halt?Laurent Bienvenu, Damien Desfontaines, Alexander ShenICALP: International Colloquium on Automata, Languages and Programming, EATCS, Jul 2015, Kyoto, Japan. pp.219-230.
- Coverability in Two DimensionsGuilhem Gamard, Gwenaël RichommeLATA: Language and Automata Theory and Applications, Mar 2015, Nice, France. pp.402-413.
- Comparing 1D and 2D Real Time on Cellular AutomataAnaël Grandjean, Victor PoupetSTACS: Symposium on Theoretical Aspects of Computer Science, Mar 2015, München, Germany. pp.367-378.
- 5-State Rotation-Symmetric Number-Conserving Cellular Automata are not Strongly UniversalKatsunobu Imai, Hisamichi Ishizaka, Victor PoupetAUTOMATA, Jul 2014, Himeji, Japan. pp.31-43.
- L-Convex Polyominoes Are Recognizable in Real Time by 2D Cellular AutomataAnaël Grandjean, Victor PoupetAUTOMATA, Jun 2015, Turku, Finland. pp.127-140.
2014
- Monte Carlo markovian modeling of modal competition in dual-wavelength semiconductor lasersLaurent Chusseau, Fabrice Philippe, Alain Jean-MariePhotonics West OPTO: Physics and Simulation of Optoelectronic Devices, Feb 2014, San Francisco, United States. <10.1117/12.2036268>
- Aperiodic Tilings and EntropyBruno Durand, Guilhem Gamard, Anaël GrandjeanDLT: Developments in Language Theory, Aug 2014, Ekaterinburg, Russia. pp.166-177.
- Algorithmic Identification of Probabilities Is HardLaurent Bienvenu, Benoit Monin, Alexander ShenALT: Algorithmic Learning Theory, Oct 2014, Bled, Slovenia. pp.85-95.
Dernière mise à jour le 09/12/2019
Département : Informatique
Responsable : Victor POUPET
Site de l'équipe : http://www.lirmm.fr/escape/