• Home
• Members
• Meetings
• Publications
• Documents
• Tools
• Related projects
• Private Area

Publications

• 2020
  • Nicolas Baudru and Pierre-Alain Reynier. From Two-Way Transducers to Regular Function Expressions. IJFCS 2020.
  • L. Exibard, E. Filiot, P.-A. Reynier. On Computability of Data Word Functions Defined by Transducers. FoSSaCS 2020.
  • P. BarcelĂł, D. Figueira, G. Gottlob, A. Pieris. Semantic Optimization of Conjunctive Queries. Journal of the ACM. 2020.
  • N. Fijalkow, P. Gawrychowski, P. Ohlmann The complexity of mean payoff games using universal graphs. MFCS 2020.
  • D. Figueira, A. Majumdar, M. Praveen. Playing with repetitions in data words using energy games. Logical Methods in Computer Science - 16(3)
  • D. Figueira, S. Figueira, E. Pin Baque. Finite Controllability for Ontology-Mediated Query Answering of CRPQ. KR 2020.
  • D. Figueira, A. Godbole, S. Krishna, W. Martens, M. Niewerth, T. Trautner. Containment of Simple Regular Path Queries. KR 2020.
  • D. Figueira. Containment of UC2RPQ: the hard and easy cases. ICDT 2020.
• 2019
  • L. Exibard, E. Filiot, P.-A. Reynier. Synthesis of Data Word Transducers. CONCUR 2019.
  • Thomas Colcombet, JoĂ«l Ouaknine, Pavel Semukhin, James Worrell. On Reachability Problems for Low-Dimensional Matrix Semigroups. ICALP 2019.
  • D. Figueira, V. Ramanathan, P. Weil. The Quantifier Alternation Hierarchy of Synchronous Relations. MFCS 2019.
  • P.-A. Reynier, D. Villevalois. Sequentiality of String-to-Context Transducers. ICALP 2019.
  • E. Filiot, O. Gauwin, P.-A. Reynier and F. Servais. Streamability of nested words transductions. Logical Methods in Computer Science (LMCS), 2019.
  • Thomas Place, Marc Zeitoun, On all things star-free. ICALP 2019.
  • Thomas Place, Marc Zeitoun, Separation and covering for group-based concatenation hierarchies. LICS 2019.
  • Thomas Place, Marc Zeitoun, Generic results for concatenation hierarchies. Theory of Computing Systems (ToCS), 2019.
  • Thomas Place, Marc Zeitoun, Going Higher in First-Order Quantifier Alternation Hierarchies on Words, Journal of the ACM (JACM), 2019.
  • Jorge Almeida and Alfredo Costa and JosĂ©-CArlos Costa and Marc Zeitoun. The linear nature of pseudowords, Publicacions MatemĂ tiques, 2019.
  • P. BarcelĂł, D. Figueira, M. Romero. Boundedness of Conjunctive Regular Path Queries. ICALP 2019.
  • W. CzerwiĹ„ski, L. Daviaud, N. Fijalkow, M. JurdziĹ„ski, R. Lazić, and P. Parys Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games. SODA'2019
  • T. Colcombet and N. Fijalkow Universal Graphs and Good for Games Automata: New Tools for Infinite Duration Games, FoSSaCS'19
  • Antoine Amarilli, Pierre Bourhis, Stefan Mengel and Matthias Niewerth. Enumeration on Trees with Tractable Combined Complexity and Efficient Updates. PODS 2019
  • Antoine Amarilli, Pierre Bourhis, Stefan Mengel and Matthias Niewerth Constant-Delay Enumeration for Nondeterministic Document Spanners. ICDT 2019
  • M.E. Descotte, D. Figueira, S. Figueira. Closure properties of synchronized relations. STACS 2019.
