Streamlining Input/Output Logics with Sequent Calculi (Extended Abstract)

Agata Ciabattoni, Dmitry RozplokhasIJCAI 2024

Introduction

Input/Output (I/O) logics provide a formal framework for reasoning about conditional norms and causality, often expressed as "if-then" scenarios in ethics, law, and artificial intelligence. Historically, the field has been divided between "original" I/O logics, focused on normative systems, and their "causal" counterparts. This fragmentation led to gaps in proof theory, semantic clarity, and computational complexity analysis. This paper addresses these challenges by introducing a unified set of proof-search-oriented sequent calculi.

Methodology

The authors develop a modular proof theory by extending Gentzen’s classical logic (LK) with "pair elimination" rules specifically designed for causal I/O logics. A central contribution is the "Syntactic Bridge" theorem, which establishes a direct link between derivability in original I/O logics and their causal versions. This allows a single calculus to serve both families. Furthermore, characterization lemmas reduce I/O statement verification to classical logic checks, enabling efficient automated proof search.

Key Insights and Theoretical Framework

The research identifies causal logics (those including a "bottom" or contradiction axiom) as the foundational layer. By solving the proof theory for these versions first, the properties of the original logics can be derived elegantly.

Table 1: Logical properties satisfied by various I/O logic systems, highlighting the modularity of the framework.

A significant breakthrough is the universal modal embedding: all four primary I/O logics can be embedded into the "shallow" fragment of normal modal logics (e.g., K and KD). This resolves a long-standing question regarding the possibility of translating logics that lack the "reasoning by cases" (OR) rule into standard modal frameworks.

Results and Complexity Analysis

The paper settles the computational complexity for the entire family of eight logics, proving that the entailment problem is co-NP-complete. This includes OUT3, whose complexity was previously an open problem.

Table 2: Frame conditions and notions of validity for the unified I/O logic family.

The reduction of these problems to classical propositional formulas allows for the application of high-performance SAT solvers in automated reasoning. Additionally, the authors provide a uniform "possible worlds" semantics (In/Out models) that applies across the entire family, as detailed in the frame conditions above.

Conclusion and Future Directions

While this work provides a robust foundation for monotonic I/O logics, future research is needed to address non-monotonic scenarios—where new information can invalidate previous conclusions, a common occurrence in legal and causal reasoning. The streamlined monotonic framework established here serves as the necessary "solid ground" for these future extensions.

Summary updated

BibTeX
@inproceedings{ciabattoni2024streamlining,
  author = {Agata Ciabattoni and Dmitry Rozplokhas},
  title = {{Streamlining Input/Output Logics with Sequent Calculi (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure