26. LICS 2012: Dubrovnik, Croatia
Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, Dubrovnik, Croatia, June 25-28, 2012. IEEE 2012 ISBN 978-1-4673-2263-8
Invited Papers
Robert J. Aumann: Backward induction in games of perfect information. 1
Robert L. Constable: On Building Constructive Formal Theories of Computation Noting the Roles of Turing, Church, and Brouwer. 2-8
Joan Feigenbaum: Privacy, Anonymity, and Accountability in Ad-Supported Services. 9-10
Leonid A. Levin: Turing's Password: What Internet Cannot Leak. 11
Invited Tutorials
Jan Willem Klop: Term Rewriting and Lambda Calculus. 12
André Platzer: Logics of Dynamical Systems. 13-24
Kleene Award Paper
Christoph Berkholz: Lower Bounds for Existential Pebble Games and k-Consistency Tests. 25-34
Regular Papers


Manindra Agrawal, S. Akshay, Blaise Genest, P. S. Thiagarajan: Approximate Verification of the Symbolic Dynamics of Markov Chains. 55-64
Robert Atkey: The Semantics of Parsing with Semantic Actions. 75-84
Arnon Avron, Beata Konikowska, Anna Zamansky: Modular Construction of Cut-free Sequent Calculi for Paraconsistent Logics. 85-94
David Baelde, Gopalan Nadathur: Combining Deduction Modulo and Logics of Fixed-Point Definitions. 105-114
Pablo Barceló, Diego Figueira, Leonid Libkin: Graph Logics with Rational Relations and the Generalized Intersection Problem. 115-124
Libor Barto, Marcin Kozik, Ross Willard: Near Unanimity Constraints Have Bounded Pathwidth Duality. 125-134

Daniel Bundala, Joël Ouaknine, James Worrell: On the Magnitude of Completeness Thresholds in Bounded Model Checking. 155-164
Arnaud Carayol, Olivier Serre: Collapsible Pushdown Automata and Labeled Recursion Schemes: Equivalence, Safety and Effective Selection. 165-174
Krishnendu Chatterjee, Laurent Doyen: Partial-Observation Stochastic Games: How to Win When Belief Fails. 175-184
Krishnendu Chatterjee, Mathieu Tracol: Decidable Problems for Probabilistic Automata on Infinite Words. 185-194

Hubie Chen, Moritz Müller: An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction. 215-224

Bob Coecke, Ross Duncan, Aleks Kissinger, Quanlong Wang: Strong Complementarity and Non-locality in Categorical Quantum Mechanics. 245-254
Carles Creus, Adria Gascón, Guillem Godoy, Lander Ramos: The HOM Problem is EXPTIME-Complete. 255-264
Michael Elberfeld, Martin Grohe, Till Tantau: Where First-Order and Monadic Second-Order Logic Coincide. 265-274
Viktor Engelmann, Stephan Kreutzer, Sebastian Siebertz: First-Order and Monadic Second-Order Model-Checking on Ordered Structures. 275-284
Nathanaël Fijalkow, Hugo Gimbert, Youssouf Oualhadj: Deciding the Value 1 Problem for Probabilistic Leaktight Automata. 295-304
Deepak Garg, Valerio Genovese, Sara Negri: Countermodels from Sequent Calculi in Multi-Modal Logics. 315-324
Stefan Göller, Jean Christoph Jung, Markus Lohrey: The Complexity of Decomposing Modal and First-Order Theories. 325-334
Clemens Grabmayer, Jörg Endrullis, Dimitri Hendriks, Jan Willem Klop, Lawrence S. Moss: Automatic Sequences and Zip-Specifications. 335-344
Serge Grigorieff, Pierre Valarcher: Functionals Using Bounded Information and the Dynamics of Algorithms. 345-354
Serge Haddad, Sylvain Schmitz, Philippe Schnoebelen: The Ordinal-Recursive Complexity of Timed-arc Petri Nets, Data Nets, and Other Enriched Nets. 355-364
Hugo Herbelin: A Constructive Proof of Dependent Choice, Compatible with Classical Logic. 365-374
Frédéric Herbreteau, B. Srivathsan, Igor Walukiewicz: Better Abstractions for Timed Automata. 375-384
Naohiko Hoshino: Step Indexed Realizability Semantics for a Call-by-Value Language Based on Basic Combinatorial Objects. 385-394
Sanjay Jain, Alexei Miasnikov, Frank Stephan: The Complexity of Verbal Languages over Groups. 405-414
Petr Jancar: Decidability of DPDA Language Equivalence via First-Order Grammars. 415-424
Emanuel Kieronski, Jakub Michaliszyn, Ian Pratt-Hartmann, Lidia Tendera: Two-Variable First-Order Logic with Equivalence Closure. 431-440
Anvesh Komuravelli, Corina S. Pasareanu, Edmund M. Clarke: Learning Probabilistic Systems from Tree Samples. 441-450
Andreas Krebs, A. V. Sreejith: Non-definability of Languages by Generalized First-order Formulas over (N, +). 451-460
Annabelle McIver, Larissa Meinicke, Carroll Morgan: A Kantorovich-Monadic Powerdomain for Information Hiding, with Probability and Nondeterminism. 461-470
Damiano Mazza: An Infinitary Affine Lambda-Calculus Isomorphic to the Full Lambda-Calculus. 471-480
Paul-André Melliès: Game Semantics in String Diagrams. 481-490
Sebastian Müller, Iddo Tzameret: Short Propositional Refutations for Dense Random 3CNF Formulas. 501-510
Vivek Nigam: On the Complexity of Linear Authorization Logics. 511-520
Pawel Parys: On the Significance of the Collapse Operation. 521-530
André Platzer: The Complete Proof Theory of Hybrid Systems. 541-550

Andrea Schalk, Hugh Steele: Constructing Fully Complete Models for Multiplicative Linear Logic. 571-580
Peter Schuster: Induction in Algebra: A First Case Study. 581-585
Tony Tan: An Automata Model for Trees with Ordered Data Values. 586-595
Dmitriy Traytel, Andrei Popescu, Jasmin Christian Blanchette: Foundational, Compositional (Co)datatypes for Higher-Order Logic: Category Theory Applied to Theorem Proving. 596-605
Jamie Vicary: Higher Semantics of Quantum Protocols. 606-615



