- 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–12.
- 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.
Contact details
Address
Northampton Square
London EC1V 0HB
United Kingdom
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
Progam committee member:
- ICLA 2023
- FSTTCS 2022
- MFCS 2021
- CSR 2021
- Reachability Problems 2020
- LICS 2020
- ICALP 2019
- Reachability Problems 2018
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, Sep 2011 – Sep 2014
Employment
- Lecturer, City, University of London, Jan 2019 – present
- Post-doctoral research fellow, The University of Warwick, Sep 2017 – Jan 2019
- Post-doctoral research fellow, University of Warsaw, Oct 2016 – Aug 2017
- Post-doctoral researh fellow, ENS Lyon, Oct 2015 – Sep 2016
- Post-doctoral research fellow, Aix-Marseille University, Oct 2014 – Sep 2015
Publications
Publications by category
Conference papers and proceedings (16)
- Daviaud, L. and Purser, D. (2023). The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete). Thirty-Eighth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2023) 26-29 June, Boston, USA.
- 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
- 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
- Bojańczyk, M., Daviaud, L. and Krishna, S.N. (2018). Regular and first-order list functions. doi:10.1145/3209108.3209163
- 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 Feb 2013 – 2 Mar 2013, Kiel, Germany. doi:10.4230/LIPIcs.STACS.2013.574