Publications

Not every publication of a member or an associate member of ReLaX is joint with a co-author from the other country. We list here only the publications with an India-based and a France-based co-author or with an explicit reference to the UMI ReLaX, along with some publications presented in FSTTCS, the yearly international conference in theoretical computer science sponsored by the IARCS (Indian Association for Research in Computing Science) and ICLA, the biennial conference in logic sponsored by ALI (Association for Logic in India).

Submitted and to appear

Sinnou David, Noriko Hirata-Kohno, Makoto Kawashima. Recent Developments on Polylogarithms and Period Conjecture (in Japanese). Submitted.

Frédérique Bassino, Cyril Nicaud, Pascal Weil. Silhouettes and generic properties of subgroups of the modular group. Submitted

Pierre Fima, François Le Maître, Kunal Mukherjee, Issan Patri. Michael’s selection theorem and applications to the Maréchal topology. Submitted.

Olivier Ramaré, G. Kasi Wiswanadham. The trigonometric polynomial on sums of two squares, an additive problem and generalisation. Submitted

Pierre Fima, Malay Mandal, Issan Patri. Operator algebras of universal quantum homomorphisms. Submitted.

Diego Figueira, S. Krishna, Om Swostik Mishra, Anantha Padmanabha. Boundedness for Unions of Conjunctive Regular Path Queries over Simple Regular Expressions. In: Proceedings of KR’24. To appear.

Sanoli Gun, Olivier Ramaré, Jyothsnaa Sivaraman. An application of counting ideals in ray classes. Acta Arithmetica. To appear.

Marco Aymone, Gopal Maiti, Olivier Ramaré, Priyamvad Srivastav. Convolution of periodic multiplicative functions and the divisor problem. Canadian J. Mathematics. To appear.

2024 ReLaX publications

Frédérique Bassino, Cyril Nicaud, Pascal Weil. Random generation of subgroups of the modular group with a fixed isomorphism type. Electronic Journal of Combinatorics 31:4 (2024). DOI: 10.37236/12559

Arnaud Casteigts, Timothée Corsini, Writika Sarkar. Simple, strict, proper, happy: A study of reachability in temporal graphs. Theoretical Computer Science 991 (2024) 114434. DOI: 10.1016/j.tcs.2024.114434

Mallika Roy, Enric Ventura, Pascal Weil. The central tree property and algorithmic problems on subgroups of free groups. J. Group Theory 27:5 2024, pp. 1059-1089. DOI: 10.1515/jgth-2023-0050

S. Akshay, Paul Gastin, R. Govind and B. Srivathsan. Simulations for Event-Clock Automata. Logical Methods in Computer Science 20(3) 2024. DOI: 10.46298/lmcs-20(3:2)2024

Luc Dartois, Paul Gastin, Loïc Germerie Guizouarn, R. Govind and Shankara Narayanan Krishna. Reversible Transducers over Infinite Words. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024). DOI: 10.4230/LIPIcs.CONCUR.2024.21

S. Akshay, Paul Gastin, R. Govind and B. Srivathsan. MITL Model Checking via Generalized Timed Automata and a New Liveness Algorithm. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024). DOI:
10.4230/LIPIcs.CONCUR.2024.5

Geoffroy Couteau, Naman Kumar. 10-party sublinear secure computation from standard assumptions. In: Reyzin, L., Stebila, D. (eds) Advances in Cryptology CRYPTO 2024, Lecture Notes in Computer Science, vol 14928. Springer (2024). DOI: 10.1007/978-3-031-68400-5_2

Parosh Aziz Abdulla, Mohamed Faouzi Atig, Ahmed Bouajjani, K. Narayan Kumar, Prakash Saivasan. Verification under Intel-x86 with Persistency. In: Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2024). Article 195, pp. 1189-1212, 2024. DOI: 10.1145/3656425

M. Praveen, Philippe Schnoebelen, Julien Véron, Isa Vialard. On the piecewise complexity of words and periodic words. In: In: Fernau, H., Gaspers, S., Klasing, R. (eds) Theory and Practice of Computer Science (SOFSEM 2024). Lecture Notes in Computer Science, vol 14519. Springer. DOI: 10.1007/978-3-031-52113-3_32

C. Aiswarya, Soumodev Mal, Prakash Saivasan. Satisfiability of Context-Free String Constraints with Subword-Ordering and Transducers. In: International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024),  5:1-5:20. DOI: 10.4230/LIPIcs.STACS.2024.5

Loïc Hélouet, Prerak Contractor. Symbolic domains and reachability for nets with trajectories. In: Kristensen, L.M., van der Werf, J.M. (eds) Application and Theory of Petri Nets and Concurrency (Petri Nets 2024). Lecture Notes in Computer Science, vol 14628. Springer (2024). DOI: 10.1007/978-3-031-61433-0_12

R. Ramanujam, Vaishnavi Sundararajan, S.P. Suresh. Solving the insecurity problem for assertions. In: Proceedings of the 37th IEEE Computer Security Foundations Symposium (CSF), 2024, pp. 112-126. DOI: 10.1109/CSF61375.2024.00008

Bharat Adsul, Paul Gastin, Shantanu Kulkarni, Pascal Weil. Propositional dynamic logic and asynchronous cascade decompositions for regular trace languages. In: LICS ’24: Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, Article No.: 2, Pages 1 – 13. DOI: 10.1145/3661814.3662110

2023 ReLaX publications

Julien Roth, Abhitosh Upadhyay. On almost stable linear Weingarten hypersurfaces. Bulletin des Sciences Mathématiques 189 (2023) 103343. DOI: 10.1016/j.bulsci.2023.103343

Sanoli Gun, Olivier Ramaré, Jyothsnaa Sivaraman. Counting ideals in ray classes. J. Number Theory 243 (2023) 13-37. DOI: 10.1016/j.jnt.2022.08.005

