Dr Laure Daviaud
Contact details
About
Overview
I joined City University as a lecturer in Computer Science in January 2019.
I am a member of CitAI, the research centre in artificial intelligence at City.
Research interests:
- Verification
- Logic
- Game and Automata theory
- Quantitative models (Probability and Optimisation)
- Transducers
- Streaming models
- Algebra and Topology for rational languages.
Supervision:
- Andrew Ryzhikov (Post-doctoral Researcher - started December 2020)
- Alex Dean (PhD student - started October 2020)
Grant:
- EPSRC New Investigator: Learning, Approximating and Minimising Streaming Automata for Large-scale Optimisation (EP/T018313/1), 09/2020-08/2023
Program committee member:
- CSR 2021
Journal Editor:
- AEJM
Publications:
For the most recent versions of my papers, see arXiv. If you cannot find one of my papers online, feel free to contact me.
Talks:
Tutorial on Probabilistic Automata
- Highlights of Logic, Games and Automata 2020 (Online-15/09/20): slides
Learning automata and weighted automata
- Seminar IRIF-University Paris VII (Online-26/06/20)
- Seminar QuantLa (Online-09/06/20)
The equivalence problem for weighted automata
- ICSAA 2019 (Kochi-09/12/19)
- QuantLa 2018 (Meissen-29/08/18): slides
Mean-payoff parity games
- INFINITY 2019 (Taipei-27/10/2019)
- HIGHLIGHTS of Logic, Games and Automata 2018 (Berlin-19/09/18): slides
- LICS 2018 (Oxford-09/07/18): slides
- Seminar LABRI (Bordeaux-05/06/18): slides
- Journées du GT Verif 2018 (Grenoble-29/05/18): slides
Regular transductions: First order and regular list functions
- TRENDS 2018 (Ahmedabad-10/12/18): slides
- Seminar LSC (Lyon-26/04/18): slides
Probabilistic automata and the containment problem
- Seminar ENS Lyon (Lyon-23/04/18): slides
- Delta 2018 (Paris-27/03/18): slides
Profinite theory and generalised star height problem
- Seminar University of York (York-22/01/20)
- ICART 2019 (Chalakudy-14/12/19)
- Seminar Heriot-Watt University (Edinburgh-20/02/19): slides
- Journées Montoises 2018 (Bodeaux-12/09/18): slides
- MFPS 2017 (Ljubljana-13/06/17): slides
- Conference Topology and Languages (Toulouse-23/06/16): slides
- MFCS 2015 (Milan-27/08/15): slides
- AMS-EMS-SPM International meeting 2015 (Porto-11/06/15): slides
Max-plus automata and tropical identities
- Seminar University of East Anglia (Norwich-07/11/18): slides
- Seminar University of Oxford (Oxford-01/02/18): slides
- Seminar IRIF (Paris-10/11/17)
- Tropical Mathematics and its Applications 2017 (Birmingham-15/11/17): slides
- Delta 2017 (Porquerolle-18/10/17): slides
- MFCS 2017 (Aalborg-22/08/17): slides
Comparison of max-plus automata and joint spectral radius
- MFCS 2017 (Aalborg-22/08/17): slides
- Seminar Manchester University (Manchester-23/11/16): slides
- PGMO Days 2016 (Palaiseau-09/11/16): slides
- Seminar Warsaw University (Warsaw-12/10/16)
- Seminar ULB (Bruxelles-22/09/16)
- ILAS 2016-minisymposium Tropical linear algebra and beyond (Louvain-12/07/16): slides
A generalised twinning property for minimisation of cost register automata
- Journées du GT ALGA (Marseille-12/04/16): slides
- Seminar LABRI (Bordeaux-09/02/16): slides
Asymptotic behaviours of min-plus and max-plus automata
- Seminar LIGM (Marnes-la-Vallée-27/05/14): slides
- Seminar LSV (Cachan-13/05/14): slides
- Groupe de travail FREC (Marseille-30/04/14): slides
Max-plus automata and size-change abstraction
- Workshop DICE (Eindhoven-02/04/16): slides
- Journées du GT ALGA (Paris-30/03/15): slides
- Seminar LIP (Lyon-05/03/15): slides
- Seminar LACL (Créteil-26/01/15): slides
- Seminar LABRI (Bordeaux-16/12/14): slides
- MFCS 2014 (Budapest-26/08/14): slides
- HIGHLIGHTS of Logic, Games and Automata 2014 (Paris-04/09/14): slides
- Seminar LITIS (Rouen-24/10/13): slides
Approximate comparison of min-plus automata
- Seminar I2M (Marseille-20/01/15)
- Seminar LIF (Marseille-25/03/14): slides
- STACS 2013 (Kiel-02/03/13): slides
- HIGHLIGHTS of Logic, Games and Automata 2013 (Paris-19/09/13): slides
- Seminar Warsaw University (Warsaw-12/06/13)
Qualifications
- PhD supervised by Thomas Colcombet and Jean-Eric Pin, University Paris VII, France, 2011 - September 2014
Employment
- Lecturer, City, University of London, UK, January 2019 - present
- Post-doctoral research fellow, The University of Warwick, UK, September 2017 - January 2019
- Post-doctoral research fellow, University of Warsaw, Poland, October 2016 - August 2017
- Post-doctoral researh fellow, ENS Lyon, France, October 2015 - September 2016
- Post-doctoral research fellow, Aix-Marseille University, France, October 2014 - September 2015
Publications
Publications by category
Conference papers and proceedings (21)
- Wickramasinghe, S.Y., Howe, J.M. and Daviaud, L. Extracting Deterministic Finite Automata from RNNs via Hyperplane Partitioning and Learning. .doi:10.1007/978-3-032-15638-9_8
- Wickramasinghe, S.Y., Howe, J.M. and Daviaud, L. (2025). Extracting Weighted Finite Automata from RNNs via iterative partitioning and spectral learning. International Workshop on Artificial Intelligence and Formal Verification, Logic, Automata, and Synthesis 26 October, Bologna.
- Daviaud, L. and Ryzhikov, A. Universality and Forall-Exactness of Cost Register Automata with Few Registers. .doi:10.4230/LIPIcs.MFCS.2023.40
- El-Naggar, N., Ryzhikov, A., Daviaud, L., Madhyastha, P. and Weyde, T. (2023). Formal and Empirical Studies of Counting Behaviour in ReLU RNNs. The 16th International Conference on Grammatical Inference 10-13 July.
- Daviaud, L. and Purser, D. (2023). The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete). 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 26-29 June.doi:10.1109/lics56636.2023.10175798
- Daviaud, L., Jurdzinski, M. and Thejaswini, K.S. (2020). The Strahler number of a parity game. 47th International Colloquium on Automata, Languages, and Programming (ICALP) 8-11 July, Saarbrucken, Germany.doi:10.4230/LIPIcs.ICALP.2020.123
- Daviaud, L., Jurdziński, M. and Lehtinen, K. (2019). Alternating Weak Automata from Universal Trees. 30th International Conference on Concurrency Theory (CONCUR) 26-31 August, Amsterdam, Netherlands.doi:10.4230/LIPIcs.CONCUR.2019.18
- Czerwiński, W., Daviaud, L., Fijalkow, N., Jurdziński, M., Lazić, R. and Parys, P. (2019). Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games. ACM-SIAM Symposium on Discrete Algorithms (SODA) 6-9 January, San Diego, California, USA.doi:10.1137/1.9781611975482.142
- Daviaud, L., Jurdzinski, M., Lazic, R., Mazowiecki, F., Pérez, G.A. and Worrell, J. (2018). When is containment decidable for probabilistic automata? 45th International Colloquium on Automata, Languages, and Programming (ICALP) 9-13 July, Prague, Czech Republic.doi:10.4230/LIPIcs.ICALP.2018.121
- Bojańczyk, M., Daviaud, L. and Krishna, S.N. Regular and first-order list functions. .doi:10.1145/3209108.3209163
- Daviaud, L., Jurdzinski, M. and Lazic, R. (2018). A pseudo-quasi-polynomial algorithm for mean-payoff parity games. 33th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 9-12 July, Oxford, UK.doi:10.1145/3209108.3209162
- Daviaud, L., Guillon, P. and Merlet, G. (2017). Comparison of max-plus automata and joint spectral radius of tropical matrices. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS) 21-25 August, Aalborg, Denmark.doi:10.4230/LIPIcs.MFCS.2017.19
- Daviaud, L. and Johnson, M. (2017). The shortest identities for max-plus automata with two states. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS) 21-25 August, Aalborg, Denmark.doi:10.4230/LIPIcs.MFCS.2017.48
- Bojanczyk, M., Daviaud, L., Guillon, B. and Penelle, V. (2017). Which classes of origin graphs are generated by transducers? 44th International Colloquium on Automata, Languages, and Programming (ICALP) 10-14 July, Warsaw, Poland.doi:10.4230/LIPIcs.ICALP.2017.114
- Daviaud, L., Jecker, I., Reynier, P.A. and Villevalois, D. (2017). Degree of sequentiality of weighted automata. 20th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS) 22-29 April, Uppsala, Sweden.doi:10.1007/978-3-662-54458-7_13
- Daviaud, L., Reynier, P.-.A. and Talbot, J.-.M. (2016). A Generalised Twinning Property for Minimisation of Cost Register Automata. 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 5-8 July, New-York City, USA.doi:10.1145/2933575.2934549
- Daviaud, L., Kuperberg, D. and Pin, J.-.E. (2016). Varieties of cost functions. 33rd International Symposium on Theoretical Aspects of Computer Science (STACS) 17-20 February, Orleans, France.doi:10.4230/LIPIcs.STACS.2016.30
- Daviaud, L. and Paperman, C. (2015). Classes of languages generated by the kleene star of a word. 40th International Symposium on Mathematical Foundations of Computer Science (MFCS) 24-28 August, Milan, Italy.doi:10.1007/978-3-662-48057-1_13
- Colcombet, T., Daviaud, L. and Zuleger, F. (2014). Size-change abstraction and max-plus automata. 39th International Symposium on Mathematical Foundations of Computer Science (MFCS) 25-29 August, Budapest, Hungary.doi:10.1007/978-3-662-44522-8_18
- Colcombet, T. and Daviaud, L. (2013). Approximate comparison of distance automata. 30th International Symposium on Theoretical Aspects of Computer Science (STACS) 27 February-2 March, Kiel, Germany.doi:10.4230/LIPIcs.STACS.2013.574
- Daviaud, L. Weighted Automata at the Border of Decidability. .doi:10.4204/eptcs.390.0.2
Journal articles (8)
- Daviaud, L. and Johnson, M. (2025). Feasability of Learning Weighted Automata on a Semiring. Logical Methods in Computer Science, Volume 21, Issue 3. doi:10.46298/lmcs-21(3:15)2025
- Daviaud, L., Purser, D. and Tcheng, M. (2025). The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete). Logical Methods in Computer Science, Volume 21, Issue 3. doi:10.46298/lmcs-21(3:3)2025
- Daviaud, L., Jurdziński, M., Lazić, R., Mazowiecki, F., Pérez, G.A. and Worrell, J. (2021). When are emptiness and containment decidable for probabilistic automata? Journal of Computer and System Sciences, 119, pp. 78-96. doi:10.1016/j.jcss.2021.01.006
- Daviaud, L. (2020). Register complexity and determinisation of max-plus automata. ACM SIGLOG News, 7(2), pp. 4-14. doi:10.1145/3397619.3397621
- Bojanczyk, M., Daviaud, L., Guillon, B., Penelle, V. and Sreejith, A.V. (2020). Undecidability of a weak version of MSO+U. Logical Methods in Computer Science, 16(1), pp. 12:1-12:15. doi:10.23638/LMCS-16(1:12)2020
- Daviaud, L. and Paperman, C. (2018). Classes of languages generated by the Kleene star of a word. Information and Computation, 262, pp. 90-109. doi:10.1016/j.ic.2018.07.002
- Daviaud, L., Johnson, M. and Kambites, M. (2018). Identities in upper triangular tropical matrix semigroups and the bicyclic monoid. Journal of Algebra, 501, pp. 503-525. doi:10.1016/j.jalgebra.2017.12.032
- Colcombet, T. and Daviaud, L. (2016). Approximate Comparison of Functions Computed by Distance Automata. Theory of Computing Systems, 58(4), pp. 579-613. doi:10.1007/s00224-015-9643-3