2015

S. Salvati, I. Walukiewicz,Using models to model-check recursive schemes. Logical Methods in Computer Science, to appear.

S. Salvati, I. Walukiewicz,Recursive Schemes, Krivine Machines, and Collapsible Pushdown Automata. Mathematical Structures in Computer Science, to appear.

S. Salvati, I. Walukiewicz, Typing weak MSOL properties. In FoSSACS'15, Lect. Notes Comp. Sci., Springer. To appear 2015.

J. Almeida, J. C. Costa and M. Zeitoun, McCammond’s normal forms for free aperiodic semigroups revisited. LMS Journal of Computation and Mathematics, 18 (1), pp. 130–147, Cambridge University Press, 2015.

T. Place, M. Zeitoun, Separation and the Successor Relation. In STACS'15, Lect. Notes Comp. Sci., Springer. To appear in 2015.

A. Manuel, A. Muscholl, G. Puppis Walking on Data Words, Theory of Computing Systems, pp. 1-29, Springer.

J. Almeida, A. Cano, O. Klima and J.-E. Pin, Fixed points of the lower set operator, to appear in Internat. J. Algebra Comput. (2015).

2014

Proceedings of FREC'14, final conference of project FREC, G. SĂ©nizergues, ed.

S. Salvati, I. Walukiewicz, Krivine machines and higher-order schemes, Inf. Compt. (239) 2014: 340-355.

T. Colcombet, N. Fijalkow, F.Horn, Playing Safe, FSTTCS 2014: 379-390.

S. Almagor, D. Kuperberg, O.Kupferman, Regular Sensing, FSTTCS 2014: 161-173.

N. Fijalkow, D. Kuperberg, ACME: Automata with Counters, Monoids and Equivalence. ATVA 2014: 163-167.

A. Blumensath, T. Colcombet, D. Kuperberg, P. Parys, M. Vanden Boom: Two-way cost automata and cost logics over infinite trees. CSL-LICS 2014: 16.

D. Kuperberg, Temporal Logic for Regular Cost Functions. Logical Methods in Computer Science 10(1), 2014.

A. Blumensath, O. Carton, T. Colcombet, Asymptotic Monadic Second-Order Logic. MFCS (1) 2014: 87-98

B. BĂ©rard and O. Carton, Channel synthesis revisited, in LATA, vol. 8370 of Lecture Notes in Computer Science, pp. 149-160, Springer, 2014.

A. Dreyfus, P.-C. Heam, O. Kouchnarenko, A random testing approach using pushdown automata, Spftware: testing, verification and reliability, DOI: 10.1002/stvr.1526, To appear.

T. Place and M. Zeitoun, Going higher in the First-order Quantifier Alternation Hierarchy on Words. In ICALP'14, pp. 342–353, Springer. 2014.

S. Salvati and I. Walukiewicz Simply typed fixpoint calculus and collapsible pushdown automata, to appear in Mathematical Structures in Computer Science.

M. Gehrke, A. Krebs, and J.-E. Pin,  From ultrafilters on words to the expressive power of a fragment of logic, Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science 8614, (2014), 138-149.

T. Place and M. Zeitoun, Separating Regular Languages with First-Order Logic. In CSL-LICS'14, pp. 75:1–75:10, ACM. 2014.

B. Bollig, P. Gastin, B. Monmege, M. Zeitoun, Logical Characterization of Weighted Pebble Walking Automata. In CSL-LICS'14, pp. 19:1–19:10, ACM. 2014.

T. Place, L. van Rooijen and M. Zeitoun, On Separation by Locally Testable and Locally Threshold Testable Languages. Logical Methods in Computer Science 10 (3:24), pp. 1–28, 2014.

J. Almeida, J. C. Costa, and M. Zeitoun. Iterated periodicity over finite aperiodic semigroups. In European J. Combin. 37 (2014) 115–149.

Benedikt Bollig, Paul Gastin, Benjamin Monmege and Marc Zeitoun, Pebble Weighted Automata and Weighted Logics, ACM Transactions on Computational Logic 15 (2), pp. 15:1–15:35, 2014.

T. Colcombet, C. Ley, and G. Puppis. Logics with Rigidly Guarded Data Tests. http://arxiv.org/abs/1410.2022, 2014.

M. Benedikt, G. Puppis, and C. Riveros. The Per-character Cost of Repairing Word Languages. Theoretical Computer Science, pp. 38-67, 2014.

J. Almeida, J. C. Costa and M. Zeitoun, Closures of Regular Languages for Profinite Topologies. Semigroup Forum 89 (1), pp. 20–40, 2014.

A. Carayol, A. Haddad, Olivier Serre: Randomization in Automata on Infinite Trees. ACM Trans. Comput. Log. 15(3): 24, 2014.

J.-E. Pin and P.V. Silva, A noncommutative extension of Mahler’s theorem on interpolation series, European J. Combin. 36 (2014), 564–578.

Benedikt Bollig, Aiswarya Cyriac, Paul Gastin, Marc Zeitoun, Temporal Logics for Concurrent Recursive Programs: Satisfiability and Model Checking, Journal of Applied Logic, To appear.

N. Fijalkow and C. Paperman, Monadic Second-Order Logic with Arbitrary Monadic Predicates, Proc. of MFCS (2014). Part I, 279–290

P. Weil. From algebra to logic : there and back again - the story of a hierarchy, Developments in Language Theory, DLT 2014, Lecture Notes in Computer Science 8633 (2014), pp. 275-278.

F. Bassino, C. Nicaud, P. Weil. Genericity of Whitehead minimality, Journal of Group Theory, to appear.

H. Straubing, P. Weil. Varieties, in Handbook of Automata Theory, to appear.

D. Coumans, M. Gehrke, and L. van Rooijen, Relational semantics for full linear logic, Journal of Applied Logic 12 (1) 2014, 50-66, http://dx.doi.org/10.1016/j.jal.2013.07.005

M. Gehrke, S. J. van Gool. Distributive Envelopes and Topological Duality for Lattices via Canonical Extensions, Order 31 (3)2014, 435-461. http://dx.doi.org/10.1007/s11083-013-9311-7

M. Gehrke. Canonical extensions, Esakia spaces, and universal models. In G. Bezhanishvili, editor. Leo Esakia on duality in modal and intuitionistic logic, volume 4 of Outstanding contributions to logic. Springer, 2014, pages 9-41.

M. Gehrke, S. J. van Gool, and V. Marra. Sheaf representations of MV-algebras and lattice-ordered abelian groups via duality. J. Algebra, 417:290-332, 2014.

2013

B. Aminof, A. Legay, A. Murano, Olivier Serre, M.Y. Vardi: Pushdown module checking with imperfect information. Inf. Comput. 223: 1-17, 2013.

U. Boker, D. Kuperberg, O. Kupferman, M. Skrzypczak: Nondeterminism in the Presence of a Diverse or Unknown Future. ICALP (2) 2013: 89-100.

C. Broadbent, A. Carayol, M. Hague and Olivier Serre. C-SHORe: a collapsible approach to higher-order verification, In proceedings of ICFP 2013: 13-24.

A. Dreyfus, P.-C. Heam, O. Kouchnarenko,Enhancing Approximations for Regular Reachability Analysis, CIAA 2013, LNCS 7982, pages 331-339.

A. Cano, G. Guaiana and J.-E. Pin, Closure of regular languages under semi-commutations, Information and Computation 230, (2013), 76-96.

N. Fijalkow, S. Pinchinat, O. Serre, Emptiness Of Alternating Tree Automata Using Games With Imperfect Information, FSTTCS 2013: 299-311.

J.-E. Pin, An explicit formula for the intersection of two polynomials of regular languages, Developments in Language Theory, - 17th International Conference, DLT 2013, Lecture Notes in Computer Science 7907, Springer Verlag, (2013), 31-45.

S. Salvati and I. Walukiewicz, Evaluation is MSOL compatible, FSTTCS 2013. DOI 0.4230/LIPIcs.FSTTCS.2013.103

T. Place, L. van Rooijen and M. Zeitoun, Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages, FSTTCS'13.

P. Henry and G. SĂ©nizergues, LALBLC, a program testing the equivalence of dpda’s.CIAA'2013.

A. Milchior, Undecidability of satisfiability of expansion of FO[<] with a Semilinear Non Regular Predicate over words. CIE2013

J. Ferté and N. Marin and G. Sénizergues, Word-mappings of level 2. TOCS, 2013.

T. Place, L. van Rooijen and M. Zeitoun, Separating regular languages by piecewise testable and unambiguous languages, MFCS'13.

L. van Rooijen and M. Zeitoun, The separation problem for regular languages by piecewise testable languages, research report.

L. Clemente and R. Mayr, Advanced Automata Minimization. POPL 2013.

S. Salvati and I. Walukiewicz, Using models to model-check recursive schemes. TLCA 2013.

M. Benedikt, G. Puppis, and C. Riveros. Bounded Repairability of Word Languages. Journal of Computer and System Sciences, pp. 1302-1321, 2013.

A. Manuel, A. Muscholl, and G. Puppis. Walking on Data Words. CSR, pp. 64-75, 2013.

P. Bourhis, G. Puppis, and C. Riveros. Which DTDs are Streaming Bounded Repairable? ICDT, pp. 57-68, 2013.

T. Colcombet, C. Löding, D. Kuperberg, and M. V. Boom, Deciding the weak definability of Büchi definable tree languages, CSL, pp. 215-230, 2013.

T. Colcombet, Regular cost functions, part I: logic and algebra over words, Logical Methods in Computer Science, vol. 9, no. 3, p. 47, 2013.

T. Colcombet, Composition with algebra in the background, in CSR, 2013, pp. 391-404.

T. Colcombet, Cost functions with several orders of magnitudes and the use of relative internal set theory, LICS, 2013.

A. Ballester-Bolinches, J.-É. Pin and X. Soler-Escrivà, Languages associated with saturated formations of groups, (2013), Forum Mathematicum, to appear, ISSN (Online) 1435-5337, ISSN (Print) 0933-7741.

L. Dartois and Ch. Paperman. Two-variable first order logic with modular predicates over words, In proceedings of STACS 2013, p 329-340.

M. Gehrke, R. Jansana and A. Palmigiano, Δ1-completions of a Poset. Order 30(1): 39-64 (2013).

T. Colcombet and L. Daviaud, Approximate comparison of distance automata, in STACS (N. Portier and T. Wilke, eds.), vol. 20, pp. 574-585, Schloss Dagstuhl - Leibniz-Zentrum fĂĽr Informatik, 2013.

J.-M. Couvreur, D. Poitrenaud, P. Weil. Branching processes for general Petri nets, Fundamenta Informaticæ 120 (2013), pp. 31-58.

F. Bassino, C. Nicaud, P. Weil. Statistical properties of subgroups of free groups, Random Structures and Algorithms 42 (2013), pp. 349-373.

A. Bauer, K. Cvetko-Vah, M. Gehrke, S. van Gool, and Ganna Kudryatseva. A non-commutative Priestley duality, Topology and its Applications 160 (12) (2013), 1423-1438.

2012

M. Bojańczyk and T. Place, Regular Languages of Infinite Trees that are Boolean Combination of Open Sets. ICALP (2) 2012: p.104-115

G. Puppis, C. Riveros, and S. Staworko. Bounded Repairability for Regular Tree Languages. ICDT 2012: pp. 155-168.

T. Colcombet, Forms of determinism for automata (invited talk), in STACS (C. DĂĽrr and T. Wilke, eds.), vol. 14 of LIPIcs, pp. 1-23, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012.

D. Kuperberg, Michael Vanden Boom: On the Expressive Power of Cost Logics over Infinite Words. ICALP (2) 2012: p.287-298

N. Fijalkow and M. Zimmermann. Cost-parity and cost-Streett games, In proceedings of FSTTCS 2012 (Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan editors), pp.124-135, LIPIcs Volume 18.

P. Parys and I. Walukiewicz Weak Alternating Timed Automata, Logical Methods in Computer Science 8(3), 2012.

M. Bojanczyk, H. Straubing and I. Walukiewicz Wreath Products of Forest Algebras, with Applications to Tree Logics, Logical Methods in Computer Science 8(3), 2012.

B. Srivathsan and I. Walukiewicz An alternate proof of Statman’s finite completeness theorem, Information Processing Letters, Volume 112, Issues 14-15 pp.612-616, 2012

I. Walukiewicz Simple Models for Recursive Schemes. MFCS 2012 LNCS 7464 pp. 49-60

S. Salvati, I. Walukiewicz: Recursive Schemes, Krivine Machines, and Collapsible Pushdown Automata. RP 2012: LNCS 7550 pp.6-20

V. Diekert, M. Kufleitner. Bounded synchronization delay in omega-rational expressions. In Proc. CSR 2012, E. Hirsch, J. Karhumäki, A. Lepistö, M. Prilutskii (Eds.), Lect. Notes Comp. Sci. 7353, pp. 89-98, Springer, 2012.

R. Bonnet, A. Finkel, J. Leroux, and M. Zeitoun. Model Checking Vector Addition Systems with one zero-test. In Logical Methods in Computer Science 8 (2012), pp. 1–25.

B. Bollig, P. Gastin, B. Monmege and M. Zeitoun. A Probabilistic Kleene Theorem. In Proc. of the 10th Symp. on Automated Technology for Verification and Analysis, ATVA'12, Supratik Chakraborty and Madhavan Mukund (Eds.), Lect. Notes Comp. Sci., pp. 400–415. Springer, 2012.

P.-C. HĂ©am, V. Hugot, O. Kouchnarenko. On Positive TAGED with a Bounded Number of Constraints. In proceedings of CIAA'12, LNCS 7381, pp 329-336.

P.-C. HĂ©am, V. Hugot, O. Kouchnarenko. From Linear Temporal Logic Properties to Rewrite Propositions. In proceedings of IJCAR'12. LNCS 7364, pp 316-331

P.-C. HĂ©am, V. Hugot, O. Kouchnarenko. Loops and Overloops for Tree Walking Automata, Theoretical Computer Science 450 (2012), 43-53.

J.-E. Pin, Equational descriptions of languages, Int. J. Found. Comput. S. 23, (2012), 1227–1240.

A. Ballester-Bolinches, J.-E. Pin and X. Soler-EscrivĂ , http://www.liafa.univ-paris-diderot.fr/~jep/PDF/Formations.pdf ! Formations of finite monoids and formal languages: Eilenberg’s variety theorem revisited, (2012), Forum Mathematicum, ISSN (Online) 1435-5337, ISSN (Print) 0933-7741, DOI: 10.1515/forum-2012-0055, June 2012.

A. Cano and J.-E. Pin, Upper set monoids and length preserving morphisms, Journal of Pure and Applied Algebra, (2012), 1178-1183.

C. Broadbent, A. Carayol, M. Hague and Olivier Serre. A Saturation Method for Collapsible Pushdown Systems, In proceedings of ICALP(2) 2012: 165-176.

A. Carayol and O. Serre. Collapsible Pushdown Automata and Labeled Recursion Schemes: Equivalence, Safety and Effective Selection, In proceedings of LICS 2012: 165-174.

A. Chernilovskaya, M. Gehrke, Lorijn van Rooijen, Generalized Kripke semantics for the Lambek-Grishin calculus, Logic Journal of IGPL 2012. doi: 10.1093/jigpal/jzr051

V. Diekert, M. Kufleitner, Pascal Weil. Star-Free Languages are Church-Rosser Congruential, Theoretical Computer Science 454, 2012, 129-135.

N. Fijalkow, Hugo Gimbert and Youssouf Oualhadj. Deciding the Value 1 Problem for Probabilistic Leaktight Automata, In proceedings of LICS 2012: pp. 295-304.

M. Kufleitner, P. Weil. The FO2 alternation hierarchy is decidable. Proceedings of Computer Science Logic (CSL 2012), Leibniz International Proceedings in Informatics (LIPIcs) 16, 2012, pp. 426-439.

M. Kufleitner, P. Weil. On logical hierarchies within FO2-definable languages, Logical Methods in Computer Science 8 (3:11) (2012) pp. 1-30

S. Salvati, G. Manzonetto, M. Gehrke, Henk Barendregt. Urzyczyn and Loader are Logically Related, In proceedings of ICALP(2) 2012, pp. 364-376.

