EA's photo

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 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. Till 2022 I was 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 member of the Modeling and Verification team (within Automata, structures and verification pole).

Research interests (chronological)

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 9-11 May 2016.

Since fall 2020 I am involved in three new projects

Conferences

Co-organizer:

Steering Committee member: FORMATS

Program Committee member:

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(*)

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 teaching-related pages are on Moodle

See also:

Old teaching-related 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

  1. E. Asarin, O. Maler, A. Pnueli, Reachability analysis of dynamical systems having piecewise-constant derivatives, Theoretical Computer Science 138 , 35-65, 1995 [Abstract] , [Postscript]
  2. E. Asarin, O. Maler, Discrete-continuous systems: an algorithmic aspect (in Russian) Avtomatika i Telemekhanika, 1995, No 5, 124-137. [Abstract] , [Postscript]
  3. E .Asarin, O. Maler, Achilles and the Tortoise Climbing Up the Arithmetical Hierarchy , J. of Computer and System Sciences 57 , 389-398, 1998. [Abstract] , [Pdf]
  4. E. Asarin, O. Bournez, T. Dang, O. Maler, A. Pnueli, Effective Synthesis of Switching Controllers for Linear Systems , Proceedings of the IEEE 88 , No. 7, 2000, 1011-1025 [Pdf]
  5. E. Asarin, P. Caspi, O. Maler, Timed Regular Expressions, Journal of the ACM 49 , No.2, 2002, 172-206 [Abstract] , [Pdf]
  6. 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
  7. Y. Abdeddaïm, E. Asarin, O. Maler Scheduling with Timed Automata, Theoretical Computer Science , 354 :2, 2006, 272-300, [Pdf]
  8. 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
  9. 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
  10. 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/
  11. E. Asarin, C. Dima, On the Computation of Covert Channel Capacity , RAIRO-ITA , 44, 2010, 37-58, doi:10.1051/ita/2010004
  12. 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
  13. 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
  14. D. Ulus, Th. Ferrère, E.Asarin, D. Nickovic, O. Maler: Elements of Timed Pattern Matching ACM Transactions on Embedded Computing Systems, 2024, DOI: 10.1145/3645114

Conference proceedings (editor)

  1. 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), DOI:10.1016/S1571-0661(05)80481-5
  2. 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

Conference proceedings

(see LNCS Homepage )

  1. 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]
  2. 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]
  3. 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]
  4. E. Asarin, O. Maler, P. Caspi, A Kleene Theorem for Timed Automata , in G. Winskel (Ed.) Proc. LICS'97 , 1997. [Abstract] , [Postscript]
  5. 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]
  6. 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]
  7. 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]
  8. 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]
  9. 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]
  10. 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]
  11. 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]
  12. 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]
  13. E. Asarin, A. Bouajjani, Perturbed Turing Machines and Hybrid Systems, LICS'2001 [Pdf]
  14. 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]
  15. 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
  16. 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
  17. 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
  18. E. Asarin, C. Dima: Balanced timed regular expressions. Electronic Notes in Theoretical Computer Science,Volume 68, Issue 5 , May 2003, Pages 1-18, DOI:10.1016/S1571-0661(04)80518-8
  19. 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
  20. Y. Abdeddaïm, E. Asarin, O. Maler, On Optimal Scheduling under Uncertainty TACAS 2003 240-255, LNCS 2619, © Springer-Verlag, 2003 [Postscript]
  21. 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]
  22. 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]
  23. 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]
  24. E. Asarin, P. Collins, Noisy Turing Machines , in. Proc. of ICALP'05 , 1031-1042 LNCS 3580, © Springer-Verlag , 2005. [Pdf]
  25. 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
  26. 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
  27. 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
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
  33. 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
  34. 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
  35. 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
  36. 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
  37. 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
  38. E. Asarin, M. Blockelet, A.Degorre, C.Dima, C.Mu, Asymptotic behaviour in temporal logic . CSL-LICS 2014 download
  39. 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
  40. 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
  41. 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
  42. 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
  43. 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
  44. 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
  45. 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
  46. B. Jacobo Inclán, E. Asarin, A.Degorre:  Bounded delay timed channel coding , FORMATS 2022, LNCS 13465, p.65-79, DOI:10.1007/978-3-031-15839-1_4
  47. Akshay Mambakam, Eugene Asarin, Nicolas Basset, and Thao Dang. 2023. Pattern Matching and Parameter Identification for Parametric Timed Regular Expressions. HSCC '23 DOI:10.1145/3575870.3587115 download
  48. E. Asarin, A. Degorre, C. Dima, B. Jacobo Inclán, Bandwidth of Timed Automata: 3 Classes. FSTTCS 2023, LIPIcs vol. 284 DOI: 10.4230/LIPIcs.FSTTCS.2023.10 . A longer version with proof details: arXiv:2310.01941

Manuscripts and preprints:

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

E-mail: asarin@irif.fr

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

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