Satisfiability of co-nested formulas

DOI10.1007/BF01209713MaRDI QIDQ1323332zbMATH OpenFDO

Authors Jan Kratochvíl, Mirko Křivánek

Publication date 2 June 1994

Published in Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

decidabilitysatisfiabilityco-nested formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Decidability of theories and sets of sentences (03B25)

Recommendations

• Optimization and probabilistic satisfiability on nested and co-nested formulas
• Nested satisfiability
• Strong backdoors to nested satisfiability
• On Linear CNF Formulas
• Recognition of tractable satisfiability problems through balanced polynomial representations

Cites work

• Efficient Planarity Testing
• Nested satisfiability
• Noncrossing Subgraphs in Topological Layouts
• Planar Formulae and Their Uses
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The complexity of induced minors and related problems

Cited in

(11)

• Satisfiability of mixed Horn formulas
• Planar 3-SAT with a clause/variable cycle
• Max Horn SAT and the minimum cut problem in directed hypergraphs
• scientific article; zbMATH DE number 1420799 (Why is no real title available?)
• Satisfiability of acyclic and almost acyclic CNF formulas
• Satisfiability of acyclic and almost acyclic CNF formulas
• Nested satisfiability
• Recognition of Nested Gates in CNF Formulas
• New tractable classes for default reasoning from conditional knowledge bases
• Optimization and probabilistic satisfiability on nested and co-nested formulas
• Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable

This page was built for publication: Satisfiability of co-nested formulas

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