Ramachandran Balasubramanian, Olivier Ramaré, Priyamvad Srivastav. Explicit bounds for products of primes in AP. Mathematics of Computation 92 (243) (2023) 2381-2411. DOI:  10.1090/mcom/3853

Ramachandran Balasubramanian, Olivier Ramaré, Priyamvad Srivastav. Product of three primes in large arithmetic progressions. International Journal of Number Theory 19:04 (2023) 843-857. DOI: 10.1142/S1793042123500422

Olivier Ramaré, Gopajosiula Kasi Viswanadham. Exponential sums over primes with multiplicative coefficients. Mathematische Zeitschrift 304:50 (2023), 21 pp. 10.1007/s00209-023-03305-7

Ratnadeep Acharya, Sary Drappeau, Satadal Ganguly, Olivier Ramaré. A modular analogue of a problem of Vinogradov. Ramanujan J. 62:2 (2023) 365-382. DOI: 10.1007/s11139-022-00688-9

Dhruv Nevatia, Benjamin Monmege. An Automata Theoretic Characterization of Weighted First-Order Logic. In (É. André, J. Sun, eds) Automated Technology for Verification and Analysis (ATVA 2023). Lecture Notes in Computer Science 14215, Springer, Cham., 2023. DOI: 10.1007/978-3-031-45329-8_6

Samir Datta, Asif Khan, Anish Mukherjee. Dynamic Planar Embedding Is in DynFO. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (J. Leroux, S. Lombardy, D. Peleg, eds), volume 272 of LIPIcs, pages 39:1-39:15, 2023. DOI: 10.4230/LIPIcs.MFCS.2023.39

Diego Figueira, Anantha Padmanabha, Luc Segoufin, Cristina Sirangelo.
A Simple Algorithm for Consistent Query Answering Under Primary Keys. In 26th International Conference on Database Theory (ICDT 2023) (F. Geerts, B. Vandevoort, eds), volume 255 of LIPIcs, pages 24:1-24:18, 2023. DOI: 10.4230/LIPIcs.ICDT.2023.24

Madhavan Mukund, Adwitee Roy, B. Srivathsan. A Local-Time Semantics for Negotiations. In Proc. 21st International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS 2023) (L. Petrucci and J. Sproston, eds), Lecture Notes in Computer Science 14138, Springer, 2023, 105-121. DOI: 10.1007/978-3-031-42626-1\_7

S. Akshay, Paul Gastin, R. Govind, Aniruddha R. Joshi, B. Srivathsan. A Unified Model for Real-Time Systems: Symbolic Techniques and Implementation. In Proc. of 35th International Conference on Computer Aided Verification (CAV 2023) (C. Enea, A. Lal, eds,), Lecture Notes in Computer Science 13964, Springer, 2023, 266 – 288. DOI: 10.1007/978-3-031-37706-8\_14

Henning Fernau, Florent Foucaud, Kevin Mann, Utkarsh Padariya and Rajath Rao K.N. Parameterizing path partitions. Proceedings of the 13th International Conference on Algorithms and Complexity (CIAC 2023), Lecture Notes in Computer Science 13898, Springer, 2023, 187-201. DOI: 10.1007/978-3-031-30448-4_14

Ashwin Bhaskar and M. Praveen. Constraint LTL with Remote Access. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 41:1-41:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023). DOI: 10.4230/LIPIcs.FSTTCS.2023.41 

2022 ReLaX publications

Sinnou David, Noriko Hirata-Kohno, Makoto Kawashima. Linear forms in polylogarithms.  Annali della Scuola Normale Superiore di Pisa 23:3 (2022) 1447-1490. DOI: 10.4064/aa220307-18-10

Hugo Gimbert. Distributed Asynchronous Games with Causal Memory are Undecidable. Logical Methods in Computer Science 18:3 (2022) 30:1-30:22. DOI: 10.46298/lmcs-18(3:30)2022

Benedikt Bollig, Alain Finkel, Amrita Suresh. Bounded Reachability Problems are Decidable in FIFO Machines. Logical Methods in Computer Science 18:1 (2022) 19:1-19:32. DOI: 10.46298/lmcs-18(1:19)2022

B. Srivathsan: Reachability in timed automata. ACM Siglog News 9:3 (2022) 6-28.

Loïc Hélouët, Nicolas Markey, Ritam Raha. Reachability games with relaxed energy constraints. Information and Computation (2022) 104806. DOI: 10.1016/j.ic.2021.104806

Vrunda Dave, Paul Gastin, S. N. Krishna. Regular Transducer Expressions for Regular Transformations. Information and Computation 282 (2022) 104655. DOI: 10.1016/j.ic.2020.104655

Bharat Adsul, Paul Gastin, Saptarshi Sarkar, Pascal Weil. Asynchronous wreath product and cascade decompositions for concurrent behaviours. Logical Methods in Computer Science 18:2 (2022) 22:1-22:44. DOI: 10.46298/lmcs-18(2:22)2022

Francesco Amoroso, Sinnou David. On the Galois group of lacunary polynomials. Rivista di Matematica dell’Università di Palermo (N.S.) 13 (2022) 19-29.

Lars Jaffke, Paloma T. Lima, Geevarghese Philip. Structural Parameterizations of Clique Coloring. Algorithmica 84:2 (2022) 273-303. DOI: 10.1007/s00453-021-00890-z

Julien Baste, Michael R. Fellows, Lars Jaffke, Tomáš Masařík, Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond.  Diversity of solutions: an exploration through the lens of fixed-parameter tractability theory. Artif. Intell. 303: 103644 (2022). DOI: 10.1016/j.artint.2021.103644

