STACS 2004

DOI10.1007/B96012zbMATH Open1122.68586OpenAlexW4236485840MaRDI QIDQ5309697FDOQ5309697

Authors: Elmar Böhler, Edith Hemaspaandra, Heribert Vollmer, S. Reith 

Publication date: 1 October 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b96012

Recommendations

• scientific article; zbMATH DE number 1948177
• Complexity classifications of Boolean constraint satisfaction problems
• Isomorphic implication
• Mathematical Foundations of Computer Science 2005
• On the computational complexity of some classical equivalence relations on boolean functions

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cited In (11)

• Isomorphism Testing of Boolean Functions Computable by Constant-Depth Circuits
• On the expression complexity of equivalence and isomorphism of primitive positive formulas
• Bases for Boolean co-clones
• On the isomorphism problem for decision trees and decision lists
• The complexity of equivalence and isomorphism of systems of equations over finite groups
• Isomorphic implication
• An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• Title not available (Why is that?)
• Mathematical Foundations of Computer Science 2005
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?

This page was built for publication: STACS 2004

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