On the complexity of Boolean unification

DOI10.1016/S0020-0190(98)00106-9MaRDI QIDQ293360zbMATH OpenOpenAlexWikidataFDO

Authors Franz Baader

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098001069?np=y

zbMATH Keywords

computational complexityautomatic theorem proving

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Boolean unification - the story so far
• Unification in Boolean rings
• Boolean unification with predicates
• scientific article; zbMATH DE number 4016225
• Unification in Boolean rings and Abelian groups

Cites work

• scientific article; zbMATH DE number 3930347 (Why is no real title available?)
• scientific article; zbMATH DE number 3501560 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• A resolution principle for a logic with restricted quantifiers
• AC-superposition with constraints: no AC-unifiers needed
• Boolean unification - the story so far
• Complexity of Boolean algebras
• Embedding Boolean expressions into logic programming
• Model theory.
• Two-Processor Scheduling with Start-Times and Deadlines
• Unification algorithms cannot be combined in polynomial time
• Unification in Boolean rings
• Unification in Boolean rings and Abelian groups
• Unification in a combination of arbitrary disjoint equational theories
• Unification in the union of disjoint equational theories: Combining decision procedures

Cited in

(16)

• Primitivity, uniform minimality, and state complexity of Boolean operations
• Boolean functional synthesis: hardness and practical algorithms
• Algorithmic introduction of quantified cuts
• scientific article; zbMATH DE number 16457 (Why is no real title available?)
• On the parameterized complexity of associative and commutative unification
• Towards Parallel Boolean Functional Synthesis
• Boolean unification with predicates
• scientific article; zbMATH DE number 4049133 (Why is no real title available?)
• Unification in Boolean rings and Abelian groups
• Embedding Boolean expressions into logic programming
• Unification in Boolean rings
• Boolean unification - the story so far
• Lost in translation: language independence in propositional logic -- application to belief change
• Finitariness of elementary unification in Boolean region connection calculus
• On complexity of the anti-unification problem
• Contact logic is finitary for unification with constants

This page was built for publication: On the complexity of Boolean unification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293360)