Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science
LICS, 2012.

@proceedings{LICS-2012,
	address       = "Dubrovnik, Croatia",
	ee            = "http://www.computer.org/csdl/proceedings/lics/2012/4769/00/index.html",
	isbn          = "978-1-4673-2263-8",
	publisher     = "{IEEE Computer Society}",
	title         = "{Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science}",
	year          = 2012,
}

Contents (66 items)

12 ×#logic
7 ×#automaton
6 ×#first-order
6 ×#game studies
5 ×#bound
5 ×#on the
5 ×#probability
4 ×#complexity
4 ×#higher-order
4 ×#problem

LICS-2012-Aumann #game studies #induction

Backward induction in games of perfect information (RJA), p. 1.

LICS-2012-Constable #on the

On Building Constructive Formal Theories of Computation Noting the Roles of Turing, Church, and Brouwer (RLC), pp. 2–8.

LICS-2012-Feigenbaum #privacy

Privacy, Anonymity, and Accountability in Ad-Supported Services (JF), pp. 9–10.

LICS-2012-Levin #internet #what

Turing’s Password: What Internet Cannot Leak (LAL), p. 11.

LICS-2012-Klop #term rewriting #λ-calculus

Term Rewriting and λ Calculus (JWK), p. 12.

LICS-2012-Platzer #logic

Logics of Dynamical Systems (AP), pp. 13–24.

LICS-2012-Berkholz #bound #game studies #testing

Lower Bounds for Existential Pebble Games and k-Consistency Tests (CB), pp. 25–34.

LICS-2012-AbdullaAS #automaton

Dense-Timed Pushdown Automata (PAA, MFA, JS), pp. 35–44.

LICS-2012-AdamekMBL #monad #set

Coproducts of Monads on Set (JA, SM, NB, PBL), pp. 45–54.

LICS-2012-AgrawalAGT #approximate #markov #verification

Approximate Verification of the Symbolic Dynamics of Markov Chains (MA, SA, BG, PST), pp. 55–64.

LICS-2012-AlurFT #infinity #string

Regular Transformations of Infinite Strings (RA, EF, AT), pp. 65–74.

LICS-2012-Atkey #parsing #semantics

The Semantics of Parsing with Semantic Actions (RA), pp. 75–84.

LICS-2012-AvronKZ #calculus #composition #logic

Modular Construction of Cut-free Sequent Calculi for Paraconsistent Logics (AA, BK, AZ), pp. 85–94.

LICS-2012-AwodeyGS #induction #type system

Inductive Types in Homotopy Type Theory (SA, NG, KS), pp. 95–104.

LICS-2012-BaeldeN #deduction #fixpoint #logic

Combining Deduction Modulo and Logics of Fixed-Point Definitions (DB, GN), pp. 105–114.

LICS-2012-BarceloFL #graph #logic #problem

Graph Logics with Rational Relations and the Generalized Intersection Problem (PB, DF, LL), pp. 115–124.

LICS-2012-BartoKW #bound #constraints

Near Unanimity Constraints Have Bounded Pathwidth Duality (LB, MK, RW), pp. 125–134.

LICS-2012-BernardyM #parametricity

A Computational Interpretation of Parametricity (JPB, GM), pp. 135–144.

LICS-2012-BienvenuM #revisited

Von Neumann’s Biased Coin Revisited (LB, BM), pp. 145–154.

LICS-2012-BundalaOW #bound #model checking #on the

On the Magnitude of Completeness Thresholds in Bounded Model Checking (DB, JO, JW), pp. 155–164.

LICS-2012-CarayolS #automaton #effectiveness #equivalence #recursion #safety

Collapsible Pushdown Automata and Labeled Recursion Schemes: Equivalence, Safety and Effective Selection (AC, OS), pp. 165–174.

LICS-2012-ChatterjeeD #game studies #how #probability

Partial-Observation Stochastic Games: How to Win When Belief Fails (KC, LD), pp. 175–184.

LICS-2012-ChatterjeeT #automaton #decidability #infinity #probability #problem #word

Decidable Problems for Probabilistic Automata on Infinite Words (KC, MT), pp. 185–194.

LICS-2012-ChatterjeeV #automaton #game studies

Mean-Payoff Pushdown Games (KC, YV), pp. 195–204.

LICS-2012-ChenD #quantifier

Decomposing Quantified Conjunctive (or Disjunctive) Formulas (HC, VD), pp. 205–214.

LICS-2012-ChenM #algebra #category theory #constraints #quantifier #theorem

An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction (HC, MM), pp. 215–224.

LICS-2012-ChenF #on the #order

On the Ordered Conjecture (YC, JF), pp. 225–234.

LICS-2012-ClairambaultGW #concurrent #game studies

The Winning Ways of Concurrent Games (PC, JG, GW), pp. 235–244.

LICS-2012-CoeckeDKW #category theory #quantum

Strong Complementarity and Non-locality in Categorical Quantum Mechanics (BC, RD, AK, QW), pp. 245–254.

LICS-2012-CreusGGR #problem

The HOM Problem is EXPTIME-Complete (CC, AG, GG, LR), pp. 255–264.

LICS-2012-ElberfeldGT #first-order #higher-order #logic #monad

Where First-Order and Monadic Second-Order Logic Coincide (ME, MG, TT), pp. 265–274.

LICS-2012-EngelmannKS #first-order #higher-order #model checking #monad

