Publications

  • 2020
  • 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.