Fundamental Logic Is Decidable

It is shown that Holliday’s propositional Fundamental Logic is decidable in polynomial time and that first-order Fundamental Logic is decidable in double-exponential time. The proof also yields a double-exponential–time decision procedure for first-order orthologic.

Saved in:
Bibliographic Details
Published in:ACM transactions on computational logic 2024-07, Vol.25 (3), p.1-14, Article 17
Main Authors: Aguilera, Juan, Bydžovský, Jan
Format: Article
Language:English
Subjects:
Complexity theory and logic
Proof theory
Theory of computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:It is shown that Holliday’s propositional Fundamental Logic is decidable in polynomial time and that first-order Fundamental Logic is decidable in double-exponential time. The proof also yields a double-exponential–time decision procedure for first-order orthologic.
ISSN:1529-3785
1557-945X
DOI:10.1145/3665328