Publications

Matching walks that are minimal with respect to edge inclusion

ArXiv preprint:2408.14048. 2024.

@misc{Marsault2024,
    author  = {Victor Marsault},
    title   = {Matching walks that are minimal with respect to edge inclusion},
    year    = {2024},
    note    = {ArXiv preprint:2408.14048},
    url     = {https://arxiv.org/abs/2408.14048}
}

Queries with External Predicates

Joint work with Paolo Guagliardo, Leonid Libkin, Wim Martens, Filip Murlak, Liat Peterfreund, Cristina Sirangelo.

In the proceedings of ICDT. To appear. 2025.

@inproceedings{GuagliardoLMMMPS25,
    author = {Paolo Guagliardo 
          and Leonid Libkin 
          and Victor Marsault 
          and Wim Martens 
          and Filip Murlak 
          and Liat Peterfreund 
          and Cristina Sirangelo},
    title = {Queries with External Predicates},
    year = {2025},
    booktitle = {ICDT},
    note = {To appear},
}

Distinct Shortest Walk Enumeration for RPQs

Joint work with Claire David, Nadime Francis.

In the proceedings of PODS, vol. 2, n°2. 2024.

@inproceedings{DavidFrancisMarsault2024,
  author  = {Claire David and Nadime Francis and Victor Marsault},
  title   = {Distinct Shortest Walk Enumeration for RPQs},
  year    = {2024},
  booktitle = {PODS},
  url     = {https://doi.org/10.1145/3651601},
  publisher = {ACM},
  volume = {2},
  number = {2},
}

Enumerating regular languages in radix order: Revisiting the Ackerman-Shallit algorithm

Joint work with Nadime Francis.

Technical Report. ArXiv:2310.13309. 2023.

@techreport{FrancisMarsault2023,
    author  = {Nadime Francis and Victor Marsault},
    title   = {Enumerating regular languages in radix order: Revisiting the Ackerman-Shallit algorithm},
    year    = {2023},
    note    = {ArXiv:2310.13309},
    url     = {https://arxiv.org/abs/2310.13309}
}

A Researcher’s Digest of GQL

Joint work with Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, Domagoj Vrgoč.

In the proceedings of ICDT, LIPIcs, vol. 255. Invited talk. 2023.

@inproceedings{FrancisEtAl2023a,
      author = {Nadime Francis and
                Amélie Gheerbrant and
                Paolo Guagliardo and
                Leonid Libkin and
                Victor Marsault and
                Wim Martens and
                Filip Murlak and
                Liat Peterfreund and
                Alexandra Rogova and
                Domagoj Vrgoč},
  title =	{A Researcher’s Digest of GQL},
  booktitle =	{ICDT},
  series =	{LIPIcs},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  month =       {03},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17743},
  note =        {Invited talk}
}

GPC: A Pattern Calculus for Property Graphs

Joint work with Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, Domagoj Vrgoč.

In the proceedings of PODS. 2023.

@inproceedings{FrancisEtAl2023b,
      title = {GPC: A Pattern Calculus for Property Graphs},
      author = {Nadime Francis and
                Amélie Gheerbrant and
                Paolo Guagliardo and
                Leonid Libkin and
                Victor Marsault and
                Wim Martens and
                Filip Murlak and
                Liat Peterfreund and
                Alexandra Rogova and
                Domagoj Vrgoč},
      year = {2023},
      booktitle = {Symposium on Principles of Database Systems (PODS)},
      publisher = {ACM},
      pages = {241–250},
      url = {https://doi.org/10.1145/3584372.3588662},
}

Run-Based Semantics for RPQs

Joint work with Claire David, Nadime Francis.

In the proceedings of KR. 2023.

@inproceedings{DavidFrancisMarsault2023,
    author  = {Claire David and Nadime Francis and Victor Marsault},
    title   = {Run-Based Semantics for RPQs},
    pages   = {178--187},
    year    = {2023},
    month   = {8},
    booktitle = {Principles of Knowledge Representation and Reasoning (KR'23)},
    url = {https://doi.org/10.24963/kr.2023/18},
}

PG-Schema: Schemas for Property Graphs

Joint work with Renzo Angles, Angela Bonifati, Stefania Dumbrava, George Fletcher, Alastair Green, Jan Hidders, Bei Li, Leonid Libkin, Wim Martens, Filip Murlak, Stefan Plantikow, Ognjen Savković, Michael Schmidt, Juan Sequeda, Sławek Staworko, Dominik Tomaszuk, Hannes Voigt, Domagoj Vrgoč, Mingxi Wu, Dušan Živković.

In the proceedings of SIGMOD, vol. 1, n°2. Industrial Track. 2023.

@inproceedings{AnglesEtAl2023,  
  author = {Renzo Angles and
            Angela Bonifati and
            Stefania Dumbrava and
            George Fletcher and
            Alastair Green and
            Jan Hidders and
            Bei Li and
            Leonid Libkin and
            Victor Marsault and
            Wim Martens and
            Filip Murlak and
            Stefan Plantikow and
            Ognjen Savković and
            Michael Schmidt and
            Juan Sequeda and
            Sławek Staworko and
            Dominik Tomaszuk and
            Hannes Voigt and
            Domagoj Vrgoč and
            Mingxi Wu and
            Dušan Živković},
  title = {PG-Schema: Schemas for Property Graphs},
  year = {2023},
  month = {6},
  booktitle = {Proceedings of the ACM on Management of Data (SIGMOD)},
  volume = {1},
  number = {2},
  publisher = {ACM},
  note = {Industrial Track},
}

Graph Pattern Matching in GQL and SQL/PGQ

Joint work with Alin Deutsch, Nadime Francis, Alastair Green, Keith Hare, Bei Li, Leonid Libkin, Tobias Lindaaker, Wim Martens, Jan Michels, Filip Murlak, Stefan Plantikow, Petra Selmer, Oskar van Rest, Hannes Voigt, Domagoj Vrgoč, Mingxi Wu, Fred Zemke.

In the proceedings of SIGMOD. Industrial track. 2022.

@inproceedings{DeutschEtAl2022,
      title = {Graph Pattern Matching in GQL and SQL/PGQ}, 
      author = {Alin Deutsch and 
                Nadime Francis and 
                Alastair Green and 
                Keith Hare and 
                Bei Li and 
                Leonid Libkin and 
                Tobias Lindaaker and 
                Victor Marsault and 
                Wim Martens and 
                Jan Michels and 
                Filip Murlak and 
                Stefan Plantikow and 
                Petra Selmer and 
                Oskar van Rest and 
                Hannes Voigt and 
                Domagoj Vrgoč  and 
                Mingxi Wu and 
                Fred Zemke},
      year = {2022},
      publisher = {ACM},
      pages        = {2246--2258},
      booktitle = {Conference on Management of Data (SIGMOD)},
      note = {Industrial track}
}

On p/q-recognisable sets

In Logical Methods in Computer Science, vol. 17, n°3. 2021.

@article{Marsault2021,
  author = {Victor Marsault},
  title = {On p/q-recognisable sets},
  journal = {Logical Methods in Computer Science},
  volume = {17},
  number = {3},
  year = {2021},
  doi = {10.46298/lmcs-17(3:12)2021},
}

Taking-and-merging games as rewrite games

Joint work with Eric Duchêne, Aline Parreau, Michel Rigo.

In Discrete Mathematics & Theoretical Computer Science, vol. 22, n°4. 2020.

@article{DucheneMarsaultParreauRigo2020a,
  author = {Eric Duch\^ene and Victor Marsault and Aline Parreau and Michel Rigo},
  title = {Taking-and-merging games as rewrite games},
  journal = {{Discrete Mathematics \& Theoretical Computer Science}},
  volume = {22},
  number = {4},
  year = {2020},
  url = {https://doi.org/10.23638/DMTCS-22-4-5}
  month = Sep,
}

Updating Graph Databases with Cypher

Joint work with Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Stefan Plantikow, Martin Schuster, Petra Selmer, Hannes Voigt.

In the proceedings of VLDB, vol. 12, n°12. 2019.

@inproceedings{GreenEtAl2019,
  author = {Alastair Green and Paolo Guagliardo and Leonid Libkin 
            and Tobias Lindaaker and Stefan Plantikow and Martin Schuster
            and Petra Selmer and Hannes Voigt },
  title = {Updating Graph Databases with Cypher},
  year = {2019},
  booktitle = {VLDB},
  volume = {12},
  number = {12},
}

An efficient algorithm to decide periodicity of b-recognisable sets using LSDF convention

In Logical Methods in Computer Science, vol. 15, n°3. 2019.

@article{Marsault2019a,
  title = {An efficient algorithm to decide periodicity of b-recognisable sets
  using LSDF convention},
  author = {Victor Marsault},
  url = {https://lmcs.episciences.org/5656},
  journal = {Logical Methods in Computer Science},
  volume = {15},
  number = {3},
  year = {2019},
  url = {https://dx.doi.org/10.23638/LMCS-15(3:8)2019},
  month = Jul,
}

Formal Semantics of the Language Cypher

Joint work with Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Stefan Plantikow, Mats Rydberg, Martin Schuster, Petra Selmer, Andrés Taylor.

Technical Report. Arxiv:1802.09984. 2018.

@techreport{FrancisEtAl2018b,
  author =   {Nadime Francis and
              Alastair Green and
              Paolo Guagliardo and
              Leonid Libkin and
              Tobias Lindaaker and
              Victor Marsault and
              Stefan Plantikow and
              Mats Rydberg and
              Martin Schuster and
              Petra Selmer and
              Andr\'es Taylor},
  title = {Formal Semantics of the Language Cypher},
  year  = {2018},
  note = {Arxiv:1802.09984},
}

Cypher: An Evolving Query Language for Property Graphs

Joint work with Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Stefan Plantikow, Mats Rydberg, Petra Selmer, Andrés Taylor.

In the proceedings of SIGMOD. 2018.

@inproceedings{FrancisEtAl2018,
  author = {Nadime Francis and Alastair Green and
            Paolo Guagliardo and Leonid Libkin and
            Tobias Lindaaker and Victor Marsault and
            Stefan Plantikow and Mats Rydberg and
            Petra Selmer and Andr\'es Taylor},
  title = {Cypher: An Evolving Query Language for Property Graphs},
  booktitle = {Proceedings of the 2018 International Conference
               on Management of Data},
  year  = {2018},
  isbn = {978-1-4503-4703-7},
  url = {http://doi.acm.org/10.1145/3183713.3190657},
  doi = {10.1145/3183713.3190657},
  acmid = {3190657},
  publisher = {ACM},
}

On subtrees of the representation tree in rational base numeration systems

Joint work with Shigeki Akiyama, Jacques Sakarovitch.

In Discrete Mathematics & Theoretical Computer Science, vol. 20, n°1. 2018.

@article{AkiyamaMarsaultSakarovitch2018,
  author = {Shigeki Akiyama and Victor Marsault and Jacques Sakarovitch},
  title = {On subtrees of the representation tree in rational base numeration
           systems},
  journal = {{Discrete Mathematics & Theoretical Computer Science}},
  volume = {20},
  number = {1},
  year = {2018},
}

An Efficient Algorithm to Decide Periodicity of b-Recognisable Sets Using MSDF Convention

Joint work with Bernard Boigelot, Isabelle Mainz, Michel Rigo.

In the proceedings of ICALP, Leibniz International Proceedings in Informatics, vol. 80. 2017.

@inproceedings{BoigelotEtAl2017,
  author =	{Bernard Boigelot and Isabelle Mainz and Victor Marsault and
                 Michel Rigo},
  title =	{An Efficient Algorithm to Decide Periodicity of b-Recognisable
                 Sets Using MSDF Convention},
  booktitle =	{44th International Colloquium on Automata, Languages, and
                 Programming (ICALP)},
  pages =	{118:1--118:14},
  series =	{Leibniz International Proceedings in Informatics},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  url= {http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.118},
}

Trees and languages with periodic signature

Joint work with Jacques Sakarovitch.

In Indagationes Mathematicae, vol. 28, n°1. Special Issue on Automatic Sequences, Number Theory, and Aperiodic Order. 2017.

@article{MarsaultSakarovitch2017,
  author = {Victor Marsault and Jacques Sakarovitch},
  title = {Trees and languages with periodic signature},
  journal = {Indagationes Mathematicae},
  volume = {28},
  number = {1},
  pages = {221 - 246},
  year = {2017},
  issn = {0019-3577},
  url = {http://dx.doi.org/10.1016/j.indag.2016.11.015},
  note = {Special Issue on Automatic Sequences, Number Theory, and Aperiodic Order}
}

The signature of rational languages

Joint work with Jacques Sakarovitch.

In Theoretical Computer Science, vol. 658, Part A. Formal Languages and Automata: Models, Methods and Application In honour of the 70th birthday of Antonio Restivo. 2017.

@article{MarsaultSakarovitch2017,
  title = {The signature of rational languages},
  journal = {Theoretical Computer Science},
  volume = {658, Part A},
  pages = {216 - 234},
  year = {2017},
  month = {1},
  note = {Formal Languages and Automata: Models, Methods
          and Application In honour of the 70th birthday
          of Antonio Restivo},
  issn = {0304-3975},
  url= {http://dx.doi.org/10.1016/j.tcs.2016.04.023},
  author = {Victor Marsault and Jacques Sakarovitch},
}

Énumération et numération

Ph.D. Thesis. In French. 2016.

@phdthesis{Marsault2016,
  author = {Victor Marsault},
  title = {{\'E}numeration et Num{\'e}ration},
  year = {2016},
  school = {T{\'e}l{\'e}com--ParisTech},
  language = {French},
}

Trees and Languages with Periodic Signature

Joint work with Jacques Sakarovitch.

In the proceedings of LATIN, Lecture Notes in Computer Science, vol. 9644. 2016.

@inproceedings{MarsaultSakarovitch2016a,
  author = {Victor Marsault and Jacques Sakarovitch},
  title = {Trees and Languages with Periodic Signature},
  booktitle = {Latin American Symposium of Theoretical Informatics},
  pages = {605--618},
  year = {2016},
  crossref = {LATIN2016},
  url = {http://dx.doi.org/10.1007/978-3-662-49529-2_45}
}
@proceedings{LATIN2016,
  editor = {Evangelos Kranakis and Gonzalo Navarro and Edgar Ch{\'{a}}vez},
  title = {{LATIN} 2016: Theoretical Informatics - 12th  Latin American
           Symposium, Ensenada, Mexico, Proceedings},
  booktitle = {LATIN},
  series = {Lecture Notes in Computer Science},
  volume = {9644},
  publisher = {Springer},
  year = {2016},
}

Surminimisation of Automata

In the proceedings of DLT, Lecture Notes in Computer Science, vol. 9168. 2015.

@inproceedings{Marsault2015,
  author = {Victor Marsault},
  title = {Surminimisation of Automata},
  booktitle = {Developments in Language Theory},
  pages = {352--363},
  year = {2015},
  crossref = {DLT2015},
  url = {http://dx.doi.org/10.1007/978-3-319-21500-6_28},
}
@proceedings{DLT2015,
  editor = {Igor Potapov},
  title = {Developments in Language Theory - 19th International Conference,
           {DLT}, Liverpool, UK, Proceedings},
  booktitle = {DLT},
  series = {Lecture Notes in Computer Science},
  volume = {9168},
  publisher = {Springer},
  year = {2015},
  isbn = {978-3-319-21499-3},
}

Breadth-First Serialisation of Trees and Rational Languages

Joint work with Jacques Sakarovitch.

In the proceedings of DLT, Lecture Notes in Computer Science, vol. 8633. 2014.

@inproceedings{MarsaultSakarovitch2014a,
  author = {Victor Marsault and Jacques Sakarovitch},
  title = {Breadth-First Serialisation of Trees and Rational Languages},
  booktitle = {Developments in Language Theory},
  pages = {252--259},
  year = {2014},
  crossref = {DLT2014},
  url = {http://dx.doi.org/10.1007/978-3-319-09698-8_22},
}
@proceedings{DLT2014,
  editor = {Arseny M. Shur and Mikhail V. Volkov},
  title = {Developments in Language Theory - 18th International Conference,
           {DLT} 2014, Ekaterinburg, Russia, August 26-29, 2014. Proceedings},
  booktitle = {DLT},
  series = {Lecture Notes in Computer Science},
  volume = {8633},
  publisher = {Springer},
  year = {2014},
  isbn = {978-3-319-09697-1},
}

Auto-similarity in Rational Base Number Systems

Joint work with Shigeki Akiyama, Jacques Sakarovitch.

In the proceedings of WORDS, Lecture Notes in Computer Science, vol. 8079. 2013.

@inproceedings{AkiyamaMarsaultSakarovitch2013,
  author = {Shigeki Akiyama and Victor Marsault and Jacques Sakarovitch},
  title = {Auto-similarity in Rational Base Number Systems},
  booktitle = {WORDS},
  year = {2013},
  pages = {34-45},
  crossref = {WORDS2013},
  url = {http://dx.doi.org/10.1007/978-3-642-40579-2_7},
}
@proceedings{WORDS2013,
  editor = {Juhani Karhum{\"a}ki and Arto Lepist{\"o} and Luca Q. Zamboni},
  title = {Combinatorics on Words - 9th International Conference on WORDS,
           Turku, Finland, September 16-20. Proceedings},
  booktitle = {WORDS},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  volume = {8079},
  year = {2013},
  isbn = {978-3-642-40578-5},
}

On Sets of Numbers Rationally Represented in a Rational Base Number System

Joint work with Jacques Sakarovitch.

In the proceedings of CAI, Lecture Notes in Computer Science, vol. 8080. 2013.

@inproceedings{MarsaultSakarovitch2013b,
  author = {Victor Marsault and Jacques Sakarovitch},
  title = {On Sets of Numbers Rationally Represented in a Rational Base Number
           System},
  booktitle = {CAI},
  year = {2013},
  pages = {89-100},
  crossref = {CAI2013},
  url = {http://dx.doi.org/10.1007/978-3-642-40663-8_10},
}
@proceedings{CAI2013,
  editor = {Traian Muntean and Dimitrios Poulakis and Robert Rolland},
  title = {Algebraic Informatics - 5th International Conference, CAI
           2013, Porquerolles, France, September 3-6, 2013. Proceedings},
  booktitle = {CAI},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  volume = {8080},
  year = {2013},
  isbn = {978-3-642-40662-1},
}

Ultimate Periodicity of b-Recognisable Sets: A Quasilinear Procedure

Joint work with Jacques Sakarovitch.

In the proceedings of DLT, Lecture Notes in Computer Science, vol. 7907. 2013.

@inproceedings{MarsaultSakarovitch2013a,
  author = {Victor Marsault and
            Jacques Sakarovitch},
  title = {Ultimate Periodicity of b-Recognisable Sets: A Quasilinear
           Procedure},
  booktitle = {Developments in Language Theory},
  year = {2013},
  pages = {362-373},
  crossref = {DLT2013},
  url = {http://dx.doi.org/10.1007/978-3-642-38771-5_32},
}
@proceedings{DLT2013,
  editor = {Marie-Pierre B{\'e}al and
            Olivier Carton},
  title = {Developments in Language Theory - 17th International Conference,
           DLT 2013, Marne-la-Vall{\'e}e, France, June 18-21, 2013. Proceedings},
  booktitle = {DLT},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  volume = {7907},
  year = {2013},
  isbn = {978-3-642-38770-8},
}

Last update : 2024.12.12

Professional Page of Victor Marsault