First-Order and Monadic Second-Order Model-Checking on Ordered Structures (VE, SK, SS), pp. 275–284.

LICS-2012-EsparzaGM #bound #verification

A Perfect Model for Bounded Verification (JE, PG, RM), pp. 285–294.

LICS-2012-FijalkowGO #automaton #probability #problem

Deciding the Value 1 Problem for Probabilistic Leaktight Automata (NF, HG, YO), pp. 295–304.

LICS-2012-GaoAC

Delta-Decidability over the Reals (SG, JA, EMC), pp. 305–314.

LICS-2012-GargGN #calculus #logic #multi

Countermodels from Sequent Calculi in Multi-Modal Logics (DG, VG, SN), pp. 315–324.

LICS-2012-GollerJL #complexity #first-order

The Complexity of Decomposing Modal and First-Order Theories (SG, JCJ, ML), pp. 325–334.

LICS-2012-GrabmayerEHKM #automation #sequence

Automatic Sequences and Zip-Specifications (CG, JE, DH, JWK, LSM), pp. 335–344.

LICS-2012-GrigorieffV #algorithm #bound #using

Functionals Using Bounded Information and the Dynamics of Algorithms (SG, PV), pp. 345–354.

LICS-2012-HaddadSS #complexity #petri net #recursion

The Ordinal-Recursive Complexity of Timed-arc Petri Nets, Data Nets, and Other Enriched Nets (SH, SS, PS), pp. 355–364.

LICS-2012-Herbelin #logic #proving

A Constructive Proof of Dependent Choice, Compatible with Classical Logic (HH), pp. 365–374.

LICS-2012-HerbreteauSW #abstraction #automaton

Better Abstractions for Timed Automata (FH, BS, IW), pp. 375–384.

LICS-2012-Hoshino #call-by #combinator #semantics

Step Indexed Realizability Semantics for a Call-by-Value Language Based on Basic Combinatorial Objects (NH), pp. 385–394.

LICS-2012-JaberTS #type system

Extending Type Theory with Forcing (GJ, NT, MS), pp. 395–404.

LICS-2012-JainMS #complexity

The Complexity of Verbal Languages over Groups (SJ, AM, FS), pp. 405–414.

LICS-2012-Jancar #decidability #equivalence #first-order

Decidability of DPDA Language Equivalence via First-Order Grammars (PJ), pp. 415–424.

LICS-2012-JeanninK

Capsules and Separation (JBJ, DK), pp. 425–430.

LICS-2012-KieronskiMPT #equivalence #first-order #logic

Two-Variable First-Order Logic with Equivalence Closure (EK, JM, IPH, LT), pp. 431–440.

LICS-2012-KomuravelliPC #learning #probability

Learning Probabilistic Systems from Tree Samples (AK, CSP, EMC), pp. 441–450.

LICS-2012-KrebsS #first-order

Non-definability of Languages by Generalized First-order Formulas over (N, +) (AK, AVS), pp. 451–460.

LICS-2012-McIverMM #information management #nondeterminism #probability

A Kantorovich-Monadic Powerdomain for Information Hiding, with Probability and Nondeterminism (AM, LM, CM), pp. 461–470.

LICS-2012-Mazza #λ-calculus

An Infinitary Affine λ-Calculus Isomorphic to the Full λ-Calculus (DM), pp. 471–480.

LICS-2012-Mellies #diagrams #game studies #semantics #string

Game Semantics in String Diagrams (PAM), pp. 481–490.

LICS-2012-MichaliszynO #decidability #logic

Decidable Elementary Modal Logics (JM, JO), pp. 491–500.

LICS-2012-MullerT #random

Short Propositional Refutations for Dense Random 3CNF Formulas (SM, IT), pp. 501–510.

LICS-2012-Nigam #complexity #linear #logic #on the

On the Complexity of Linear Authorization Logics (VN), pp. 511–520.

LICS-2012-Parys #on the

On the Significance of the Collapse Operation (PP), pp. 521–530.

LICS-2012-PierardS #calculus #distributed #higher-order

A Higher-Order Distributed Calculus with Name Creation (AP, ES), pp. 531–540.

LICS-2012-Platzer12a #hybrid #proving

The Complete Proof Theory of Hybrid Systems (AP), pp. 541–550.

LICS-2012-RabinovichR #branch

Interpretations in Trees with Countably Many Branches (AR, SR), pp. 551–560.

LICS-2012-SabelS #concurrent #haskell

Conservative Concurrency in Haskell (DS, MSS), pp. 561–570.

LICS-2012-SchalkS #linear #logic #modelling #multi

Constructing Fully Complete Models for Multiplicative Linear Logic (AS, HPS), pp. 571–580.

LICS-2012-Schuster #algebra #case study #induction

Induction in Algebra: A First Case Study (PS), pp. 581–585.

LICS-2012-Tan #automaton #order

An Automata Model for Trees with Ordered Data Values (TT), pp. 586–595.

LICS-2012-TraytelPB #category theory #composition #data type #higher-order #logic #proving #theorem proving

Foundational, Compositional (Co)datatypes for Higher-Order Logic: Category Theory Applied to Theorem Proving (DT, AP, JCB), pp. 596–605.

LICS-2012-Vicary #protocol #quantum #semantics

Higher Semantics of Quantum Protocols (JV), pp. 606–615.