H. Straubing, P. Weil. An introduction to finite automata and their connection to logic, in Modern applications of automata theory (D. D'Souza, Priti Shankar eds), IISc Research Monographs 2, World Scientific (2012), pp. 3-43.

F. Herbreteau, B. Srivathsan, I. Walukiewicz. Better abstractions for timed automata, in Proceedings of IEEE LICS, 2012, pp. 375-384.

F. Herbreteau, B. Srivathsan, I. Walukiewicz. Efficient emptiness check for timed BĂĽchi automata. Formal Methods in System Design 40(2): 122-146 (2012)

O. Carton. Two-Way Transducers with a Two-Way Output Tape. Developments in Language Theory 2012: 263-272

V. Bruyère, O. Carton, A. Decan, O. Gauwin, Jef Wijsen. An aperiodicity problem for multiwords. RAIRO - Theor. Inf. and Applic. 46(1): 33-50 (2012)

2011

T. Colcombet, C. Ley, and G. Puppis, On the use of guards for logics with data, in MFCS, vol. 6907 of Lecture Notes in Comput. Sci., pp. 243-255, Springer, 2011.

T. Colcombet Green’s Relations and Their Use in Automata Theory. LATA 2011: 1-21.

M. Gehrke, Duality and Recognition. MFCS 2011: 3-18.

N. Bezhanishvili and M. Gehrke, Finitely generated free Heyting algebras via Birkhoff duality and coalgebra. Logical Methods in Computer Science 7(2)(2011).

D. Kuperberg and M. Vanden Boom. Quasi-Weak Cost Automata: A New Variant of Weakness, in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), pages 66-77, Schloss Dagstuhl-Leibniz-Zentrum fĂĽr Informatik, 2011.

Denis Kuperberg: Linear temporal logic for regular cost functions. STACS 2011: p.627-636

J.-E. Pin and P.V. Silva, On profinite uniform structures defined by varieties of finite monoids, International Journal of Algebra and Computation, 21, (2011), 295-314.

B. Bollig, A. Cyriac, P. Gastin, M. Zeitoun. Temporal Logics for Concurrent Recursive Programs: Satisfiability and Model Checking, In Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS'11), Warsaw, Poland, August 2011, LNCS 6907, pages 132-144. Springer.

S. Salvati, I. Walukiewicz. Krivine machines and higher-order schemes, in ICALP (2), Lecture Notes in Computer Science 6756 (Springer 2011), pp 162-173, 2011.

P. Bourreau, S. Salvati. Game Semantics and Uniqueness of Type Inhabitance in the Simply-Typed lambda-Calculus, in TLCA, Lecture Notes in Computer Science 6690 (Springer 2011), pp 61-75, 2011.

J.-M. Couvreur, D. Poitrenaud, P. Weil. Unfoldings for general Petri nets, Applications and Theory of Petri Nets 2011, Lecture Notes in Computer Science 6709 (Springer, 2011), pp. 129-148. DOI:10.1007/978-3-642-21834-7_8.

J.-E. Pin, Theme and variations on the concatenation product, CAI 2011, LNCS 6742, Springer Verlag (2011), 44-64.

P.-C. HĂ©am, V. Hugot, O. Kouchnarenko. Loops and Overloops for Tree Walking Automata, International Conference on Implementation and Application of Automata 2011, Lecture Notes in Computer Sciences 6807(Springer, 2011), pp. 166-177. DOI:10.1007/978-3-642-22256-6_16.

P.-C. HĂ©am, C. Masson. A Random Testing Approach Using Pushdown Automata, Tests and Proofs 2011, Lecture Notes in Computer Science 6706 (Springer, 2011), pp. 119-133. DOI:10.1007/978-3-642-21768-5_10.

P.-C. HĂ©am. On the complexity of computing the profinite closure of a rational language, Theoretical Computer Science, 412(41), pp 5808-5813 (2011). DOI:0.1016/j.tcs.2011.06.022

A. Carayol, A. Haddad and Olivier Serre. Qualitative Tree Languages, In proceedings of LICS 2011, pp 13-22, 2011

A. Bès, O. Carton. Algebraic Characterization of FO for Scattered Linear Orderings. CSL 2011: p.67-81

O. Carton, T. Colcombet, Gabriele Puppis. Regular Languages of Words over Countable Linear Orderings. ICALP (2) 2011: p.125-136

F. Herbreteau, B. Srivathsan. Coarse abstractions make Zeno behaviours difficult to detect. Proceedings of CONCUR, LNCS 6901, pages 92-107, 2011.

F. Herbreteau, D. Kini, B. Srivathsan, I. Walukiewicz. Using non-convex approximations for efficient analysis of timed automata. Proceedings of FSTTCS 2011: 78-89

2010

Thomas Colcombet, Denis Kuperberg, Sylvain Lombardy. Regular Temporal Cost Functions. ICALP (2) 2010: P.563-574

R. Bonnet, A. Finkel, J. Leroux, M. Zeitoun: Place-Boundedness for Vector Addition Systems with one zero-test., in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), pages 192-203, Schloss Dagstuhl-Leibniz-Zentrum fĂĽr Informatik, 2010.