Advances in Programming Language Semantics and Verification

The field of programming language semantics and verification is witnessing significant developments, with a focus on innovative approaches to reasoning about loops, linear logic, and catalytic computation. Researchers are exploring new perspectives on assigning meaning to proofs, simplifying the theory of loops, and settling open questions in catalytic computation. Notable papers in this area include those that propose a proof-theoretic approach to the semantics of classical linear logic, collapse catalytic classes, and introduce a game-based approach to model-checking for HyperQPTL. These advancements have the potential to improve the efficiency and effectiveness of programming language verification and validation. Noteworthy papers include:

  • A paper that proposes a proof-theoretic approach to the semantics of classical linear logic, extending the framework to the classical case and presenting a proof-theoretic approach to the semantics of the multiplicative-additive fragment of linear logic.
  • A paper that collapses catalytic classes, giving an optimal reduction from catalytic space with additional resources to the corresponding non-catalytic space classes and settling almost all questions regarding randomized and non-deterministic catalytic computation.

Sources

The nature of loops in programming

A Proof-Theoretic Approach to the Semantics of Classical Linear Logic

Collapsing Catalytic Classes

Nondeterminism makes unary 1-limited automata concise

The Complexity of Generalized HyperLTL with Stuttering and Contexts

Prophecies all the Way: Game-based Model-Checking for HyperQPTL beyond $\forall^*\exists^*$

Counterexample-Guided Abstraction Refinement for Generalized Graph Transformation Systems (Full Version)

Products of Recursive Programs for Hypersafety Verification

Enhanced Data Race Prediction Through Modular Reasoning

Automata for the commutative closure of regular sets

Directed First-Order Logic

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs

Canonicity for Cost-Aware Logical Framework via Synthetic Tait Computability

Anonymous Public Announcements

Built with on top of