Publications

2024

  1. Jean Goubault-Larrecq, Maurice Pouzet. A Few Characterizations of Topological Spaces with No Infinite Discrete Subspace. Topology and its Applications, 2024, 341, pp.108733. ⟨10.1016/j.topol.2023.108733⟩. 〈hal〉.

2023

  1. Wojciech Czerwiński, Ismaël Jecker, Sławomir Lasota, Jérôme Leroux, Łukasz Orlikowski. New Lower Bounds for Reachability in Vector Addition Systems. FSTTCS, Dec 2023, Telangana, India. pp.35:1--35:22, ⟨10.4230/LIPICS.FSTTCS.2023.35⟩. 〈hal〉.
  2. Isa Vialard. On the width of the cartesian product of ordinals. 2023. 〈hal〉.
  3. Petr Jančar, Jérôme Leroux. The Semilinear Home-Space Problem Is Ackermann-Complete for Petri Nets. 34th International Conference on Concurrency Theory, {CONCUR} 2023, Sep 2023, Antwerp, Belgium. pp.36:1--36:17, ⟨10.4230/LIPICS.CONCUR.2023.36⟩. 〈hal〉.
  4. Alain Finkel, Serge Haddad, Lina Ye. About Decisiveness of Dynamic Probabilistic Models. the 34th International Conference on Concurrency Theory, Sep 2023, Gif-sur-Yvette, France. ⟨10.4230/LIPICS.CONCUR.2023.14⟩. 〈hal〉.
  5. Philipp Czerner, Javier Esparza, Jérôme Leroux. Lower bounds on the state complexity of population protocols. Distributed Computing, 2023, 36 (3), pp.209-218. ⟨10.1007/s00446-023-00450-4⟩. 〈hal〉.
  6. Isa Vialard. Ordinal measures of the set of finite multisets. MFCS 2023, Aug 2023, Bordeaux, France. ⟨10.4230/LIPIcs⟩. 〈hal〉.
  7. Aliaume Lopez. Fixed Points and Noetherian Topologies. FoSSaCS, Apr 2023, Paris, France. pp.456-476, ⟨10.1007/978-3-031-30829-1_22⟩. 〈hal〉.
  8. Jean Goubault-Larrecq, Bastien Laboureix. Statures and Sobrification Ranks of Noetherian Spaces. Houston Journal of Mathematics, In press, 49 (1), pp.1-76. ⟨10.48550/arXiv.2112.06828⟩. 〈hal〉.
  9. Jean Goubault-Larrecq, Simon Halfon, Aliaume Lopez. Infinitary Noetherian Constructions II. Transfinite Words and the Regular Subword Topology. Colloquium Mathematicum, 2023, 173 (2), pp.227-250. ⟨10.4064/cm8793-3-2023⟩. 〈hal〉.

2022

  1. Jérôme Leroux. State Complexity of Protocols with Leaders. PODC '22: ACM Symposium on Principles of Distributed Computing, Jul 2022, Salerno, Italy. pp.257-264, ⟨10.1145/3519270.3538421⟩. 〈hal〉.
  2. Benedikt Bollig, Alain Finkel, Amrita Suresh. Branch-Well-Structured Transition Systems and Extensions. 42nd International Conference on Formal Techniques for Distributed Objects, Components, and Systems (FORTE 2022), Jun 2022, Lucca, Italy. pp.50-66, ⟨10.1007/978-3-031-08679-3_4⟩. 〈hal〉.
  3. Jérôme Leroux. The Reachability Problem for Petri Nets is Not Primitive Recursive. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), Feb 2022, Denver, France. pp.1241-1252, ⟨10.1109/FOCS52979.2021.00121⟩. 〈hal〉.
  4. Alain Finkel, Serge Haddad, Igor Khmelnitsky. Coverability, Termination, and Finiteness in Recursive Petri Nets. Fundamenta Informaticae, 2022, 183, pp.33 - 66. ⟨10.3233/fi-2021-2081⟩. 〈hal〉.
  5. Jean Goubault-Larrecq. Infinitary Noetherian Constructions I. Infinite Words. Colloquium Mathematicum, 2022, 168, pp.257-286. ⟨10.4064/cm8077-4-2021⟩. 〈hal〉.