Arnaud Casteigts, Timothée Corsini, Writika Sarkar. Simple, strict, proper, happy: A study of reachability in temporal graphs, Proceedings of the 24th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) (S. Devismes, F. Petit, K. Altisen, G. A. Di Luna, A. F. Anta, eds.), Lecture Notes in Computer Science 13751, Springer, 2022, 3-18.

Ashwin Bhaskar, M. Praveen. Realizability Problem for Constraint LTL. In 29th International Symposium on Temporal Representation and Reasoning, TIME 2022 (A. Artikis, R. Posenato, S. Tonetta, eds), volume 247 of LIPIcs, pages 8:1-8:19, 2022. DOI: 10.4230/LIPIcs.TIME.2022.8

Bharat Adsul, Paul Gastin, Saptarshi Sarkar, Pascal Weil. Propositional dynamic logic and asynchronous cascade decompositions for regular trace languages. In 33rd International Conference on Concurrency Theory (CONCUR 2022) (B. Klin, S. Lasota, A. Muscholl eds), volume 243 of LIPIcs, pages 28:1-28:19, 2022. DOI: 10.4230/LIPIcs.CONCUR.2022.28

Frédéric Herbreteau, B. Srivathsan, Igor Walukiewicz. Checking timed Büchi automata emptiness using the local-time semantics. In 33rd International Conference on Concurrency Theory (CONCUR 2022) (B. Klin, S. Lasota, A. Muscholl eds), volume 243 of LIPIcs, pages 12:1-12:24, 2022. DOI: 10.4230/LIPIcs.CONCUR.2022.12

S. Akshay, Paul Gastin, R. Govind and B. Srivathsan. Simulations for event-clock automata. In 33rd International Conference on Concurrency Theory(CONCUR 2022) (B. Klin, S. Lasota, A. Muscholl eds), volume 243 of LIPIcs, pages 13:1-13:18, 2022. DOI: 10.4230/LIPIcs.CONCUR.2022.13

R. Govind, Frédéric Herbreteau, B. Srivathsan, Igor Walukiewicz. Abstractions for the local-time semantics of timed-automata: a foundation for partial-order methods. In LICS’22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science (C. Baier, D. Fisman, eds), ACM, 2022, 24:1-24:14. DOI: 10.1145/3531130.3533343

Luc Dartois, Paul Gastin, R. Govind, S. Krishna. Efficient construction of reversible transducers from regular transducer expressions. In LICS’22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science (C. Baier, D. Fisman, eds), ACM, 2022, 24:1-24:14. DOI: 10.1145/3531130.3533364

Patricia Bouyer, Paul Gastin, Frédéric Herbreteau, Ocan Sankur, B. Srivathsan. Zone-based verification of times automata: extrapolations, simulations and what next? In Proc. of the 20th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS’22), Lecture Notes in Computer Science 13465, Springer, 2022, 16-42. DOI: 10.1007/978-3-031-15839-1_2

Nathanaël Fijalkow, Guillaume Lagarde, Théo Matricon, Kevin Ellis, Pierre Ohlmann, Akarsh Potta. Scaling Neural Program Synthesis with Distribution-based Search, Proceedings of the AAAI Conference on Artificial Intelligence, 36(6), 6623-6630, 2022. DOI: 10.1609/aaai.v36i6.20616

S. Akshay, Hugo Bazille, Blaise Genest, Mihir Vahanwala. On Robustness for the Skolem and positivity problems. 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) (P. Berenbrink, B. Monmège, eds), volume 219 of LIPIcs, pages 5:1-5:20, 2022. DOI: 10.4230/LIPIcs.STACS.2022.5

Loïc Hélouët, Pranay Agrawal. Waiting Nets. In Application and Theory of Petri Nets and Concurrency. Petri Nets 2022 (Bernardinello, L., Petrucci, L. eds), Lecture Notes in Computer Science 13288, Springer, 2022, 67-89. Best paper award! DOI: 10.1007/978-3-031-06653-5_4

Benedikt Bollig, Alain Finkel, Amrita Suresh. Branch-Well-Structured Transition Systems and Extensions. In 42nd International Conference on Formal Techniques for Distributed Objects, Components, and Systems, FORTE’22 (M. Reza Mousavi and A. Philippou, eds), Lecture Notes in Computer Science 13273, Springer, 2022, 50-66. DOI: 10.1007/978-3-031-08679-3\_4

Ritam Raha, Rajarshi Roy, Nathanaël Fijalkow, Daniel Neider. Scalable Anytime Algorithms for Learning Formulas in Linear Temporal Logic, Proceedings of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2022 (D. Fisman, G. Rosu, eds), Lecture Notes in Computer Science 13243, Springer, 2022. DOI: 10.1007/978-3-030-99524-9_14

Parosh Aziz Abdulla, Mohamed Faouzi Atig, Ahmed Bouajjani, B. Jonsson,K. Narayan Kumar, Prakash Saivasan. Consistency and Persistency in Program Verification: Challenges and Opportunities. A chapter in: Principles of Systems Design, Lecture Notes in Computer Science 13660, Springer, 2022. DOI: 10.1007/978-3-031-22337-2_24

2021 ReLaX publications

Parosh Abdulla, M. F. Atig, Ahmed Bouajjani, K. Narayan Kumar and Prakash Saivasan. Deciding Reachability under Persistent x86-TSO. Proceedings of the ACM on the Principles of Programming Languages 5 (2021) 1-32. DOI: 10.1145/3434337

Julien Bensmail, Sandip Das, Soumen Nandi, Soumyajit Paul, Théo Pierron, Sagnik Sen, Éric Sopena. Pushable chromatic number of graphs with degree constraints. Discrete Mathematics 344:1 (2021) 112-151. DOI: 10.1016/j.disc.2020.112151

