Publications
International Journals
- Minimization of visibly pushdown automata is NP-complete
Olivier Gauwin. Anca Muscholl. Michael Raskin.
Logical Methods in Computer Science, volume 16(1), pages . 2020.
[url] - Logical and Algebraic Characterizations of Rational Transductions
Emmanuel Filiot. Olivier Gauwin. Nathan Lhote.
Logical Methods in Computer Science
(extended version of the FSTTCS'16 paper and of the LICS'16 paper), volume 15(4), pages . 2019.
[url] - Streamability of nested word transductions
Emmanuel Filiot. Olivier Gauwin. Pierre-Alain Reynier. Frédéric Servais.
Logical Methods in Computer Science
(extended version of the FSTTCS'11 paper), volume 15(2), pages . 2019.
[url] - One-way definability of two-way word transducers
Félix Baschenis. Olivier Gauwin. Anca Muscholl. Gabriele Puppis.
Logical Methods in Computer Science
(extended version of the FSTTCS'15 paper and LICS'17 paper), volume 14(4), pages . 2018.
[url] - Early Nested Word Automata for XPath Query Answering on XML Streams
Denis Debarbieux. Olivier Gauwin. Joachim Niehren. Tom Sebastian. Mohamed Zergaoui.
Theoretical Computer Science
(extended version of the CIAA'13 paper), volume 578, pages 100-125. 2015.
[url] - Reasoning on BGP Routing Filters Using Tree Automata
Caroline Battaglia. Véronique Bruyère. Olivier Gauwin. Cristel Pelsser. Bruno Quoitin.
Computer Networks, volume 65, pages 232-254. 2014.
[url] - Tree Automata (book chapter)
Olivier Gauwin.
Handbook of Finite State Based Models and Applications (Chapman and Hall/CRC). 2012.
[url] - An aperiodicity problem for multiwords
Véronique Bruyère. Olivier Carton. Alexandre Decan. Olivier Gauwin. Jef Wijsen.
RAIRO - Theoretical Informatics and Applications
(long version of the JMIT paper), volume 46, pages 33-50. 2012.
[url] - Queries on XML Streams with Bounded Delay and Concurrency
Olivier Gauwin. Joachim Niehren. Sophie Tison.
Information and Computation
(long version of the LATA'09 paper)
, volume 209(3), pages 409-442. 2011.
[url] - Streaming Tree Automata
Olivier Gauwin. Joachim Niehren. Yves Roos.
Information Processing Letters, volume 109(1), pages 13-17. 2008.
[url] - Conciliation through Iterated Belief Merging
Olivier Gauwin. Sébastien Konieczny. Pierre Marquis.
Journal of Logic and Computation, volume 17(5), pages 909-937. 2007.
[url]
International Conferences
- On Canonical Models for Rational Functions over Infinite Words
Emmanuel Filiot. Olivier Gauwin. Nathan Lhote. Anca Muscholl.
In Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'18), volume 122 of LIPIcs, pages 30:1--30:17. 2018.
[url] - Untwisting two-way transducers in elementary time
Félix Baschenis. Olivier Gauwin. Anca Muscholl. Gabriele Puppis.
In Proceedings of the 32nd Annual (ACM/IEEE) Symposium on Logic in Computer Science (LICS'17), volume of LICS'17, pages 1--12. 2017.
[url] - Aperiodicity of rational functions is PSpace-complete
Emmanuel Filiot. Olivier Gauwin. Nathan Lhote.
In Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'16), volume 65 of LIPIcs, pages 13:1--13:15. 2016.
[url] - Minimizing resources of sweeping and streaming string transducers
Félix Baschenis. Olivier Gauwin. Anca Muscholl. Gabriele Puppis.
In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP'16), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 114:1--114:14. 2016.
[url] - First-order definability of rational transductions: An algebraic approach
Emmanuel Filiot. Olivier Gauwin. Nathan Lhote.
In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16), volume of LICS'16, pages 387--396. 2016.
[url] - One-way definability of sweeping transducers
Félix Baschenis. Olivier Gauwin. Anca Muscholl. Gabriele Puppis.
In Proceedings of the 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'15), volume 45 of LIPIcs, pages 178-191. 2015.
[url] - Right-universality of Visibly Pushdown Automata
Véronique Bruyère. Marc Ducobu. Olivier Gauwin.
In Proceedings of the 4th International Conference on Runtime Verification (RV'13), volume 8174 of Lecture Notes in Computer Science, pages 76-93. 2013.
[url] - From Two-Way to One-Way Finite State Transducers
Emmanuel Filiot. Olivier Gauwin. Pierre-Alain Reynier. Frédéric Servais.
Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'13), volume 0, pages 468-477. 2013.
[url] - Early Nested Word Automata for XPath Query Answering on XML Streams
Denis Debarbieux. Olivier Gauwin. Joachim Niehren. Tom Sebastian. Mohamed Zergaoui.
In Proceedings of the 18th International Conference on Implementation and Application of Automata (CIAA'13), volume 7982 of Lecture Notes in Computer Science, pages 292-305. 2013.
[url] - Visibly Pushdown Automata: Universality and Inclusion via Antichains
Véronique Bruyère. Marc Ducobu. Olivier Gauwin.
In Proceedings of the 7th International Conference on Language and Automata Theory and Applications (LATA'13) (see also the
extended version), volume 7810 of Lecture Notes in Computer Science, pages 190-201. 2013.
[url] - Streamability of Nested Word Transductions
Emmanuel Filiot. Olivier Gauwin. Pierre-Alain Reynier. Frédéric Servais.
In Proceedings of the 31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'11), volume 13 of Leibniz International Proceedings in Informatics (LIPIcs), pages 312-324. 2011.
[url] - Streamable Fragments of Forward XPath
Olivier Gauwin. Joachim Niehren.
In Proceedings of the 16th International Conference on Implementation and Application of Automata (CIAA'11, invited talk), volume 6807 of Lecture Notes in Computer Science, pages 3-15. 2011.
[url] - Efficient Enumeration for Conjunctive Queries over X-underbar Structures
Guillaume Bagan. Arnaud Durand. Emmanuel Filiot. Olivier Gauwin.
In Proceedings of the 19th EACSL Annual Conference on
Computer Science Logic (CSL'10), volume 6247 of Lecture Notes in Computer Science, pages 80-94. 2010.
- Earliest Query Answering for Deterministic Nested Word Automata
Olivier Gauwin. Joachim Niehren. Sophie Tison.
In Proceedings of the 17th International Symposium on
Fundamentals of Computation Theory (FCT'09), volume 5699 of Lecture Notes in Computer Science, pages 121-132. 2009.
[url] - Bounded Delay and Concurrency for Earliest Query Answering
Olivier Gauwin. Joachim Niehren. Sophie Tison.
In Proceedings of the 3rd International Conference on Language and Automata Theory and Applications (LATA'09), volume 5457 of Lecture Notes in Computer Science, pages 350-361. 2009.
[slides][url] - Conciliation and Consensus in Iterated Belief Merging
Olivier Gauwin. Sébastien Konieczny. Pierre Marquis.
In Proceedings of the 8th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU'05), volume 3571 of Lecture Notes in Computer Science, pages 514-526. 2005.
[url]
International Workshops
Thesis