A sharp threshold for the renameable-Horn and the q-Horn properties
From MaRDI portal
Publication:2581546
DOI10.1016/J.DAM.2005.05.005zbMATH Open1105.68096OpenAlexW2001835703MaRDI QIDQ2581546FDOQ2581546
Authors: Nadia Creignou, Hervé Daudé, John V. Franco 
Publication date: 10 January 2006
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.005
Recommendations
- The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas
- scientific article; zbMATH DE number 5244891
- A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses
- New combinatorial topology upper and lower bounds for renaming
- Unique Horn renaming and Unique 2-Satisfiability
- On the size of maximum renamable Horn sub-CNF
- New combinatorial topology bounds for renaming: the lower bound
- Sharp thresholds for constraint satisfaction problems and homomorphisms
- On renaming a set of clauses as a Horn set
- New combinatorial topology bounds for renaming: the upper bound
Cites Work
- Approximation algorithms for combinatorial problems
- Recognition of \(q\)-Horn formulae in linear time
- Renaming a Set of Clauses as a Horn Set
- Title not available (Why is that?)
- Bounded model checking using satisfiability solving
- Sharp thresholds of graph properties, and the $k$-sat problem
- Title not available (Why is that?)
- Supersaturated graphs and hypergraphs
- Generalized satisfiability problems: Minimal elements and phase transitions.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Combinatorial sharpness criterion and phase transition classification for random CSPs
- Title not available (Why is that?)
- On finding solutions for extended Horn formulas
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- A linear algorithm for renaming a set of clauses as a Horn set
- Determining computational complexity from characteristic ``phase transitions
- A threshold for unsatisfiability
- A perspective on certain polynomial-time solvable classes of satisfiability
- A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability
- Extended Horn sets in propositional logic
- Statistical mechanics methods and phase transitions in optimization problems
- Models for Random Constraint Satisfaction Problems
- A Complexity Index for Satisfiability Problems
- Sharp thresholds for certain Ramsey properties of random graphs
Cited In (4)
This page was built for publication: A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581546)