Frédérique Bassino, Cyril Nicaud, P. Weil. Statistics of subgroups of the modular group. International Journal of Algebra and Computation 31:8 (2021) 1691-1751. DOI: 10.1142/S0218196721500624

Raphaël Berthon, Nathanaël Fijalkow, Emmanuel Filiot, Shibashis Guha, Bastien Maubert, Aniello Murano, Laureline Pinault, Sophie Pinchinat, Sasha Rubin, Olivier Serre. Alternating Tree Automata with Qualitative Semantics. ACM Trans. Comput. Log. 22(1) (2021) 7:1-7:24.

Paul Gastin, Amaldev Manuel, R. Govind. Reversible Regular Languages: Logical and Algebraic Characterisations. Fundamenta Informaticæ 180:4 (2021), 333-350. DOI: 10.3233/FI-2021-2045

Francesco Amoroso, Sinnou David. Covolumes, unités, régulateur: conjectures de D. Bertrand et F. Rodriguez-Villegas.  Annales mathématiques du Québec 45 (2021), 1-18. Awarded the first CRM-ISM-AMQ prize for an outstanding publication in the Annales Mathématiqu es du Québec. DOI: 10.1007/s40316-019-00128-z

Hans van Ditmarsch, David Fernández Duque, Vaishnavi Sundararajan, S.P. Suresh. Who holds the best card? Secure communication of optimal secret bits. Australasian Journal of Combinatorics 80(1) (2021), 1-29.

Nathalie Bertrand, Patricia Bouyer, Anirban Majumdar. Reconfiguration and Message Losses in Parameterized Broadcast Networks. Logical Methods in Computer Science 17(1) (2021). DOI: 10.23638/LMCS-17(1:23)2021

Danny Hendler, Adnane Khattabi, Alessia Milani, Corentin Travers. Upper and Lower Bounds for Deterministic Approximate Objects. In Proceedings of the 41st IEEE International Conference on Distributed Computing Systems (ICDCS 2021), 438-448. DOI: 10.1109/ICDCS51616.2021.00049

Rupak Majumdar, Madhavan Mukund, Felix Stutz and Damien Zufferey, Generalizing Projection in Asynchronous Multiparty Session Types. In Proceedings of 32nd International Conference on Concurrency Theory (CONCUR 2021), LIPIcs Vol 203, 35:1-35:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021), DOI: https://doi.org/10.4230/LIPIcs.CONCUR.2021.0

Benedikt Bollig, Cinzia Di Giusto, Alain Finkel, Laetitia Laversa, Etienne Lozes, Amrita Suresh. A Unifying Framework for Deciding Synchronizability. In Proceedings of 32nd International Conference on Concurrency Theory (CONCUR 2021), LIPIcs Vol 203, 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021), DOI: 10.4230/LIPIcs.CONCUR.2021.14

Benoît Barbot, Benedikt Bollig, Alain Finkel, Serge Haddad, Igor Khmelnitsky, Martin Leucker, Daniel Neider, Rajarshi Roy, Lina Ye. Extracting Context-Free Grammars from Recurrent Neural Networks using Tree-Automata Learning and A* Search. Proceedings of the Fifteenth International Conference on Grammatical Inference (ICGI), Proceedings of Machine Learning Research 153, 2021: 113-129

Snigdha Athaiya, Raghavan Komondoor and K. Narayan Kumar. Data Flow Analysis of Asynchronous Systems using Infinite Abstract Domains. In Programming Languages and Systems, Proceedings of the 30th European Symposium on Programming (ESOP 2021) (N. Yoshida ed.). Lecture Notes in Computer Science 12648, Springer, 2021, 30-58. DOI: 10.1007/978-3-030-72019-3_2

Igor Khmelnitsky, Daniel Neider, Rajarshi Roy, Xuan Xie, Benoît Barbot, Benedikt Bollig, Alain Finkel, Serge Haddad, Martin Leucker, Lina Ye. Property-Directed Verification and Robustness Certification of Recurrent Neural Networks. In Proceedings of Automated Technology for Verification and Analysis (ATVA 2021) (Zhe Hou and Vijay Ganesh, eds). Lecture Notes in Computer Science 12971, Springer, 2021, 364-380. DOI: 10.1007/978-3-030-88885-5\_24

Ashwani Anand, Nathanaël Fijalkow, Aliénor Goubault-Larrecq, Jérôme Leroux, Pierre Ohlmann. New Algorithms for Combinations of Objectives using Separating Automata. Proceedings of GandALF (D. Della Monica, G. L. Pozzato, E. Scala eds), CEUR Workshop Proceedings 2987, 2021, 227-240.

Fedor Fomin, Petr Golovach, Fahad Panolan, Geevarghese Philip, Saket Saurabh. Diverse Collections in Matroids and Graphs. 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) (M. Bläser, B. Monmège, eds), volume 187 of LIPIcs, pages 31:1-31:14, 2021. DOI: 10.4230/LIPIcs.STACS.2021.31

Prajakta Nimbhorkar, Geevarghese Philip, Vishwa Prakash H.V. Disjoint Stable Matchings in Linear Time. In Graph Theoretic Concepts in Computer Science WG 2021 (Ł. Kowalik, M. Pilipczuk, P. Rzążewski), Lecture Notes in Computer Science 12911, Springer, 2021. DOI: 10.1007/978-3-030-86838-3_7

S. Akshay, Paul Gastin, Karthik R.Prakash. Fast Zone-based Algorithms for Reachability in Pushdown Timed Automata. Computer Aided Verification (CAV 2021) Proceedings, Part I (Alexandra Silva, K. Rustan, M. Leino, eds). Lecture Notes in Computer Science 12759, Springer, 2021, 619-642.

