
Eugene Asarin's home page

Short resume:
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 19841988 I worked in M.Krasnosel'skii's team at the Institute for Control Science in Moscow. In 19901999 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)
 Cyberphysical, Hybrid, Timed Systems (main research interest now)
 Verification
 Information and entropy (hot!)
Projects
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 911 May 2016.
Since fall 2020 I am involved in three new projects
 CyPhAI; (Formal Analysis and Design of AIintensive CyberPhysical Systems) – FrancoJapanese ANRJST project
 MAVERIQ (Methods of Analysis for VERIfication of Quantitative properties)
 DIFFERENCE (Complexity Theory with Discrete Differential/Difference Equations)
Conferences
Coorganizer:
Steering Committee member: FORMATS
Program Committee member:
 ATVA'22
 LFCS'16 and 18
 HSCC (several times)
 FORMATS (several times)
 LATA'14
 FOSSACS'13
 STACS'07
 CSR'07
 RP'09
NEW! HOT! PhD thesis on cyberphysical systems, verification and learning available
What: A fully funded PhD position in Computer Science with the subject “Cyberphysical 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 FrancoJapanese research project CyPhAI.
IRIF is a research unit cofounded 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 cyberphysical 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: Cyberphysical systems (CPS) are computerbased 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 selfdriving cars and other autonomous systems. The thesis will be centered on several aspects of modeling, learning and verification of such CPSAI systems.
 Defining mathematical models of CPSAI, based on hybrid, timed and/or probabilistic automata. Validating their relevance by modeling reallife 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 humanunderstandable 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, blackbox and whitebox setting.
 Formalizing and solving problems of quantitative verification of CPS: to what extent the CPS satisfies a specification. In offline (modelchecking) and online (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 reallife 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, cyberphysical 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 email to the three addresses: asarin@irif.fr, foughali@irif.fr, haberm@irif.fr 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 L3ENS or M1 level here(*)
Teaching activity:
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 teachingrelated pages are on Moodle
See also:
Old teachingrelated pages
Also in French
Paris 7:
Grenoble 1 (very old):
Publications
Thesis
PhD thesis "Individual random signals: an approach based on complexity" (1988, in Russian) [djvu]
List of publications before 1994
here
Journal papers
 E. Asarin, O. Maler, A. Pnueli, Reachability analysis of dynamical systems having piecewiseconstant derivatives,Theoretical Computer Science138, 3565, 1995 [Abstract],[Postscript]
 E. Asarin, O. Maler, Discretecontinuous systems: an algorithmic aspect (in Russian) Avtomatika i Telemekhanika, 1995, No 5, 124137. [Abstract], [Postscript]
 E .Asarin, O. Maler, Achilles and the Tortoise Climbing Up the Arithmetical Hierarchy, J. of Computer and System Sciences57, 389398, 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, 10111025 [Pdf]
 E. Asarin, P. Caspi, O. Maler, Timed Regular Expressions,Journal of the ACM49, No.2, 2002, 172206 [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 hal00157685
 Y. Abdeddaïm, E. Asarin, O. Maler Scheduling with Timed Automata, Theoretical Computer Science, 354:2, 2006, 272300, [Pdf]
 E. Asarin, T. Dang, A. Girard, Hybridization methods for the analysis of nonlinear systems,Acta Informatica,43:7, 2007, 451476 , doi:10.1007/s0023600600357
 E. Asarin, G. Schneider, S. Yovine, Algorithmic Analysis of Polygonal Hybrid Systems, Part I: Reachability, Theoretical Computer Science, 379:12, 2007, 231265, 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, 126, hal00172768/
 E. Asarin, C. Dima, On the Computation of Covert Channel Capacity, RAIROITA, 44, 2010, 3758, 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, 138159, doi:10.1016/j.ic.2011.11.006
 E. Asarin, N. Basset, A. Degorre, Entropy of timed regular languages,Information and Computation, 241, 2015, 142176, 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 131 (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 2527, 2006. Proceedings LNCS 4202, © Springer, http://www.springerlink.com/content/9783540450269
Conference proceedings
(seeLNCS Homepage)
 E. Asarin, O. Maler, On some Relations between Dynamical Systems and Transition Systems, in S. Abiteboul and E. Shamir (Eds.), Proc. of ICALP'94, 5972, LNCS 820, © SpringerVerlag , 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, © SpringerVerlag, 1995. [Abstract],[Postscript]
 E. Asarin, M. Bozga, A. Kerbrat, O. Maler, A. Pnueli, A. Rasse, DataStructures for the Verification of Timed Automata, in O. Maler (Ed.), Proc. HART'97, 346360, LNCS 1201, © SpringerVerlag, 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, © SpringerVerlag, 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, 469474, 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, 470484, LNCS 1466, © SpringerVerlag, 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, 1930, LNCS 1569, © SpringerVerlag, 1999. [Pdf]
 E. Asarin, O. Bournez, T. Dang, O. Maler, Approximate Reachability Analysis of PiecewiseLinear Dynamical Systems. in B. Krogh and N. Lynch (Eds.) Hybrid Systems: Computation and Control , 2031 LNCS 1790, © SpringerVerlag, 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. SangiovanniVincentelli (Eds.) Hybrid Systems: Computation and Control, 89104, LNCS 2034, © SpringerVerlag, 2001. [Pdf]
 E. Asarin, S. Bansal, B. Espiau, T. Dang, Oded Maler. On Hybrid Control of Underactuated Mechanical Systems. in M. Di Benedetto and A. SangiovanniVincentelli (Eds.) Hybrid Systems: Computation and Control, 7788, LNCS 2034, © SpringerVerlag, 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, 4961, LNCS 2289, © SpringerVerlag, 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, 354358, LNCS 2404 © SpringerVerlag Postscript
 E. Asarin, T. Dang, O. Maler. The d/dt Tool for Verification of Hybrid Systems. In: CAV'2002, Copenhagen, Denmark, July 2002, 365370, LNCS 2404 © SpringerVerlag Postscript
 E. Asarin and G. Schneider. Widening the boundary between decidable and undecidable hybrid systems. In: CONCUR'2002, Brno, Czech Republic, August 2002, 193208, LNCS 2421. © SpringerVerlag Postscript
 E. Asarin, C. Dima: Balanced timed regular expressions. Electronic Notes in Theoretical Computer Science, Volume 68, Issue 5 , May 2003, Pages 118.
 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, 225243, LNCS 2469, © SpringerVerlag, Postscript
 Y. Abdeddaïm, E. Asarin, O. Maler, On Optimal Scheduling under UncertaintyTACAS 2003 240255, LNCS 2619, © SpringerVerlag, 2003 [Postscript]
 E. Asarin, T. Dang, and A. Girard. Reachability Analysis of Nonlinear Systems Using Conservative Approximation. HSCC'03  Hybrid Systems: Control and Computation, 2035, LNCS 2623, © SpringerVerlag, April 2003. [ps.gz]
 E. Asarin and T. Dang, Abstraction by projection and application to multiaffine systems. HSCC'04  Hybrid Systems: Control and Computation, 3247, LNCS 2993, © SpringerVerlag March 2004. [ps.gz]
 S. Cotton, E. Asarin, O. Maler, P. Niebert, Some Progress in Satisfiability Checking for Difference Logic, FORMATS/FTRTFT 2004, 6376, LNCS 3253. © SpringerVerlag [Pdf]
 E. Asarin, P. Collins, Noisy Turing Machines, in. Proc. of ICALP'05, 10311042 LNCS 3580, © SpringerVerlag , 2005. [Pdf]
 E. Asarin, Th. Cachat, A. Seliverstov, T. Touili, V. Lyubetsky. Attenuation Regulation as a Term Rewriting System, Algebraic Biology, LNCS 4545, © SpringerVerlag, 2007, p.8194. hal00154748
 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: 29
 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.99106 hal00374700
 E. Asarin, A. Degorre, Volume and Entropy of Regular Timed Languages: Discretization Approach.CONCUR'09, LNCS 5710, © SpringerVerlag, 2009, p.6983. See preprint hal00369812
 E. Asarin, A. Degorre, Volume and Entropy of Regular Timed Languages: Analytic Approach. FORMATS'09, LNCS 5813, © SpringerVerlag, 2009, p.1327. Best Paper Award. See preprint hal00369812
 E.Asarin, R. ChaneYackFa, D. Varacca, Fair adversaries and randomization in twoplayer games. FOSSACS'10, LNCS 6014, © SpringerVerlag, 2010, p.6478, doi:10.1007/9783642120329_6
 E. Asarin, T. Dang, O. Maler, R. Testylier, Using Redundant Constraints for Refinement,ATVA'10, LNCS 6252, © SpringerVerlag, 2010, p. 3751, DOI: 10.1007/9783642156434_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 : hal00527852
 N. Basset, E. Asarin, Thin and thick timed regular languages, FORMATS'11, LNCS 6919, © SpringerVerlag, 2011, p.113128, DOI: 10.1007/9783642243103_9
 E. Asarin, A. Donzé, O. Maler and D. Nickovic. Parametric Identification of Temporal Properties, RV'11, LNCS 7186, p. 147160, © SpringerVerlag, 2012, DOI: 10.1007/9783642298608_12
 E. Asarin, N. Basset, A. Degorre, D. Perrin, Generating functions of timed languages, MFCS'12, LNCS 7464, p. 124135, © SpringerVerlag, 2012, a preprint version hal00678443
 E. Asarin, N. Basset, M.P. Béal, A. Degorre, D. Perrin, Toward a timed theory of channel coding, FORMATS'12, LNCS 7595, 2742, p. 124135, © SpringerVerlag, 2012, DOI: 10.1007/9783642333651_4
 E. Asarin, N. Basset, A. Degorre: Spectral Gap in Timed Automata. FORMATS'13, LNCS 8053, p.1630, © SpringerVerlag, 2012, DOI:10.1007/9783642402296_2
 E. Asarin, M. Blockelet, A.Degorre, C.Dima, C.Mu, Asymptotic behaviour in temporal logic. CSLLICS 2014: 10
 D. Ulus, Th. Ferrère, E.Asarin, O. Maler: Timed Pattern Matching. FORMATS 2014: 222236 DOI: 10.1007/9783319105123_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: hal01164086
 D. Ulus, Th. Ferrère, E.Asarin, O. Maler: Online Timed Pattern Matching Using Derivatives. TACAS 2016, LNCS 9636, p.736751, © SpringerVerlag, DOI: 10.1007/9783662496749_47
 E. Asarin, O. Maler, D.Nickovic, D. Ulus: Combining the Temporal and Epistemic Dimensions for MTL Monitoring. FORMATS 2017: 207223, LNCS 10419, DOI: 10.1007/9783319657653_12
 E. Asarin, N. Basset, A. Degorre: Distance on timed words and applications, FORMATS 2018, LNCS 11022, p. 199214. Best paper award DOI:10.1007/9783030001513_12
 A. Bakhirkin, Th. Ferrère, D. Nickovic, O. Maler, E. Asarin: Online Timed Pattern Matching using Automata, FORMATS 2018, LNCS 11022, p. 215232, DOI:10.1007/9783030001513_13
 E. Asarin, Th. Ferrère, D. Nickovic, D. Ulus: On the Complexity of Timed Pattern Matching, FORMATS 2021, LNCS 12860, p. 117, "Oded Maler best paper award ", DOI:10.1007/9783030850371_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]
Contact information
Mailing address:
Eugene Asarin IRIF CNRS and Université Paris Cité, Case 7014 75205 Paris Cedex 13 FRANCE

Physical address: 8 place Aurélie Nemours, 75013 Paris, France
Sophie Germain building, office 4040

Email: asarin@irif.fr

Phone: +33 (0) 1 57 27 92 34

Fax : +33 (0) 1 57 27 94 09

