Undecidability of admissibility in the product of two Alt logics

Philippe Balbiani (1, 2) , Cigdem Gencer (1, 3)

1 IRIT-LILaC - Logique, Interaction, Langue et Calcul
2 CNRS - Centre National de la Recherche Scientifique
3 Istanbul Aydin University

The product of two Alt logics possesses the polynomial product finite model property and its membership problem is coNP-complete. Using a reduction from an undecidable domino-tiling problem, we prove that its admissibility problem is undecidable.

Keywords: Products of two modal logics; Admissibility of inference rules; Dominotiling problems; Computability

Domains: Computer Science [cs]

Philippe Balbiani, Cigdem Gencer. Undecidability of admissibility in the product of two Alt logics. Logic Journal of the IGPL, 2023, ⟨10.1093/jigpal/jzad021⟩. ⟨hal-04307720⟩