Universitat de Lleida
    • English
    • català
    • español
  • English 
    • English
    • català
    • español
  • Login
Repositori Obert UdL
View Item 
  •   Home
  • Recerca
  • Informàtica i Enginyeria Industrial
  • Articles publicats (Informàtica i Enginyeria Industrial)
  • View Item
  •   Home
  • Recerca
  • Informàtica i Enginyeria Industrial
  • Articles publicats (Informàtica i Enginyeria Industrial)
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

The satisfiability problem in regular CNF-formulas

Thumbnail
View/Open
003864.pdf (319.0Kb)
Sol·licita una còpia
Issue date
1998
Author
Manyà Serres, Felip
Béjar Torres, Ramón
Escalada Imaz, G.
Suggested citation
Manyà Serres, Felip; Béjar Torres, Ramón; Escalada Imaz, G.; . (1998) . The satisfiability problem in regular CNF-formulas. Soft Computing, 1998, vol. 2, p. 116-123. https://doi.org/10.1007/s005000050042.
Impact


Web of Science logo    citations in Web of Science

Scopus logo    citations in Scopus

Google Scholar logo  Google Scholar
Share
Export to Mendeley
Metadata
Show full item record
Abstract
In this paper we deal with the propositional satisfiability (SAT) problem for a kind of multiple-valued clausal forms known as regular CNF-formulas and extend some known results from classical logic to this kind of formulas. We present a DavisÐPutnam-style satisfiability checking procedure for regular CNF-formulas equipped with suitable data structures and prove its completeness. Then, we describe a series of experiments for regular random 3-SAT instances. We observe that, for the regular 3-SAT problem with this procedure, there exists a threshold of the ratio of clauses to variables such that (i) the most computationally difficult instances tend to be found near the threshold, (ii) there is a sharp transition from satisfiable to unsatisfiable instances at the threshold and (iii) the value of the threshold increases as the number of truth values considered increases. Instances in the hard part provide benchmarks for the evaluation of regular satisfiability solvers.
URI
http://hdl.handle.net/10459.1/57193
DOI
https://doi.org/10.1007/s005000050042
Is part of
Soft Computing, 1998, vol. 2, p. 116-123
European research projects
Collections
  • Articles publicats (Informàtica i Enginyeria Industrial) [988]
  • Grup de Recerca en Energia i Intel·ligència Artificial (GREiA) (INSPIRES) [487]

Contact Us | Send Feedback | Legal Notice
© 2023 BiD. Universitat de Lleida
Metadata subjected to 
 

 

Browse

All of the repositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

Statistics

View Usage Statistics

D'interès

Política institucional d'accés obertDiposita les teves publicacionsDiposita dades de recercaSuport a la recerca

Contact Us | Send Feedback | Legal Notice
© 2023 BiD. Universitat de Lleida
Metadata subjected to