?
Logic in Computer Science (LICS), 2015 30th Annual ACM/IEEE Symposium on
LICS 2015 Foreword This volume contains the proceedings of the Thirtieth Annual ACM/IEEE Symposium on Logic in Computer Science, an international forum on the broad range of topics that lie at the intersection of computer science and mathematical logic. LICS 2015 was held in Kyoto at the Grand Prince Hotel, from July 6th to 10th, 2015, in conjunction with the Forty-Second International Colloquium on Automata, Languages, and Programming (ICALP 2015). In addition, seven workshops were colocated with LICS 2015 and ICALP 2015: • Logic and Computational Complexity (LCC 2015) • Natural Language and Computer Science 3 (NLCS 3) • Quantum Computational Complexity (QCC) • Realistic Models for Algorithms in Wireless Networks (WRAWN) • Syntax and Semantics for Low-Level Languages (LOLA 2015) • Verification of Higher-Order Programs (HOPA) • Young Researchers Forum on Automata, Languages and Programming (YR-ICALP 2015) The program included two joint invited keynote talks (joint with ICALP 2015) by ANCA MUSCHOLL (Université Bordeaux-1) and PETER O’HEARN (Facebook and University College London), two invited keynote talks by DANIEL KIFER (Penn State University) and LUKE ONG (University of Oxford), and two invited tutorials by ANDREW PITTS (University of Cambridge) and GEOFFREY SMITH (Florida International University). The 61 contributed papers in this volume were selected from 176 submissions. Each paper was assigned to four members of the program committee. In some cases, the committee chose to consult additional reviewers, whose names are listed at the end of this volume. The program committee carried out extensive electronic discussions. On behalf of the LICS community, I would like to thank my fellow program committee members for all their very hard work selecting a high-quality program of contributed papers. I would also like to thank all external reviewers, all authors who submitted papers for consideration, and the invited and tutorial speakers. I gratefully acknowledge the use of the EasyChair conference-management system, which greatly facilitated the work of the LICS Program Committee. The Kleene Award is given in honor of the late Stephen C. Kleene for the best student paper. This year the program committee chose • “Distributed Graph Automata” by FABIAN REITER (Université Paris Diderot). Warm congratulations to the author! The LICS Symposium series has been running since 1986. The foundational nature of much of the work appearing in LICS means that often its full impact is not felt immediately. Therefore, for the last few years, a Test-of-Time Award has been made, recognizing a small number of influential papers that appeared in the LICS proceedings from 20 years prior and that have best met the “test of time”. This year, the LICS Test-of-Time Award Committee, consisting of Martin Grohe, Dexter Kozen, Dale Miller (chair), and Prasad Sistla, selected the following groundbreaking paper from the proceedings of LICS 1995: • “Completeness of Kozen’s Axiomatisation of the Propositional μ-Calculus” by IGOR WALUKIEWICZ (Université Bordeaux-1). More details about the paper and the award are at the end of this volume. The committee extends its sincere congratulations to the author. Thanks are due to Luke Ong as LICS General Chair and treasurer, Patricia Bouyer (Workshop Chair), Andrzej Murawski (Publicity Chair) and Martin Grohe (Honorary Publicity Chair) for hosting the LICS web server at Aachen. Special thanks go to the conference chair Masahito Hasegawa (Kyoto University), for the local organization of LICS 2015. I would also like to thank IEEE Conference xi Support Services Meeting Planners, Hazel Harrison and Alkenia Blackmon, for their help and advice. Furthermore, I would like to thank Kazuo Iwama (Kyoto University), conference chair of ICALP 2015, and Luca Aceto (Reykjavik University), president of the EATCS, for their advice and support. Finally, I would like to thank Naoki Kobayashi (University of Tokyo), chair of the track B of ICALP 2015, for designing the whole schedule and for his cooperation in organizing a coherent program for LICS and ICALP-B. LICS 2015 was sponsored by the IEEE Technical Committee on Mathematical Foundations of Computing and by the ACM Special Interest Group on Logic and Computation (SIGLOG), in cooperation with the Association for Symbolic Logic and the European Association for Theoretical Computer Science (EATCS). We gratefully acknowledge also the following financial sponsors: ERATO Kawarabayashi Large Graph Project, MEXT Grant-in-Aid for Scientific Research on Innovative Areas “Exploring the Limits of Computation", Research Institute for Mathematical Sciences of Kyoto University, and Tateisi Science and Technology Foundation. Catuscia Palamidessi INRIA LICS 2015 Program Chair