2021

  1. Benedikt Bollig, Cinzia Di Giusto, Alain Finkel, Laetitia Laversa, Etienne Lozes, Amrita Suresh. A Unifying Framework for Deciding Synchronizability. CONCUR 2021 - 32nd International Conference on Concurrency Theory, Aug 2021, Paris, France. pp.1-33. 〈hal〉.
  2. Jérôme Leroux. Flat Petri Nets (Invited Talk). Application and Theory of Petri Nets and Concurrency - 42nd International Conference, {PETRI} {NETS} 2021, Jun 2021, Virtual Event, France. ⟨10.1007/978-3-030-76983-3_2⟩. 〈hal〉.
  3. Philippe Schnoebelen. On flat lossy channel machines. 29th EACSL Conference on Computer Science Logic, Jan 2021, Ljubljana, Slovenia. ⟨10.4230/LIPIcs.CSL.2021.37⟩. 〈hal〉.
  4. Matthias Englert, Piotr Hofman, Sławomir Lasota, Ranko Lazić, Jérôme Leroux, Juliusz Straszyński. A lower bound for the coverability problem in acyclic pushdown VAS. Information Processing Letters, 2021, 167, pp.106079. ⟨10.1016/j.ipl.2020.106079⟩. 〈hal〉.
  5. Alain Finkel, Serge Haddad, Igor Khmelnitsky. Commodification of accelerations for the Karp and Miller Construction.. Discrete Event Dynamic Systems, 2021, 31 (2), pp.251-270. 〈hal〉.
  6. Michael Blondin, Matthias Englert, Alain Finkel, Stefan Göller, Christoph Haase, Ranko Lazić, Pierre Mckenzie, Patrick Totzke. The Reachability Problem for Two-Dimensional Vector Addition Systems with States. Journal of the ACM (JACM), 2021, 68 (5), pp.1-43. ⟨10.1145/3464794⟩. 〈hal〉.
  7. Sylvain Schmitz. Branching in Well-Structured Transition Systems (Invited Talk). 29th EACSL Annual Conference on Computer Science Logic (CSL 2021), 2021, Ljubljana, Slovenia. pp.3:1--3:3, ⟨10.4230/LIPIcs.CSL.2021.3⟩. 〈hal〉.
  8. Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić, Jérôme Leroux, Filip Mazowiecki. The Reachability Problem for Petri Nets Is Not Elementary. Journal of the ACM (JACM), 2021, 68 (1), pp.7. ⟨10.1145/3422822⟩. 〈hal〉.