• 2018
  • Olivier Carton and Maurice Pouzet. Simon's theorem for scattered words. DLT 2018, 182–193, Lecture Notes in Comput. Sci., 11088, Springer
  • Nicolas Baudru and Pierre-Alain Reynier. From Two-Way Transducers to Regular Function Expressions. DLT 2018.
  • Damien Busatto-Gaston, Benjamin Monmege and Pierre-Alain Reynier. Symbolic approximation of weighted timed games. FSTTCS 2018.
  • Luc Dartois, IsmaĂ«l Jecker and Pierre-Alain Reynier. Aperiodic String Transducers. International Journal of Foundations of Computer Science. 2018.
  • Emmanuel Filiot, Jean-Francois Raskin, Pierre-Alain Reynier, FrĂ©dĂ©ric Servais and Jean-Marc Talbot. Visibly Pushdown Transducers. Journal of Computer and System Sciences. 2018.
  • Sougata Bose, Anca Muscholl, Vincent Penelle, Gabriele Puppis. Origin-equivalence of two-way word transducers is in PSPACE. FSTTCS'18.
  • Olivier Carton, Thomas Colcombet, Gabriele Puppis. An algebraic approach to MSO-definability on countable linear orderings. In Journal of Symbolic Logic, Association for Symbolic Logic.
  • Thomas Place, Marc Zeitoun, The Covering Problem. Logical Methods in Computer Science 14 (3), 2018.
  • Thomas Place, Marc Zeitoun, Separating Without Any Ambiguity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP'18), pp. 137:1–137:14, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 2018.
  • Thomas Place, Marc Zeitoun, The complexity of separation for levels in concatenation hierarchies. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'18), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 2018.
  • Jorge Almeida, Alfredo Costa, Jose Carlos Costa, Marc Zeitoun, The linear nature of pseudowords. Publicacions MatemĂ tiques, Department of Mathematics of the Universitat Autònoma de Barcelona. 2018.
  • N. Fijalkow, B. Maubert, A. Murano, and S. Rubin, Quantifying bounds in Strategy Logic, CSL'18.
  • N. Fijalkow, M. R. Pedersen, G. Bacci, K. G. Larsen, and R. Mardare, Timed Comparisons of Semi-Markov Processes, LATA'18.
  • D. Figueira, Satisfiability of XPath on data trees, Siglog Newsletter.
  • P. Gastin and B. Monmege. A unifying survey on weighted logics and weighted automata. Soft Computing, 22(4):1047–1065, Feb. 2018. DOI = 10.1007/s00500-015-1952-6
  • N. Fijalkow, The State Complexity of Alternating Automata, LICS'18.
  • M. E. Descotte, D. Figueira, and G. Puppis, Resynchronizing Classes of Word Relations, ICALP'18.
  • J.-É. Pin and X. Soler-EscrivĂ , Languages and formations generated by D4 and Q8, submitted to TCS.
  • O. Carton, D. Perrin and J.-É. Pin, A survey on difference hierarchies of regular languages, Logical Methods in Computer Science (2017) March 29, 2018, Volume 14, Issue 1. DOI = {10.23638/LMCS-14(1:24)2018}
  • O. Carton, B. Guillon, and F. Reiter. Counter Machines and Distributed Automata: A Story about Exchanging Space and Time. AUTOMATA 2018 (to appear). arXiv:1804.03582
