Sujata Ghosh Sanjiva Prasad (Eds.) 9 1 Logic and 1 0 1 S Its Applications C N L 7th Indian Conference, ICLA 2017 Kanpur, India, January 5–7, 2017 Proceedings 123 Lecture Notes in Computer Science 10119 Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen Editorial Board David Hutchison, UK Takeo Kanade, USA Josef Kittler, UK Jon M. Kleinberg, USA Friedemann Mattern, Switzerland John C. Mitchell, USA Moni Naor, Israel C. Pandu Rangan, India Bernhard Steffen, Germany Demetri Terzopoulos, USA Doug Tygar, USA Gerhard Weikum, Germany FoLLI Publications on Logic, Language and Information Subline of Lectures Notes in Computer Science Subline Editors-in-Chief Valentin Goranko, Stockholm University, Sweden Michael Moortgat, Utrecht University, The Netherlands Subline Area Editors Nick Bezhanishvili, University of Amsterdam, The Netherlands Anuj Dawar, University of Cambridge, UK Philippe de Groote, Inria Nancy, France Gerhard Jäger, University of Tübingen, Germany Fenrong Liu, Tsinghua University, Beijing, China Eric Pacuit, University of Maryland, USA Ruy de Queiroz, Universidade Federal de Pernambuco, Brazil Ram Ramanujam, Institute of Mathematical Sciences, Chennai, India More information about this series at http://www.springer.com/series/7407 Sujata Ghosh Sanjiva Prasad (Eds.) (cid:129) Logic and Its Applications 7th Indian Conference, ICLA 2017 – Kanpur, India, January 5 7, 2017 Proceedings 123 Editors Sujata Ghosh Sanjiva Prasad Indian Statistical Institute Indian Institute of Technology Delhi Chennai, Tamil Nadu NewDelhi India India ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notesin Computer Science ISBN 978-3-662-54068-8 ISBN978-3-662-54069-5 (eBook) DOI 10.1007/978-3-662-54069-5 LibraryofCongressControlNumber:2016959632 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©Springer-VerlagGmbHGermany2017 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartofthe material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodologynow knownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbookare believedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsortheeditors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissionsthatmayhavebeenmade. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringer-VerlagGmbHGermany Theregisteredcompanyaddressis:HeidelbergerPlatz3,14197Berlin,Germany Preface The seventh edition of the Indian Conference on Logic and Its Applications (ICLA 2017) was held during January 5–7, 2017 at IIT Kanpur. Co-located with the con- ferencewasthenintheditionoftheMethodsforModalitiesWorkshop(M4M-9),held during January 8–9, 2017. This volume contains the papers that were accepted for publication and presentation at ICLA 2017. The ICLA is a biennial conference organized under the aegis of ALI, the Associ- ation for Logic in India. The aim of this conference series is to bring together researchersfromawidevarietyoffieldsinwhichformallogicplaysasignificantrole. Areasofinterestincludemathematicalandphilosophicallogic,computersciencelogic, foundations and philosophy of mathematics and the sciences, use of formal logic in areas of theoretical computer science and artificial intelligence, logic and linguistics, andtherelationshipbetweenlogicandotherbranchesofknowledge.Ofspecialinterest are studies in systems of logic in the Indian tradition, and historical research on logic. We received 34 submissions this year. Each submission was reviewed by at least three Program Committee members, and by external experts in some cases. We thank allthosewhosubmittedpaperstoICLA2017.Aftergoingthroughthedetailedreviews and having extensive discussions on each paper, the Program Committee decided to accept 13 papers for publication and presentation. These contributions range over a varied set of themes including proof theory, model theory, automata theory, modal logics, algebraic logics, and Indian systems. In addition, the authors of some other submissions wereinvitedtoparticipateintheconferenceandtopresent theirideasfor discussion.WewouldliketoextendourgratitudetotheProgramCommitteemembers fortheirhardwork,patience,andknowledgeinputtingtogetheranexcellenttechnical program. We also extend our thanks to the external reviewers for their efforts in providing expert opinions and valuable feedback to the authors. The program also included four invited talks. We are grateful to Nicholas Asher, NatashaDobrinen,LukeOng,andRichardZachforacceptingourinvitationtospeakat ICLA 2017 and for contributing to this proceedings volume. We would like to express our appreciation of the Department of Mathematics and the Department of Computer Science and Engineering at IIT Kanpur for hosting the conference. Special thanks are due to Anil Seth, Mohua Banerjee, Sunil Simon, and othermembersoftheOrganizingCommitteefortheircommitmentandeffort,andtheir excellent arrangements in the smooth running of the conference. We also express our appreciation of the tireless efforts of all the volunteers who contributed to making the conference a success. The putting together of the technical program was immensely facilitated by the EasyChair conference management software, which we used from managing the submissions to producing these proceedings. VI Preface We would like to thank the Association for Symbolic Logic for supporting the conference. Finally, we are grateful to the Editorial Board at Springer for publishing this volume in the LNCS series. November 2016 Sujata Ghosh Sanjiva Prasad Organization Program Committee Natasha Alechina University of Nottingham, UK Maria Aloni University of Amsterdam, The Netherlands Steve Awodey Carnegie Mellon University, Pittsburgh, USA Mohua Banerjee Indian Institute of Technology Kanpur, India Patricia Blanchette University of Notre Dame, USA Maria Paola Università degli Studi di Verona, Italy Bonacina Lopamudra Jadavpur University, India Choudhury Agata Ciabattoni Technische Universität Wien, Austria Anuj Dawar University of Cambridge, UK Hans van Ditmarsch LORIA, Nancy, France Sujata Ghosh Indian Statistical Institute Chennai, India Brendan Gillon McGill University, Montreal, Canada Roman Kossak City University of New York, USA S. Krishna Indian Institute of Technology Bombay, India Benedikt Löwe Universiteit van Amsterdam, The Netherlands and Universität Hamburg, Germany Gopalan Nadathur University of Minnesota, USA Satyadev Indian Institute of Technology Kanpur, India Nandakumar Alessandra Technische Universiteit Delft, The Netherlands Palmigiano Prakash Panangaden McGill University, Montreal, Canada Sanjiva Prasad Indian Institute of Technology Delhi, India R. Ramanujam Institute of Mathematical Sciences, Chennai, India Christian Retoré LIRMM University of Montpellier, France Sunil Simon Indian Institute of Technology Kanpur, India Isidora Stojanovic Jean Nicod Institute, Paris, France S.P. Suresh Chennai Mathematical Institute, India Rineke Verbrugge University of Groningen, The Netherlands Yanjing Wang Peking University, China VIII Organization Additional Reviewers Bagchi, Amitabha Lodaya, Kamal Bienvenu, Meghyn Mukhopadhyay, Partha Bilkova, Marta Majer, Ondrej Fisseni, Bernhard Narayan Kumar, K. Freschi, Elisa Paris, Jeff Greco, Giuseppe Rafiee Rad, Soroush Gupta, Gopal Sadrzadeh, Mehrnoosh Henk, Paula Sreejith, A.V. Ju, Fengkui Turaga, Prathamesh Karmakar, Samir Velázquez-Quesada, Fernando R. Kurur, Piyush Woltzenlogel Paleo, Bruno Kuznets, Roman Zanuttini, Bruno Lapenta, Serafina Contents Conversation and Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Nicholas Asher and Soumya Paul Ramsey Theory on Trees and Applications. . . . . . . . . . . . . . . . . . . . . . . . . 19 Natasha Dobrinen Automata, Logic and Games for the k-Calculus . . . . . . . . . . . . . . . . . . . . . 23 C.-H. Luke Ong Semantics and Proof Theory of the Epsilon Calculus. . . . . . . . . . . . . . . . . . 27 Richard Zach Neighbourhood Contingency Bisimulation . . . . . . . . . . . . . . . . . . . . . . . . . 48 Zeinab Bakhtiari, Hans van Ditmarsch, and Helle Hvid Hansen The Complexity of Finding Read-Once NAE-Resolution Refutations. . . . . . . 64 Hans Kleine Büning, Piotr Wojciechowski, and K. Subramani Knowing Values and Public Inspection . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Jan van Eijck, Malvin Gattinger, and Yanjing Wang Random Models for Evaluating Efficient Büchi Universality Checking . . . . . 91 Corey Fisher, Seth Fogarty, and Moshe Vardi A Substructural Epistemic Resource Logic. . . . . . . . . . . . . . . . . . . . . . . . . 106 Didier Galmiche, Pierre Kimmel, and David Pym Deriving Natural Deduction Rules from Truth Tables . . . . . . . . . . . . . . . . . 123 Herman Geuvers and Tonny Hurkens A Semantic Analysis of Stone and Dual Stone Negations with Regularity . . . 139 Arun Kumar and Mohua Banerjee AchievingWhileMaintaining:ALogicofKnowingHowwithIntermediate Constraints. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Yanjun Li and Yanjing Wang Peirce’s Sequent Proofs of Distributivity . . . . . . . . . . . . . . . . . . . . . . . . . . 168 Minghui Ma and Ahti-Veikko Pietarinen On Semantic Gamification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 Ignacio Ojea Quintana