Eugene Asarin's home page
I was born in 1962 in Moscow. In 1984 I graduated from the Dept. of Mathematics and mechanics of Moscow State University, my specialization was the mathematical logic. In 1988 I made my Ph.D. "Individual random signals: an approach based on complexity", directed by A.Kolmogorov. In 1984-1988 I worked in M.Krasnosel'skii's team at the Institute for Control Science in Moscow. In 1990-1999 I was at the Institute for Information Transmission Problems in Moscow. Now I am an external member of that institute.
Since 1999 I was working as professor of computer science at the Université Joseph Fourier (Grenoble, France). My research work was done at VERIMAG laboratory (I cooperated with it since 1994).
In September 2003 I moved to Université Paris Diderot - Paris 7 and LIAFA. In 2016 LIAFA was reorganized to become part of IRIF institute (see contact information below); since 2020 my university became part of Université Paris Cité. I am head of the Modeling and Verification team (within Automata, structures and verification pole).
Research interests (chronological)
- Kolmogorov Complexity
- Desynchronized Linear Systems (almost forgotten)
- Cyber-physical, Hybrid, Timed Systems (main research interest now)
- Information and entropy (hot!)
In November 2011 – May 2016 I coordinated EQINOCS project (Entropy and quantity of information in computational systems) financed by ANR. Concluding EQINOCS workshop was organized in Paris on 9-11 May 2016.
Since fall 2020 I am involved in three new projects
- CyPhAI; (Formal Analysis and Design of AI-intensive Cyber-Physical Systems) – Franco-Japanese ANR-JST project
- MAVERIQ (Methods of Analysis for VERIfication of Quantitative properties)
- DIFFERENCE (Complexity Theory with Discrete Differential/Difference Equations)
Steering Committee member: FORMATS
Program Committee member:
- LFCS'16 and 18
- HSCC (several times)
- FORMATS (several times)
NEW! HOT! PhD thesis on cyber-physical systems, verification and learning available
What: A fully funded PhD position in Computer Science with the subject “Cyber-physical systems with AI components: modeling, learning and verification” opens in Paris, starting in September or October 2022. Excellent and motivated candidates are invited to apply.
With whom: Prof. Eugene Asarin, Dr. Mohammed Foughali, Dr. Peter Habermehl
Where: The PhD position will be hosted by IRIF (Institut de Recherche en Informatique Fondamentale), in the Modeling and verification team, in the framework of the Franco-Japanese research project CyPhAI.
IRIF is a research unit co-founded by CNRS and Université Paris Cité. The research conducted at IRIF is based on the study and understanding of the foundations of all computer science, in order to provide innovative solutions to the current and future challenges of digital sciences. In particular, IRIF is renowned for its contributions to the design and analysis of algorithms, the study of computational and data representation models, the foundations of programming languages, software development, verification, and certification
The research activities of the Modeling and verification team address the development of algorithmic approaches to system verification, from theoretical foundations to innovative verification tools.
The project CyPhAI is dedicated to modeling, identification, design and verification of cyber-physical systems with artificial intelligence components. It involves researchers from Grenoble, Paris, Toulouse, Kyoto and Osaka.
The PhD student will be based in IRIF, Paris, and will have an opportunity (but not an obligation) to teach (in French or even in English). Research visits to other partners of CyPhAI project in France and in Japan will be possible.
What will the thesis be about: Cyber-physical systems (CPS) are computer-based systems where the computer software and the physical world (of both the system and its environment) are tightly. CPS are omnipresent in everyday's life and their applications continue to proliferate – in robotics, industry, home appliances etc. Elegant and powerful mathematical models, such as hybrid and timed automata are used to represent CPS, design them and verify their properties. In recent years, more and more CPS are equipped with components from the domain of artificial intelligence – AI (computer vision systems with neural networks, and even controllers based on reinforcement learning), it suffices to mention self-driving cars and other autonomous systems. The thesis will be centered on several aspects of modeling, learning and verification of such CPS-AI systems.
- Defining mathematical models of CPS-AI, based on hybrid, timed and/or probabilistic automata. Validating their relevance by modeling real-life systems. The challenge is to have several levels, from very precise models (suitable for simulation), to more abstract (e.g., for verification) to very abstract one (for human-understandable explanation)
- Learning/identifying models of CPS from observational data. Combining, in a pragmatic way, ideas from automata theory with model identification from control science, and with machine learning with neural networks. Using active and passive, black-box and white-box setting.
- Formalizing and solving problems of quantitative verification of CPS: to what extent the CPS satisfies a specification. In off-line (model-checking) and on-line (monitoring) setting. For the three aspects we expect to follow the path from practical examples to clean mathematical definitions, theorems describing their properties, to algorithms, prototype tools, and experimental work on real-life benchmarks. Depending on the candidate profile, the focus will be on some of these aspects.
For whom: The candidate should have a master’s (or equivalent) degree in computer science or a closely related field, graduated or expected to graduate before October 2022. The most important selection criterion is their motivation and capacity of doing creative research combining fundamental and applied aspects. We require a solid background in theoretical computer science: automata, logic, algorithmics, complexity, as well as basic knowledge of mathematics (calculus, probability). Acquaintance with formal methods/verification, cyber-physical systems and their models (timed and hybrid automata), as well as machine learning (based on automata or on neural networks) will be appreciated but is not mandatory. Advanced programming skills are not required but highly appreciated.
How to apply: An application, in a free form, in English or French, should be sent by e-mail to the three addresses: email@example.com, firstname.lastname@example.org, email@example.com It may contain some of the following: a CV, a motivation letter, references or recommendation letters, transcripts of grades for master’s studies, links to publications or MSc thesis if relevant. Please send the application as soon as possible : the PhD should start in September or soon thereafter.
Subjects for master theses
The internships marked by (*) have been realized in summer 2021, but can be continued. I will update the descriptions soon.
They are related to starting research projects and can be continued with PhD theses.
Somewhat simpler versions for L3-ENS or M1 level here(*)
These pages are in French
I am member of and mostly teaching at UFR d'Informatique de l'Université Paris Cité. I am also strongly involved at École d'Ingénieur Denis Diderot (EIDD).
Most of my recent teaching-related pages are on Moodle
Old teaching-related pages
Also in French
Grenoble 1 (very old):
PhD thesis "Individual random signals: an approach based on complexity" (1988, in Russian) [djvu]
List of publications before 1994
- E. Asarin, O. Maler, A. Pnueli, Reachability analysis of dynamical systems having piecewise-constant derivatives,Theoretical Computer Science138, 35-65, 1995 [Abstract],[Postscript]
- E. Asarin, O. Maler, Discrete-continuous systems: an algorithmic aspect (in Russian) Avtomatika i Telemekhanika, 1995, No 5, 124-137. [Abstract], [Postscript]
- E .Asarin, O. Maler, Achilles and the Tortoise Climbing Up the Arithmetical Hierarchy, J. of Computer and System Sciences57, 389-398, 1998. [Abstract],[Pdf]
- E. Asarin, O. Bournez, T. Dang, O. Maler, A. Pnueli, Effective Synthesis of Switching Controllers for Linear Systems, Proceedings of the IEEE88, No. 7, 2000, 1011-1025 [Pdf]
- E. Asarin, P. Caspi, O. Maler, Timed Regular Expressions,Journal of the ACM49, No.2, 2002, 172-206 [Abstract], [Pdf]
- E. Asarin, Challenges in Timed Languages: From Applied Theory to Basic Theory,The Bulletin of the European Association for Theoretical Computer Science, Number 83, June, 2004 hal-00157685
- Y. Abdeddaïm, E. Asarin, O. Maler Scheduling with Timed Automata, Theoretical Computer Science, 354:2, 2006, 272-300, [Pdf]
- E. Asarin, T. Dang, A. Girard, Hybridization methods for the analysis of nonlinear systems,Acta Informatica,43:7, 2007, 451-476 , doi:10.1007/s00236-006-0035-7
- E. Asarin, G. Schneider, S. Yovine, Algorithmic Analysis of Polygonal Hybrid Systems, Part I: Reachability, Theoretical Computer Science, 379:1-2, 2007, 231-265, doi:10.1016/j.tcs.2007.03.055
- E. Asarin, G. Pace, G. Schneider, S. Yovine, Algorithmic Analysis of Polygonal Hybrid Systems, Part II: Phase Portrait and Tools, Theoretical Computer Science, 390, 2008, 1-26, hal-00172768/
- E. Asarin, C. Dima, On the Computation of Covert Channel Capacity, RAIRO-ITA, 44, 2010, 37-58, doi:10.1051/ita/2010004
- E. Asarin, V. Mysore, A. Pnueli, G. Schneider, Low dimensional hybrid systems - decidable, undecidable, don't know,Information and Computation,211, 2012, 138-159, doi:10.1016/j.ic.2011.11.006
- E. Asarin, N. Basset, A. Degorre, Entropy of timed regular languages,Information and Computation, 241, 2015, 142-176, doi:10.1016/j.ic.2015.03.003
Conference proceedings (editor)
- Eugene Asarin, Oded Maler and Sergio Yovine, Theory and Practice of Timed Systems (Satellite Event of ETAPS 2002)
Grenoble, France, 6 - 7 April 2002, ENTCS, Volume 65, Issue 6, Pages 1-31 (June 2002), http://www.sciencedirect.com/science/journal/15710661
- Eugene Asarin, Patricia Bouyer, Formal Modeling and Analysis of Timed Systems, 4th International Conference, FORMATS 2006, Paris, France, September 25-27, 2006. Proceedings LNCS 4202, © Springer, http://www.springerlink.com/content/978-3-540-45026-9
- E. Asarin, O. Maler, On some Relations between Dynamical Systems and Transition Systems, in S. Abiteboul and E. Shamir (Eds.), Proc. of ICALP'94, 59-72, LNCS 820, © Springer-Verlag , 1994. [Abstract], [Postscript]
- E. Asarin, O. Maler and A.Pnueli, Symbolic Controller Synthesis for Discrete and Timed Systems, in P. Antsaklis, W. Kohn, A. Nerode and S. Sastry (Eds.), Hybrid Systems II, LNCS 999, © Springer-Verlag, 1995. [Abstract],[Postscript]
- E. Asarin, M. Bozga, A. Kerbrat, O. Maler, A. Pnueli, A. Rasse, Data-Structures for the Verification of Timed Automata, in O. Maler (Ed.), Proc. HART'97, 346-360, LNCS 1201, © Springer-Verlag, 1997. [Abstract],[Postscript]
- E. Asarin, O. Maler, P. Caspi, A Kleene Theorem for Timed Automata, in G. Winskel (Ed.) Proc. LICS'97, 1997. [Abstract], [Postscript]
- E. Asarin, Equations on Timed Languages, in T.Henzinger and S. Sastry (Eds.), Hybrid Systems : Computation and Control, LNCS 1386, © Springer-Verlag, 1998. [Abstract], [Pdf]
- E. Asarin, O. Maler, A.Pnueli, J. Sifakis, Controller Synthesis for Timed Automata, in Proc. IFAC Symposium on System Structure and Control, 469-474, Elsevier, 1998. [Abstract],[Postscript]
- E. Asarin, O. Maler, A. Pnueli, On Discretization of Delays in Timed Automata and Digital Circuits in R. de Simone and D. Sangiorgi (Eds), Proc. Concur'98, 470-484, LNCS 1466, © Springer-Verlag, 1998. [Postscript]
- E. Asarin, O. Maler, As Soon as Possible: Time Optimal Control for Timed Automata. in F. Vaandrager and J. van Schuppen (Eds.), Hybrid Systems: Computation and Control, 19-30, LNCS 1569, © Springer-Verlag, 1999. [Pdf]
- E. Asarin, O. Bournez, T. Dang, O. Maler, Approximate Reachability Analysis of Piecewise-Linear Dynamical Systems. in B. Krogh and N. Lynch (Eds.) Hybrid Systems: Computation and Control , 20-31 LNCS 1790, © Springer-Verlag, 2000. [Postscript]
- A. Annichini, E. Asarin, A. Bouajjani , Symbolic Techniques for Parametric Reasoning about Counter and Clock Systems , in Proc. 12th Intern. Conf. on Computer Aided Verification (CAV'00), LNCS 1855, Chicago (Il, USA), July 2000. [Postscript]
- E. Asarin, G. Schneider, S.Yovine. On the Decidability of the Reachability Problem for Planar Differential Inclusions. in M. Di Benedetto and A. Sangiovanni-Vincentelli (Eds.) Hybrid Systems: Computation and Control, 89-104, LNCS 2034, © Springer-Verlag, 2001. [Pdf]
- E. Asarin, S. Bansal, B. Espiau, T. Dang, Oded Maler. On Hybrid Control of Under-actuated Mechanical Systems. in M. Di Benedetto and A. Sangiovanni-Vincentelli (Eds.) Hybrid Systems: Computation and Control, 77-88, LNCS 2034, © Springer-Verlag, 2001. [Pdf]
- E. Asarin, A. Bouajjani, Perturbed Turing Machines and Hybrid Systems, LICS'2001 [Pdf]
- E. Asarin, G. Schneider, S.Yovine. Towards Computing Phase Portraits of Polygonal Differential Inclusions. in C.J. Tomlin and M.R. Greenstreet (Eds.) Hybrid Systems: Computation and Control, 49-61, LNCS 2289, © Springer-Verlag, 2002. [Pdf]
- E. Asarin, G. Pace, G. Schneider and S. Yovine. SPeeDI - a Verification Tool for Polygonal Hybrid Systems. In: CAV'2002, Copenhagen, Denmark, July 2002, 354-358, LNCS 2404 © Springer-Verlag Postscript
- E. Asarin, T. Dang, O. Maler. The d/dt Tool for Verification of Hybrid Systems. In: CAV'2002, Copenhagen, Denmark, July 2002, 365-370, LNCS 2404 © Springer-Verlag Postscript
- E. Asarin and G. Schneider. Widening the boundary between decidable and undecidable hybrid systems. In: CONCUR'2002, Brno, Czech Republic, August 2002, 193-208, LNCS 2421. © Springer-Verlag Postscript
- E. Asarin, C. Dima: Balanced timed regular expressions. Electronic Notes in Theoretical Computer Science, Volume 68, Issue 5 , May 2003, Pages 1-18.
- P. Niebert, M. Mahfoudh, E. Asarin, M. Bozga, N. Jain, O. Maler, Verification of Timed Automata via Satisfiability Checking. In: FTRTFT'2002, Oldenburg, Germany, September 2002, 225-243, LNCS 2469, © Springer-Verlag, Postscript
- Y. Abdeddaïm, E. Asarin, O. Maler, On Optimal Scheduling under UncertaintyTACAS 2003 240-255, LNCS 2619, © Springer-Verlag, 2003 [Postscript]
- E. Asarin, T. Dang, and A. Girard. Reachability Analysis of Nonlinear Systems Using Conservative Approximation. HSCC'03 - Hybrid Systems: Control and Computation, 20-35, LNCS 2623, © Springer-Verlag, April 2003. [ps.gz]
- E. Asarin and T. Dang, Abstraction by projection and application to multi-affine systems. HSCC'04 - Hybrid Systems: Control and Computation, 32-47, LNCS 2993, © Springer-Verlag March 2004. [ps.gz]
- S. Cotton, E. Asarin, O. Maler, P. Niebert, Some Progress in Satisfiability Checking for Difference Logic, FORMATS/FTRTFT 2004, 63-76, LNCS 3253. © Springer-Verlag [Pdf]
- E. Asarin, P. Collins, Noisy Turing Machines, in. Proc. of ICALP'05, 1031-1042 LNCS 3580, © Springer-Verlag , 2005. [Pdf]
- E. Asarin, Th. Cachat, A. Seliverstov, T. Touili, V. Lyubetsky. Attenuation Regulation as a Term Rewriting System, Algebraic Biology, LNCS 4545, © Springer-Verlag, 2007, p.81-94. hal-00154748
- Y. Abdeddaïm, E. Asarin, M. Gallien, F. Ingrand, Ch. Lesire, M. Sighireanu: Planning Robust Temporal Plans: A Comparison Between CBTP and TGA Approaches. ICAPS 2007: 2-9
- Y. Abdeddaïm, E. Asarin, M. Sighireanu : Simple strategies for simple timed games. TIME'09, Int. Symp on Temporal Representation and Reasoning, IEEE Computer Society, 2009, p.99-106 hal-00374700
- E. Asarin, A. Degorre, Volume and Entropy of Regular Timed Languages: Discretization Approach.CONCUR'09, LNCS 5710, © Springer-Verlag, 2009, p.69-83. See preprint hal-00369812
- E. Asarin, A. Degorre, Volume and Entropy of Regular Timed Languages: Analytic Approach. FORMATS'09, LNCS 5813, © Springer-Verlag, 2009, p.13-27. Best Paper Award. See preprint hal-00369812
- E.Asarin, R. Chane-Yack-Fa, D. Varacca, Fair adversaries and randomization in two-player games. FOSSACS'10, LNCS 6014, © Springer-Verlag, 2010, p.64-78, doi:10.1007/978-3-642-12032-9_6
- E. Asarin, T. Dang, O. Maler, R. Testylier, Using Redundant Constraints for Refinement,ATVA'10, LNCS 6252, © Springer-Verlag, 2010, p. 37-51, DOI: 10.1007/978-3-642-15643-4_5
- E. Asarin, A. Degorre, Two size measures for timed languages, FSTTCS'10, LIPICS vol. 8, DOI:10.4230/LIPIcs.FSTTCS.2010.376. A long version : hal-00527852
- N. Basset, E. Asarin, Thin and thick timed regular languages, FORMATS'11, LNCS 6919, © Springer-Verlag, 2011, p.113-128, DOI: 10.1007/978-3-642-24310-3_9
- E. Asarin, A. Donzé, O. Maler and D. Nickovic. Parametric Identification of Temporal Properties, RV'11, LNCS 7186, p. 147-160, © Springer-Verlag, 2012, DOI: 10.1007/978-3-642-29860-8_12
- E. Asarin, N. Basset, A. Degorre, D. Perrin, Generating functions of timed languages, MFCS'12, LNCS 7464, p. 124-135, © Springer-Verlag, 2012, a preprint version hal-00678443
- E. Asarin, N. Basset, M.-P. Béal, A. Degorre, D. Perrin, Toward a timed theory of channel coding, FORMATS'12, LNCS 7595, 27-42, p. 124-135, © Springer-Verlag, 2012, DOI: 10.1007/978-3-642-33365-1_4
- E. Asarin, N. Basset, A. Degorre: Spectral Gap in Timed Automata. FORMATS'13, LNCS 8053, p.16-30, © Springer-Verlag, 2012, DOI:10.1007/978-3-642-40229-6_2
- E. Asarin, M. Blockelet, A.Degorre, C.Dima, C.Mu, Asymptotic behaviour in temporal logic. CSL-LICS 2014: 10
- D. Ulus, Th. Ferrère, E.Asarin, O. Maler: Timed Pattern Matching. FORMATS 2014: 222-236 DOI: 10.1007/978-3-319-10512-3_16
- E. Asarin, J. Cervelle, A. Degorre, C. Dima, F. Horn, V. Kozyakin, Entropy Games and Matrix Multiplication Games. STACS 2016, LIPICS vol. 47, DOI: 10.4230/LIPIcs.STACS.2016.11. A longer version with proof details: hal-01164086
- D. Ulus, Th. Ferrère, E.Asarin, O. Maler: Online Timed Pattern Matching Using Derivatives. TACAS 2016, LNCS 9636, p.736-751, © Springer-Verlag, DOI: 10.1007/978-3-662-49674-9_47
- E. Asarin, O. Maler, D.Nickovic, D. Ulus: Combining the Temporal and Epistemic Dimensions for MTL Monitoring. FORMATS 2017: 207-223, LNCS 10419, DOI: 10.1007/978-3-319-65765-3_12
- E. Asarin, N. Basset, A. Degorre: Distance on timed words and applications, FORMATS 2018, LNCS 11022, p. 199-214. Best paper award DOI:10.1007/978-3-030-00151-3_12
- A. Bakhirkin, Th. Ferrère, D. Nickovic, O. Maler, E. Asarin: Online Timed Pattern Matching using Automata, FORMATS 2018, LNCS 11022, p. 215-232, DOI:10.1007/978-3-030-00151-3_13
- E. Asarin, Th. Ferrère, D. Nickovic, D. Ulus: On the Complexity of Timed Pattern Matching, FORMATS 2021, LNCS 12860, p. 1-17, "Oded Maler best paper award ", DOI:10.1007/978-3-030-85037-1_2
- B. Jacobo Inclán, E. Asarin, A.Degorre: Bounded delay timed channel coding, FORMATS 2022, LNCS , to appear
Manuscripts and preprints:
- Chaos and Undecidability (Based on invited talk at the workshop on Hybrid Systems at Grenoble, 1995) [Pdf]
CNRS and Université Paris Cité, Case 7014
75205 Paris Cedex 13
8 place Aurélie Nemours, 75013 Paris, France
Sophie Germain building, office 4040
Phone: +33 (0) 1 57 27 92 34
Fax : +33 (0) 1 57 27 94 09