Sougata Bose, S.N. Krishna, Anca Muscholl, Gabriele Puppis. One-way Resynchronization of Word Transducers. FoSSaCS 2021, Lecture Notes in Computer Science 12650, Springer, 2021, 124-143. DOI: 10.1007/978-3-030-71995-1_7

2020 ReLaX publications

Frédéric Herbreteau, B. Srivathsan, T.T. Tung, Igor Walukiewicz. Why liveness for timed automata is hard, and what we can do about it. ACM Trans. Comput. Logic 21(3) 17:1-17:28 (2020).

Alain Finkel, M. Praveen. Verification of Flat FIFO Systems. Logical Methods in Computer Science 20(4) (2020). DOI: 10.23638/LMCS-16(4:4)2020

Diego Figueira, Anirban Majumdar, M. Praveen. Playing with Repetitions in Data Words Using Energy Games. Logical Methods in Computer Science 16(3) (2020). DOI: 10.23638/LMCS-16(3:1)2020

R. Ramanujam, Vaishnavi Sundararajan and S.P. Suresh. The complexity of disjunction in intuitionistic logic. Journal of Logic and Computation 30:1 (2020), 421–445. DOI: 10.1093/logcom/exaa018

Shweta Bhandari, Frédéric Herbreteau, V. Laxmi, Akka Zemmari, M. S. Gaur, P. S. Roop. SneakLeak+: Large-Scale Klepto Apps Analysis. Future Generation Computer Systems 109 (2020), 593-603. DOI: 10.1016/j.future.2018.05.047

J. Gajrani, U. Agarwal, Vijaya Laxmi, B. Bezawada, Manoj Singh Gaur, M. Tripathi, Akka Zemmari. EspyDroid+: Precise Reflection Analysis of Android Apps. Computers & Security 90 (2020). DOI: 10.1016/j.cose.2019.101688

Sinnou David, Noriko Hirata-Kohno, Makoto Kawashima. Can polylogarithms at algebraic points be linearly independent?  Mosc. J. Comb. Number Theory 9 (2020), no. 4, 389–406.

S. Akshay, Blaise Genest, Loïc Hélouet, Sharvik Mital. Timed Negotiation. In Proceedings of FoSSaCS 2020 (Goubault-Larrecq J., König B., eds). Lecture Notes in Computer Science 12077, Springer, 2020, 37-56. DOI: 10.1007/978-3-030-45231-5_3

Mirza Ahad Baig, Danny Hendler, Alessia Milani, Corentin Travers. Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity. In Proceedings of PODC 2020, pages 31-40, ACM (2020). DOI: 10.1145/3382734.3406005

Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, Danil Sagunov. Diverse Pairs of Matchings. In Proceedings of ISAAC 2020, LIPIcs, Volume 181, pages 26:1-26:12.

V. Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay. A special case of rational identity testing and the Brešar-Klep theorem. In Proceedings of MFCS 2020, LIPIcs, volume 170, 10:1-10:14. DOI: 10.4230/LIPIcs.MFCS.2020.10

Lars Jaffke, Paloma T. Lima, Geevarghese Philip. Structural Parameterizations of Clique Coloring. In Proceedings of MFCS 2020, LIPIcs, Volume 170, pages 49:1-49:15.

Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals.  MaxSAT Resolution and Subcube Sums. In Proceedings 23rd International Conference on Theory and Applications of Satisfiability Testing (SAT) (L. Pulina and M. Seidl eds), Lecture Notes in Computer Science 12178, Springer, 2020, to appear.

Julien Baste, Michael R. Fellows, Lars Jaffke, Tomáš Masařík, Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond. Diversity of solutions: an exploration through the lens of fixed-parameter tractability theory. In Proceedings of IJCAI 2020, IJCAI, pages 1119-1125.

Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, Saket Saurabh. A (2+ε)-factor approximation algorithm for split vertex deletion. In Proceedings of ICALP 2020, LIPIcs, Volume 168, pages 80:1-80:16.

Geevarghese Philip, M. R. Rani, R. Subashini. On Computing the Hamiltonian index of graphs. In  Proceedings of CSR 2020, Lecture Notes in Computer Science 12159, Springer, 2020, 341-353. DOI: 10.1007/978-3-030-50026-9_25

C. Aiswarya, Paul Gastin. Weighted Tiling Systems for Graphs: Evaluation complexity. In Proceedings of FSTTCS 2020, LIPICs, volume 182, pages 34:1-34:17. DOI: 10.4230/LIPIcs.FSTTCS.2020.34. Version longue.

Paul Gastin, Sayan Mukherjee, B. Srivathsan. Reachability for updatable timed automata made faster and more effective. In Proceedings of FSTTCS 2020, LIPICs, volume 182, pages 47:1-47:17. DOI: 10.4230/LIPIcs.FSTTCS.2020.47. Version longue.

Nathalie Bertrand, Patricia Bouyer, Anirban Majumdar. Synthesizing Safe Coalition Strategies. In Proceedings of FSTTCS 2020, LIPICs, volume 182, pages 39:1-39:17.  DOI:  10.4230/LIPIcs.FSTTCS.2020.39

Nathalie Bertrand, Nicolas Markey, Suman Sadhukhan, Ocan Sankur: Dynamic Network Congestion Games. In Proceedings of FSTTCS 2020, LIPICs, volume 182, pages 40:1-40:16. DOI: 10.4230/LIPIcs.FSTTCS.2020.40

M. Praveen, What You Must Remember When Transforming Datawords. In Proceedings of FSTTCS 2020, LIPICs, volume 182, pages 55:1-55:14.

Balasubramanian A. R. Complexity of Controlled Bad Sequences over Finite Sets of N^d. In Proceedings of the 35th ACM/IEEE Symp. Logic in Computer Science (LICS 2020), pages 130-140, ACM Press, 2020. DOI: 10.1145/3373718.3394753