2020

  1. Giannis Nikolentzos, George Dasoulas, Michalis Vazirgiannis. k-hop graph neural networks. Neural Networks, 2020, 130, pp.195-205. ⟨10.1016/j.neunet.2020.07.008⟩. 〈hal〉.
  2. Jérôme Leroux, Grégoire Sutre. Reachability in Two-Dimensional Vector Addition Systems with States: One Test Is for Free. CONCUR 2020 - 31st International Conference on Concurrency Theory, Sep 2020, Vienne, Austria. pp.37:1-37:17, ⟨10.4230/LIPIcs.CONCUR.2020.37⟩. 〈hal〉.
  3. Benedikt Bollig, Alain Finkel, Amrita Suresh. Bounded Reachability Problems are Decidable in FIFO Machines. 31st International Conference on Concurrency Theory (CONCUR 2020), Sep 2020, Vienna, Austria. 〈hal〉.
  4. Wojciech Czerwiński, Diego Figueira, Piotr Hofman. Universality Problem for Unambiguous VASS. International Conference on Concurrency Theory (CONCUR), Sep 2020, Vienna, Austria. pp.36:1-36:15, ⟨10.4230/LIPIcs.CONCUR.2020.36⟩. 〈hal〉.
  5. Wojciech Czerwiński, Slawomir Lasota, Ranko Lazić, Jérôme Leroux, Filip Mazowiecki. Reachability in Fixed Dimension Vector Addition Systems with States. 31st International Conference on Concurrency Theory, {CONCUR} 2020, September 1-4, 2020, Vienna, Austria (Virtual Conference), Sep 2020, Vienna, Austria. pp.48:1--48:21. 〈hal〉.
  6. Alain Finkel, Jean Goubault-Larrecq. Forward analysis for WSTS, part I: completions. Mathematical Structures in Computer Science, 2020, 30 (7), pp.752-832. ⟨10.1017/S0960129520000195⟩. 〈hal〉.
  7. Antonín Kučera, Jérôme Leroux, Dominik Velan. Efficient Analysis of VASS Termination Complexity. LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Jul 2020, Saarbrücken, Germany. pp.676-688. 〈hal〉.
  8. Jérôme Leroux. When Reachability Meets Grzegorczyk. LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Jul 2020, Saarbrücken, Germany. pp.1-6. 〈hal〉.
  9. Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, Florian Sikora. Parameterized Orientable Deletion. Algorithmica, 2020, 82 (7), pp.1909-1938. ⟨10.1007/s00453-020-00679-6⟩. 〈hal〉.
  10. Michael Blondin, Alain Finkel, Jean Goubault-Larrecq. Forward Analysis for WSTS, Part III: Karp-Miller Trees. Logical Methods in Computer Science, 2020, 16 (2). 〈hal〉.
  11. Alain Finkel. From Well Structured Transition Systems to Program Verification. 8th International Workshop on Verification and Program Transformation, Apr 2020, Dublin (Irlande), Ireland. pp.44-49, ⟨10.4204/EPTCS.320.3⟩. 〈hal〉.
  12. Alain Finkel, Serge Haddad, Igor Khmelnitsky. Minimal Coverability Tree Construction Made Complete and Efficient. FoSSaCS 2020 - 23rd International Conference on Foundations of Software Science and Computation Structures, Apr 2020, Dublin, Ireland. 〈hal〉.
  13. Sébastien Labbé, Vincent Penelle, Marni Mishna, Fredrik Johansson, Marthe Bonamy, Jérôme Leroux, Xavier Goaoc, Irena Penev, Sylvain Schmitz, Xavier Caruso. Informatique Mathématique Une photographie en 2020. 2020. 〈hal〉.
  14. Jean Goubault-Larrecq, Simon Halfon, Prateek Karandikar, K. Narayan Kumar, Philippe Schnoebelen. The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings. Well Quasi-Orders in Computation, Logic, Language and Reasoning, 53, Springer, pp.55-105, 2020, Trends in Logic, 978-3-030-30228-3. ⟨10.1007/978-3-030-30229-0_3⟩. 〈hal〉.
  15. Diego Figueira, Anirban Majumdar, M. Praveen. Playing with repetitions in data words using energy games. Logical Methods in Computer Science, 2020, 16 (3), pp.1. 〈hal〉.
  16. Alain Finkel, M. Praveen. Verification of Flat FIFO Systems. Logical Methods in Computer Science, 2020, ⟨10.23638/LMCS-16(4:4)2020⟩. 〈hal〉.