• 2017
  • O. Carton, L. Exibard, and O. Serre, Two-way two-tape automata, in DLT'2017, pp. 147-159, 2017.
  • O. Carton, O. Finkel, and D. Lecomte, Polishness of some topologies related to automata, in CSL 2017, vol. 82 of Leibniz International Proceedings in Informatics (LIPIcs), (Dagstuhl, Germany), pp. 22:1-22:16, 2017.
  • M. Cadilhac, O. Carton, and C. Paperman, Continuity and rational functions, in ICALP'2017, pp. 115:1-115:14, 2017.
  • Emmanuel Filiot and Pierre-Alain Reynier, Copyful Streaming String Transducers. RP 2017, Lecture Notes in Computer Science, volume 10506, pages 75-86. Springer.
  • Laure Daviaud, IsmaĂ«l Jecker, Pierre-Alain Reynier and Didier Villevalois, Degree of Sequentiality of Weighted Automata. FoSSaCS 2017, Lecture Notes in Computer Science, volume 10203, pages 215-230, Apr. 2017. Springer.
  • J.-É. Pin, Dual space of a lattice as the completion of a Pervin space, RAMICS 2017, Lecture Notes in Computer Science 10226 (2017) 24-40.
  • J. Almeida, Z. Ésik and J.-É. Pin, Commutative positive varieties of languages, Acta Cybernetica 23 (2017) 91-111. hal.archives-ouvertes.fr/hal-01614401
  • Meghyn Bienvenu, Pierre Bourhis, Marie-Laure Mugnier, Sophie Tison, Federico Ulliana, Ontology-Mediated Query Answering for Key-Value Stores. IJCAI 2017
  • Michael Benedikt, Pierre Bourhis and Michael Vanden Boom, Characterizing Definability in Decidable Fixpoint Logics. ICALP 2017 (Best Paper Award Track B)
  • Pierre Bourhis, Juan L. Reutter, Fernando Suárez, Domagoj Vrgoc, JSON: Data model, Query languages and Schema specification. PODS 2017: 123-135
  • T. Place and M. Zeitoun, Concatenation Hierarchies: New Bottle, Old Wine. In: Weil P. (eds) Computer Science – Theory and Applications. CSR 2017. Lecture Notes in Computer Science, vol 10304. Springer, 2017.
  • T. Place and M. Zeitoun, Separation for Dot-depth 2. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science. LICS 2017.
  • W. Czerwinski, W. Martens, L. van Rooijen, and M. Zeitoun, G. Zetzsche. A Characterization for Decidable Separability by Piecewise Testable Languages. Discrete Mathematics & Theoretical Computer Science, 2017.
  • J. Almeida, J. C. Costa and M. Zeitoun. Reducibility of Pointlike Problems. Semigroup Forum, 94(2):325–335, 2017. DOI 10.1007/s00233-015-9769-2.
  • T. Brihaye, G. Geeraerts, A. Haddad, and B. Monmege. Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games. Acta Informatica, 54(1):85–125, February 2017. DOI 10.1007/s00236-016-0276-z
  • P. Gallot, A. Muscholl, G. Puppis and S. Salvati. On the decomposition of finite-valued streaming string transducers. In Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
  • F. Reiter. Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment. ICALP 2017: 100:1-100:14. DOI 10.4230/LIPIcs.ICALP.2017.100
  • A. Kuusisto, F. Reiter. Emptiness Problems for Distributed Automata. GandALF 2017: 210-222. DOI 10.4204/EPTCS.256.15
  • T. Brihaye, G. Geeraerts, H.-M. Ho, and B. Monmege. Mightyl: A compositional translation from MITL to timed automata. CAV’17, volume 10426 of LNCS, pages 421–440, July 2017. Springer.
  • T. Brihaye, G. Geeraerts, H.-M. Ho, and B. Monmege. Timed-automata-based verification of MITL over signals. TIME’17, volume 90 of LIPIcs, pages 7:1–7:19, Oct. 2017.
  • D. Busatto-Gaston, B. Monmege, and P.-A. Reynier. Optimal reachability in divergent weighted timed games. In FoSSaCS’17, volume 10203 of LNCS, pages 162–178, Apr. 2017. Springer.
  • S. Haddad and B. Monmege. Interval iteration algorithm for MDPs and IMDPs. Theoretical Computer Science, Jan. 2017.
  • FĂ©lix Baschenis, Olivier Gauwin, Anca Muscholl and Gabriele Puppis. Untwisting two-way transducers in elementary time. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS'17.
  • Paul Gallot, Anca Muscholl, Gabriele Puppis, Sylvain Salvati. On decomposition of finite-valued streaming string transducers. STACS'17.
• 2016 (from october 1st).
  • F. Bassino, C. Nicaud, P. Weil. Generic properties of subgroups of free groups and of finite presentations, Contemporary Mathematics 677 (2016) 1-44. DOI 10.1090/conm/677/13619
  • E. Filiot, O. Gauwin, and N. Lhote. Aperiodicity of Rational Functions Is PSPACE-Complete. FSTTCS'16, volume 65 of LIPIcs, pages 13:1--13:15, Dec. 2016.