Bharat Adsul, Paul Gastin, Saptarshi Sarkar, Pascal Weil. Wreath/cascade products and related decomposition results for the concurrent setting of Mazurkiewicz traces. In Proceedings of CONCUR 2020, volume 171 of LIPIcs, pages 19:1-19:17, 2020. DOI: 10.4230/LIPIcs.CONCUR.2020.19

Benedikt Bollig, Alain Finkel, Amrita Suresh. Bounded Reachability Problems are Decidable in FIFO Machines. In Proceedings of CONCUR 2020, volume 171 of LIPIcs, pages 49:1-49:17, 2020. Best paper award! DOI: 10.4230/LIPIcs.CONCUR.2020.49.

Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, Saket Saurabh. 2-Approximating feedback vertex set in tournaments. In Proceedings of SODA 2020. DOI: 10.1137/1.9781611975994.61

Anantha Padmanabha, R. Ramanujam. Verifying implicitly quantified modal logic over dynamic networks of processes. Proceedings of ICDCIT 2020, Lecture Notes in Computer Science 11969, Springer, 2020, 165-176. DOI: 10.1007/978-3-030-36987-3_10

S. Akshay, Paul Gastin, S. Krishna, Sparsa Roychowdhury. Revisiting underapproximate reachability for multipushdown systems. Proceedings of TACAS’20, part 1, Lecture Notes in Computer Science 12078, Springer, 2020, 387-404. DOI: 10.1007/978-3-030-45190-5_21

Diego Figueira, Adwait Godbole, S. Krishna, Wim Martens, Matthias Niewerth, Tina Trautner. Containment of Simple Regular Path Queries, Proceedings of KR’20.

Hugo Gimbert, Soumyajit Paul, B. Srivathsan. A Bridge between polynomial optimization and games with imperfect recall. Proceedings of 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2020, pages 456 – 464. DOI: 10.5555/3398761.3398818

Ahmed Bouajjani, Constantin Enea, Madhavan Mukund, Gautham Shenoy R., S. P. Suresh. Formalizing and Checking Multilevel Consistency. In Proceedings of VMCAI 2020, Lecture Notes in Computer Science 11990, pp. 379-400, Springer (2020). DOI: 10.1007/978-3-030-39322-9_18

Olga Kharlampovich, Pascal Weil. On the generalized membership problem in relatively hyperbolic groups. In Fields of Logic and Computation III — Essays dedicated to Yuri Gurevich on the occasion of his 80th birthday (A. Blass, P. Cégielski, N. Dershowitz, M. Droste, B. Finkbeiner, eds), Lecture Notes in Computer Science 12180, Springer, 2020, 147-155. DOI:10.1007/978-3-030-48006-06_11

Frédérique Bassino, Cyril Nicaud, Pascal Weil. Random presentations and random subgroups: a survey. In Complexity and Randomness in Group Theory – GAGTA Book 1, de Gruyter, 2020. DOI: 10.1515/9783110667028

Frédérique Bassino, Ilya Kapovich, Markus Lohrey, Alexei Miasnikov, Cyril Nicaud, Andrey Nikolaev, Igor Rivin, Vladimir Shpilrain, Alexander Ushakov, Pascal Weil. Complexity and Randomness in Group Theory – GAGTA Book 1, de Gruyter, 2020. DOI: 10.1515/9783110667028

Jean Goubault-Larrecq, Simon Halfon, Prateek Karandikar, K. Narayan Kumar, Philippe Schnoebelen. The Ideal Approach to Computing Closed Subsets in Well-Quasi-Orderings. Chapter 3 in Well-Quasi Orders in Logic, Language and Reasoning – A Unifying Concept of Proof Theory, Automata Theory, Formal Languages and Descriptive Set Theory (eds. P. Schuster, M. Seisenberger, A. Weiermann), pp. 55-105. Trends in Logic 53, Springer (2020). DOI: 10.1007/978-3-030-30229-0_3

2019 ReLaX publications

Vineeta Jain, Vijay Laxmi, Manoj Singh Gaur, Mohamed Mosbah. ETGuard: Detecting D2D attacks using wireless Evil Twins. Comput. Secur. 83 (2019) 389:405.

Anantha Padmanabha, R. Ramanujam. The monadic fragment of propositional term modal logic. Studia Logica 107:3 (2019) 533-557. DOI: 10.1007/s11225-018-9784-x

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 15:4 (2019). DOI: 10.23638/LMCS-15(4:15)2019

Nathalie Bertrand, Miheer Dewaskar, Blaise Genest, Hugo Gimbert, Adwait Godpole. Controlling a population. Logical Methods in Computer Science 15(3) (2019). DOI: 10.23638/LMCS-15(3:6)2019

Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, Thomas Zeume. A Strategy for Dynamic Programs: Start over and Muddle through. Logical Methods in Computer Science 15(2) (2019).

Thomas Place, Varun Ramanathan, Pascal Weil. Covering and separation for logical fragments with modular predicates. Logical Methods in Computer Science 15:2 (2019) 11:1-11:32. DOI: 10.23638/LMCS-15(2:11)2019

Vinod P., Akka Zemmari, Mauro Conti. A machine learning based approach to detect malicious Android apps using discriminant system calls. Future Generation Computer Systems 94 333–350 (2019).

Prateek Karandikar, Philippe Schnoebelen. The height of piecewise-testable languages and the complexity of the logic of subwords. Logical Methods in Computer Science 15:2 6:1–6:27 (2019). DOI: 10.23638/LMCS-15(2:6)2019

