On the restricted equivalence for subclasses of propositional logic

DOI10.1051/ita/1993270403271zbMath0787.03008OpenAlexW106552629MaRDI QIDQ3142267

Hans Kleine Büning, Andreas Flögel, Theodor Lettmann

Publication date: 15 November 1993

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_1993__27_4_327_0/

zbMATH Keywords

algorithmssatisfiability problemquantified Boolean formulasclasses of propositional formulasquantified 2CNF formulasquantified definite Horn formulasrestricted equivalence problemrestricted implication problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05)

Related Items (1)

The Logical Difference Problem for Description Logic Terminologies

Cites Work

• The polynomial-time hierarchy
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Resolution for quantified Boolean formulas
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the restricted equivalence for subclasses of propositional logic