2019

  1. Jérôme Leroux, M. Praveen, Philippe Schnoebelen, Grégoire Sutre. On Functions Weakly Computable by Pushdown Petri Nets and Related Systems. Logical Methods in Computer Science, 2019, 15 (4), ⟨10.23638/LMCS-15(4:15)2019⟩. 〈hal〉.
  2. Alain Finkel, Ekanshdeep Gupta. The Well Structured Problem for Presburger Counter Machines. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Dec 2019, Bombay, India. ⟨10.4230/LIPIcs.FSTTCS.2019.41⟩. 〈hal〉.
  3. Alain Finkel, Ekanshdeep Gupta. The Well Structured Problem for Presburger Counter Machines. 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), Arkadev Chattopadhyay; Paul Gastin, Dec 2019, Mumbai, India. 〈hal〉.
  4. Changmin Wu, Giannis Nikolentzos, Michalis Vazirgiannis. Matching Node Embeddings Using Valid Assignment Kernels. The 8th International Conference On Complex Networks And Their Applications Complex Networks 2019, Dec 2019, Lisbon, Portugal. pp.810-821, ⟨10.1007/978-3-030-36687-2_67⟩. 〈hal〉.
  5. Alain Finkel, Serge Haddad, Igor Khmeniltsky. A Tool for the Coverability Problems in Petri Nets. MSR 2019 - 12ème Colloque sur la Modélisation des Systèmes Réactifs, Nov 2019, Angers, France, Nov 2019, Angers, France. 〈hal〉.
  6. Alain Finkel, Serge Haddad, Igor Khmeniltsky. Réification des accélérations pour la construction de Karp et Miller. Modélisation des Systèmes Réactifs (MSR 19), Nov 2019, Angers, France, Nov 2019, Angers, France. 〈hal〉.
  7. Jérôme Leroux. Distance Between Mutually Reachable Petri Net Configurations. 39th {IARCS} Annual Conference on Foundations of Software Technology and Theoretical Computer Science, {FSTTCS} 2019, December 11-13, 2019, Bombay, India, Nov 2019, Bombay, India. 〈hal〉.
  8. Petr Jančar, Jérôme Leroux, Grégoire Sutre. Co-Finiteness and Co-Emptiness of Reachability Sets in Vector Addition Systems with States. Fundamenta Informaticae, 2019, 169 (1-2), pp.123-150. ⟨10.3233/FI-2019-1841⟩. 〈hal〉.
  9. Jérôme Leroux, Jean-François Raskin. Proceedings Tenth International Symposium on Games, Automata, Logics, and Formal Verification, GandALF 2019, Bordeaux, France, 2-3rd September 2019. Electronic Proceedings in Theoretical Computer Science, 305, 2019, ⟨10.4204/EPTCS.305⟩. 〈hal〉.
  10. Alain Finkel, M. Praveen. Verification of Flat FIFO Systems. CONCUR 2019, Aug 2019, AMSTERDAM, Netherlands. 〈hal〉.
  11. Diego Figueira. Co-finiteness of VASS coverability languages. 2019. 〈hal〉.
  12. Sylvain Schmitz. The Parametric Complexity of Lossy Counter Machines. ICALP 2019, Jul 2019, Patras, Greece. pp.129:1--129:15, ⟨10.4230/LIPIcs.ICALP.2019.129⟩. 〈hal〉.
  13. Petr Jancar, Sylvain Schmitz. Bisimulation Equivalence of First-Order Grammars is ACKERMANN-Complete. LICS 2019, 34th Annual ACM/IEEE Symposium on Logic in Computer Science, Jun 2019, Vancouver, Canada. pp.1--12, ⟨10.1109/LICS.2019.8785848⟩. 〈hal〉.
  14. Jérôme Leroux, Sylvain Schmitz. Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension. LICS 2019, 34th Annual ACM/IEEE Symposium on Logic in Computer Science, Jun 2019, Vancouver, Canada. pp.1--13, ⟨10.1109/LICS.2019.8785796⟩. 〈hal〉.
  15. Alain Finkel, Serge Haddad, Igor Khmelnitsky. Coverability and Termination in Recursive Petri Nets, Couverture et Terminaison dans les réseaux de Petri Récursifs. Petri Nets 2019 / ACSD 2019 - 40th International Conference on Application and Theory of Petri Nets and Concurrency, Jun 2019, Aachen, Germany. 〈hal〉.
  16. Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić, Jérôme Leroux, Filip Mazowiecki. The reachability problem for Petri nets is not elementary. Proceedings of the 51st Annual {ACM} {SIGACT} Symposium on Theory of Computing, {STOC} 2019, Phoenix, AZ, USA, June 23-26, 2019, Jun 2019, Phoenix, United States. pp.24-33, ⟨10.1145/3313276.3316369⟩. 〈hal〉.
  17. S. Halfon, Ph. Schnoebelen. On shuffle products, acyclic automata and piecewise-testable languages. Information Processing Letters, 2019, 145, pp.68-73. ⟨10.1016/j.ipl.2019.01.012⟩. 〈hal〉.
  18. Jean Goubault-Larrecq. Spaces with no Infinite Discrete Subspace. Topology Proceedings, 2019, 53. 〈hal〉.
  19. Giannis Nikolentzos, M Vazirgiannis. Learning Structural Node Representations using Graph Kernels. IEEE Transactions on Knowledge and Data Engineering, 2019, pp.1-1. ⟨10.1109/TKDE.2019.2947478⟩. 〈hal〉.
  20. Jérôme Leroux. Petri Net Reachability Problem (Invited Talk). 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), 2019, Aachen, Germany. 〈hal〉.
  21. Sylvain Schmitz, Georg Zetzsche. Coverability Is Undecidable in One-Dimensional Pushdown Vector Addition Systems with Resets. 13th International Conference on Reachability Problems (RP 2019), 2019, Brussels, Belgium. pp.193--201, ⟨10.1007/978-3-030-30806-3_15⟩. 〈hal〉.

2018

  1. Vincent Penelle, Sylvain Salvati, Grégoire Sutre. On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems. FSTTCS 2018 - 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2018, Ahmedabad, India. pp.44:1-44:20, ⟨10.4230/LIPIcs.FSTTCS.2018.44⟩. 〈hal〉.
  2. Alain Finkel, Jérôme Leroux, Grégoire Sutre. Reachability for Two-Counter Machines with One Test and One Reset. FSTTCS 2018 - 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2018, Ahmedabad, India. pp.31:1-31:14, ⟨10.4230/LIPIcs.FSTTCS.2018.31⟩. 〈hal〉.
  3. Thomas Geffroy, Jérôme Leroux, Grégoire Sutre. Occam's Razor applied to the Petri net coverability problem. Theoretical Computer Science, 2018, 750, pp.38-52. ⟨10.1016/j.tcs.2018.04.014⟩. 〈hal〉.
  4. Alain Finkel, Etienne Lozes. Synchronizability of Communicating Finite State Machines is not Decidable. 2018. 〈hal〉.
  5. Raphael Chane-Yack-Fa, Marc Frappier, Amel Mammar, Alain Finkel. Parameterized verification of monotone information systems. Formal Aspects of Computing, 2018, 30 (3-4), pp.463 - 489. ⟨10.1007/s00165-018-0460-8⟩. 〈hal〉.
  6. Jérôme Leroux. Polynomial Vector Addition Systems With States. 45th International Colloquium on Automata, Languages, and Programming, {ICALP} 2018, July 9-13, 2018, Prague, Czech Republic, Jul 2018, Prague, Czech Republic. pp.134:1--134:13. 〈hal〉.
  7. Diego Figueira, M. Praveen. Playing with Repetitions in Data Words Using Energy Games. Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Jul 2018, Oxford, United Kingdom. ⟨10.1145/3209108.3209154⟩. 〈hal〉.
  8. Petr Jančar, Jérôme Leroux, Grégoire Sutre. Co-Finiteness and Co-Emptiness of Reachability Sets in Vector Addition Systems with States. PETRI NETS 2018 - 39th International Conference on the Application and Theory of Petri Nets and Concurrency, Jun 2018, Bratislava, Slovakia. pp.184-203, ⟨10.1007/978-3-319-91268-4_10⟩. 〈hal〉.
  9. Alain Finkel, Michael Blondin, Pierre Mckenzie. Handling infinitely branching well-structured transition systems. Information and Computation, 2018, 258, pp.28-49. ⟨10.1016/j.ic.2017.11.001⟩. 〈hal〉.
  10. Jérôme Leroux. Polynomial Vector Addition Systems With States. 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, 2018, Prague, Czech Republic. ⟨10.4230/LIPIcs.ICALP.2018.134⟩. 〈hal〉.

2017

  1. Michael Blondin, Alain Finkel, Jean Goubault-Larrecq. Forward Analysis for WSTS, Part III: Karp-Miller Trees. 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Dec 2017, Kanpur, India. ⟨10.4230/LIPIcs.FSTTCS.2017.16⟩. 〈hal〉.
  2. Alain Finkel, Etienne Lozes. Synchronizability of Communicating Finite State Machines is not Decidable. 44th International Colloquium on Automata, Languages, and Programming ICALP 2017, 2017, Varsaw, Poland. ⟨10.4230/LIPIcs.ICALP.2017.122⟩. 〈hal〉.
  3. Serge Haddad, Michael Blondin, Christoph Haase, Alain Finkel. The Logical View on Continuous Petri Nets. ACM Transactions on Computational Logic, 2017, 18 (3). 〈hal〉.
  4. Michael Blondin, Alain Finkel, Pierre Mckenzie. Well Behaved Transition Systems. Logical Methods in Computer Science, 2017, ⟨10.23638/LMCS-13(3:24)2017⟩. 〈hal〉.