Geevarghese Philip, Varun Rajan, Saket Saurabh, Prafullkumar Tale. Subset feedback vertex set in chordal and split graphs. Algorithmica 81(9) (2019) 3586-3629. DOI: 10.1007/s00453-019-00590-9

Julien Baste, Lars Jaffke, Tomás Masarík, Geevarghese Philip, Günter Rote. FPT algorithms for diverse collections of hitting sets. Algorithms 12(12) (2019) 254. DOI: 10.3390/a12120254

Vineeta Jain, Vijay Laxmi, Manoj Singh Gaur, Mohamed Mosbah. APPLADroid: Automaton Based Inter-app Privacy Leak Analysis for Android. In Proceedings of ISEA-ISAP 2019, Communications in Computer and Information Science 939, Springer,  219:233, 2019. ISBN 978-981-13-7560-6 .

Ramit Das, R. Ramanujam, Sunil Simon. Reasoning about social choice and games in monadic fixed-point logic. In Proceedings of TARK 2019, pages 106-120

Anantha Padmanabha, R. Ramanujam. Propositional modal logic with implicit modal quantification. In Logic and its applications, 8th Indian Conference ICLA, Lecture Notes in Computer Science 11600, pp. 6-17, Springer, 2019. DOI: 10.1007/978-3-662-58771-3\_2

Agnishom Chattopadhyay, M. Praveen. Query Preserving Watermarking Schemes for Locally Treelike Databases. In Proceedings of FSTTCS 2019, volume 150 of LIPIcs, pages 36:1 – 36:14, 2019. DOI: 10.4230/LIPIcs.FSTTCS.2019.36

N. Bertrand, P. Bouyer, and A. Majumdar. Concurrent parameterized games. In Proceedings of FSTTCS 2019, volume 150 of LIPIcs, pages 31:1–31:15, 2019. DOI: 10.4230/LIPIcs.FSTTCS.2019.31

Ekanshdeep Gupta, Alain Finkel. The well structured problem for Presburger counter machines. In Proceedings of FSTTCS 2019, volume 150 of LIPIcs, pages 41:1 – 41:15. DOI: 10.4230/LIPIcs.FSTTCS.2019.41

Mirza Ahad Baig, Danny Hendler, Alessia Milani, Corentin Travers. Long-Lived Counters with Polylogarithmic Amortized Step Complexity. In Proceedings of DISC 2019, volume 146 of LIPIcs, pages 3:1 – 3:16. DOI: 10.4230/LIPIcs.DISC.2019.3

Loïc Hélouët, Nicolas Markey, Ritam Raha. Reachability games with relaxed energy constraints, GANDALF 2019, EPTCS. DOI: 10.4204/EPTCS.305.2

Nathalie Bertrand, Patricia Bouyer, Anirban Majumdar. Reconfiguration and message losses in parameterized broadcast networks. In Proceedings of CONCUR 2019, volume 140 of LIPIcs, pages 32:1 – 32:15. DOI: 10.4230/LIPIcs.CONCUR.2019.32

Alain Finkel, M. Praveen. Verification of Flat FIFO Systems. In Proceedings of CONCUR 2019, volume 140 of LIPIcs, pages 12:1 – 12:17. DOI: 10.4230/LIPIcs.CONCUR.2019.12

R. Govind, Frédéric Herbreteau, B. Srivathsan, Igor Walukiewicz. Revisiting local time semantics for networks of timed automata. In Proceedings of CONCUR 2019, volume 140 of LIPIcs, pages 16:1 – 16:15. DOI: 10.4230/LIPIcs.CONCUR.2019.16

Diego Figueira, Varun Ramanathan, Pascal Weil. The quantifier alternation hierarchy of synchronous relations. In Proceedings of MFCS 2019, volume 138 of LIPIcs, pages 29:1 – 29:14. DOI: 10.4230/LIPIcs.MFCS.2019.29

Anantha Padmanabha, R. Ramanujam. Two variable fragment of term modal logic. In Proceedings of MFCS 2019, volume 138 of LIPIcs, pages 30:1 – 30:14. DOI: 10.4230/LIPIcs.MFCS.2019.30

Sougata Bose, S.N. Krishna, Anca Muscholl, Vincent Penelle, Gabriele Puppis. On Synthesis of Resynchronizers for Transducers. In Proceedings of MFCS 2019, volume 138 of LIPIcs, pages 69:1 – 69:14. DOI: 10.4230/LIPIcs.MFCS.2019.69

Paul Gastin, Amaldev Manuel, and R. Govind. Logics for Reversible Regular Languages and Semigroups with Involution. In Proceedings of the 23th International Conference on Developments in Language Theory (DLT’19), Lecture Notes in Computer Science 11647, pp. 182-191, Springer, 2019. DOI: 10.1007/978-3-030-24886-4_13

Paul Gastin, Sayan Mukherjeee, B. Srivathsan. Fast Algorithms for Handling Diagonal Constraints in Timed Automata, In  Proceedings of CAV 2019, Lecture Notes in Computer Science 11561, pp. 41-59, Springer, 2019. DOI: 10.1007/978-3-030-25540-4_3

S. Akshay, Paul Gastin, Vincent Jugé, S.N. Krishna. Timed Systems through the Lens of Logic. In Proceedings of the 34th Annual ACM/IEEE Symposium on Logic In Computer Science (LICS’19), pp. 1-13, IEEE Press, 2019. DOI: 10.1109/LICS.2019.8785684

Geevarghese Philip, Varun Rajan, Saket Saurabh, Prafullkumar Tale. Subset feedback vertex set in chordal and split graphs. In Proceedings of CIAC 2019, pp. 365-376. DOI: 10.1007/978-3-030-17402-6_30

S. Akshay, Hugo Bazille, Eric Fabre, Blaise Genest. Classification Among Hidden Markov Models. In Proceedings of the 39th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), volume 150 of LIPIcs, pages 29:1-29:14.

