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
Frédérique Bassino, Cyril Nicaud, Pascal Weil. Random generation of subgroups of the modular group with a fixed isomorphism type. Submitted
R. Ramanujam, Vaishnavi Sundararajan, S.P. Suresh. Solving the insecurity problem for assertions. 37th IEEE Computer Security Foundations Symposium (CSF), 2024, to appear
Ashwin Bhaskar, M. Praveen. Constraint LTL with Remote Access. Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2023, to appear.
Mallika Roy, Enric Ventura, Pascal Weil. The central tree property and algorithmic problems on subgroups of free groups. J. Group Theory, to appear.
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
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
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
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
Luc Dartois, Paul Gastin, S.N. Krishna. SD-Regular Transducer Expressions for Aperiodic Transformations. LICS 2021, 1-13. DOI: 10.1109/LICS52264.2021.9470738
S. Akshay, Blaise Genest, Loïc Hélouët, Shankara Narayanan Krishna, Sparsa Roychowdhury. Resilience of Timed Systems. Proceedings of FSTTCS 2021, LIPICs, volume 213, pages 33:1-33:22. DOI: 10.4230/LIPIcs.FSTTCS.2021.33
H. Straubing, P. Weil. Varieties. In Handbook of automata theory, vol. I (J.-É. Pin, ed.), EMS Publishing, 2021. ISBN print 978-3-98547-006-8, ISBN online 978-3-98547-506-3. DOI: 10.4171/Automata
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
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
C. Aiswarya, Benedikt Bollig, Paul Gastin. An Automata-Theoretic Approach to the Verification of Distributed Algorithms. Information and Computation, 259(3): 305-327. 2018. DOI: 10.1016/j.ic.2017.05.006
Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, Thomas Zeume. Reachability is in DynFO. J. ACM 65(5): 33:1-33:24 (2018).
S. Akshay, Paul Gastin, S.N. Krishna. Analyzing timed systems using tree automata. Logical Methods in Computer Science, 14(2): 1-35. 2018. DOI: 10.23638/LMCS-14(2:8)2018
Shweta Bhandari, R. Panihar, S. Naval, V. Laxmi, Akka Zemmari, M. S. Gaur. SWORD: Semantic AWare AndrOid MalwaRe Detector. Journal of Information Security and Applications 42: 46-56 (2018)
Prachi Goyal, Pranabendu Misra, Fahad Panolan, Geevarghese Philip and Saket Saurabh. Finding even subgraphs even faster. Journal of Computer and System Sciences 97: 1-13 (2018). DOI: 10.1016/j.jcss.2018.03.001
S. Saharan, V. Laxmi, M. S. Gaur, Akka Zemmari. Privacy Preserving Data-Computation Offloading. In Proceedings of the 13th International Conference on Risks and Security of Internet and Systems (CRISIS 2018), 2018, pages 86-92.
Samir Datta, Anish Mukherjee, Niels Vortmeier, Thomas Zeume. Reachability and distances under multiple changes. ICALP 2018: 120:1-120:14, LIPIcs. DOI: 10.4230/LIPIcs.ICALP.2018.120
Samir Datta, Raghav Kulkarni, Anish Kumar, Anish Mukherjee. Planar Maximum Matching: Towards a Parallel Algorithm, ISAAC 2018: 21:1-21:13, LIPIcs. DOI: 10.4230/LIPIcs.ISAAC.2018.21
Paul Gastin, Sayan Mukherjee, B. Srivathsan: Reachability in timed automata with diagonal constraints. In Proceedings of CONCUR 2018, volume 118 of LIPIcs, pages 28:1 – 28:17.
Mohamed Faouzi Atig, Ahmed Bouajjani, K. Narayan Kumar, Prakash Saivasan. Verifying Quantitative Temporal Properties of Procedural Programs. In Proceedings of CONCUR 2018, volume 118 of LIPIcs, pages 15:1 – 15:17.
Wojciech Czerwinski, Slawomir Lasota, Roland Meyer, Sebastian Muskalla, K. Narayan Kumar, Prakash Saivasan. Regular Separability of Well-Structured Transition Systems. In Proceedings of CONCUR 2018, volume 118 of LIPIcs. pages 35:1-35:18.
How good are Popular Matchings? In Proceedings of the 17th Symposium on Experimental Algorithms, SEA 2018, volume 103 of LIPIcs, pages 9:1-9:14.
Vrunda Dave, Paul Gastin, Shankara Narayanan Krishna. Regular Transducer Expressions for Regular Transformations. In LICS 2018: 315-324. Long version on ArXiv.
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
Samir Datta, Siddharth Iyer, Raghav Kulkarni, Anish Mukherjee. Shortest k-disjoint paths via determinants. FSTTCS 2018: 19:1-19:21, LIPIcs. DOI: 10.4230/LIPIcs.FSTTCS.2018.19
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.