Arkadev Chattopadhyay, Paul Gastin editors. Proceedings of the 39th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’19), Leibniz International Proceedings in Informatics (LIPIcs), volume 150,  2019.

Other 2019 papers related to ReLaX

V. Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay. Efficient black-box identity testing over free group algebra, Approx-Random 2019, LIPIcs. In Proceedings of APPROX-RANDOM 2019, volume 145 of LIPIcs, pages 57:1 – 57:16. DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.57

Kavitha Gopal, Meghana Nasre, Prajakta Nimbhorkar, and T. Pradeep Reddy. Many-to-one Popular Matchings with Two-Sided Preferences and One-Sided Ties, COCOON 2019.

2018 ReLaX publications

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. 2018.

Denis Kuperberg and Anirban Majumdar. Width of non-deterministic automata. In STACS 2018, Leibniz International Proceedings in Informatics 96, pages 47:1-47:14. Leibniz-Zentrum für Informatik, 2018. DOI: 10.4230/LIPIcs.STACS.2018.47.

Balasubramanian A.R, Nathalie Bertrand, Nicolas Markey. Parameterized verification of synchronization in constrained reconfigurable broadcast networks. In TACAS’18 (Part II), Lecture Notes in Computer Science 10806, pages 38-54. Springer-Verlag, April 2018. DOI: 10.1007/978-3-319-89963-3_3

Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi: Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth. SODA 2018: 262-273. DOI: 10.1137/1.9781611975031.19

Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, Meirav Zehavi. Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems. SODA 2018: 331-342. DOI: 10.1137/1.9781611975031.23

Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh. When Recursion is Better than Iteration: A Linear Time Algorithm for Acyclicity with Few Error Vertices. SODA 2018: 1916-1933. DOI: 10.1137/1.9781611975031.125

Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Meirav Zehavi. Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms. SODA 2018: 2785-2800. DOI: 10.1137/1.9781611975031.177

Jørgen Bang-Jensen, Manu Basavaraju, Kristine Vitting Klinkby, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi. Parameterized Algorithms for Survivable Network Design with Uniform Demands. SODA 2018: 2838-2850. DOI: 10.1137/1.9781611975031.180

2017 ReLaX publications

S. Bhandari, W. Ben Jaballah, V. Jain, V. Laxmi, A. Zemmari, M. S. Gaur, M. Mosbah, M. Conti. Android inter-app communication threats and detection techniques. Computers & Security, 70: 392-421 (2017).

N. Bertrand, M. Dewaskar, B. Genest, H. Gimbert. Controlling a Population. In  CONCUR’17, Leibniz International Proceedings in Informatics 85, pages 12:1-12:16. DOI: 10.4230/LIPIcs.CONCUR.2017.12

S. Akshay, P. Gastin, S. N. Krishna and I. Sarkar.  Towards an Efficient Tree Automata based technique for Timed Systems.  In  CONCUR’17, Leibniz International Proceedings in Informatics 85, pages 39:1-39:15. Leibniz-Zentrum für Informatik, 2017. doi: 10.4230/LIPIcs.CONCUR.2017.39

Abdullah Abdul Khadir, Madhavan Mukund and S.P. Suresh. Knowledge transfer and information leakage in protocols. In Proceedings of ATVA 2017, Springer, Lect. Notes in Comp. Science 10482  (2017), 225-240.

J. Gajrani, V. Laxmi, M. Tripathi, M.S. Gaur, D. R. Sharma, A. Zemmari, M. Mosbah, M. Conti. Unraveling Reflection Induced Sensitive Leaks in Android Apps. In Proceedings of the 12th International Conference on Risks and Security of Internet and Systems (CRISIS 2017), Dinard.

S. Bhandari, F. Herbreteau, V. Laxmi, A. Zemmari, P. S. Roop, M. S. Gaur. SneakLeak: Detecting Multipartite Leakage Paths in Android Apps. TrustCom/BigDataSE/ICESS 2017: 285-292.

V. Jain, S. Bhandari, V. Laxmi, M. S. Gaur, M. Mosbah. SniffDroid: Detection of Inter-App Privacy Leaks in Android. TrustCom/BigDataSE/ICESS 2017: 331-338.

S. Bhandari, F. Herbreteau, V. Laxmi, A. Zemmari, P. S. Roop, M. S. Gaur. POSTER: Detecting Inter-App Information Leakage Paths. AsiaCCS 2017: 908-910.

M. F. Atig, A. Bouajjani, K. Narayan Kumar, P. Saivasan. Verification of Asynchronous Programs with Nested Locks. FSTTCS 2017, LIPIcs volume 93 (2018), pp. 11:1-11:14.

Hugo Gimbert. On the Control of Asynchronous Automata. FSTTCS 2017, LIPIcs volume 93 (2018), pp. 30:1-30:15.

Other papers presented at FSTTCS 2017 and ICLA 2017

Zeinab Bakhtiari, Hans van Ditmarsch, Helle Hvid Hansen. Neighbourhood Contingency Bisimulation. ICLA 2017: 48-63.

Anca Muscholl. Automated synthesis: a distributed viewpoint. Invited speaker, FSTTCS 2017, LIPIcs volume 93 (2018), pp. 3:1-3:5.

M. Blondin, A. Finkel and J. Goubault-Larrecq.  Forward Analysis for WSTS, Part III: Karp-Miller Trees. FSTTCS 2017, LIPIcs volume 93 (2018), pp. 16:1-16:5.

S. Demri, E. Lozes, D. Lugiez. On Symbolic Heaps Modulo Permission Theories. FSTTCS 2017, LIPIcs volume 93 (2018), pp. 25:1-25:14.