About: On CDCL-Based Proof Systems with the Ordered Decision Strategy

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: On CDCL-Based Proof Systems with the Ordered Decision Strategy Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : covidontheweb.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	On CDCL-Based Proof Systems with the Ordered Decision Strategy
Creator	Mull, Nathan Pang, Shuo Razborov, Alexander
Source	PMC
abstract	We prove that CDCL SAT-solvers with the ordered decision strategy and the DECISION learning scheme are equivalent to ordered resolution. We also prove that, by replacing this learning scheme with its opposite, which learns the first possible non-conflict clause, they become equivalent to general resolution. In both results, we allow nondeterminism in the solver’s ability to perform unit propagation, conflict analysis, and restarts in a way that is similar to previous works in the literature. To aid the presentation of our results, and possibly future research, we define a model and language for CDCL-based proof systems – particularly those with nonstandard features – that allow for succinct and precise theorem statements.
has issue date	2020-06-26(xsd:dateTime)
bibo:doi	10.1007/978-3-030-51825-7_12
has license	no-cc
sha1sum (hex)	b627862512a66f85bca765635969fc96d72662e2
schema:url	https://doi.org/10.1007/978-3-030-51825-7_12
resource representing a document's title	On CDCL-Based Proof Systems with the Ordered Decision Strategy
has PubMed Central identifier	PMC7326566
schema:publication	Theory and Applications of Satisfiability Testing - SAT 2020
resource representing a document's body	covid:b627862512a66f85bca765635969fc96d72662e2#body_text
is schema:about of	named entity 'nonstandard' named entity 'define' named entity 'theorem' named entity 'general' named entity 'FEATURES' named entity 'RESULTS' named entity 'SAT' named entity 'RESTARTS' named entity 'model' named entity 'proof systems' named entity 'CDCL' named entity 'decision strategy' named entity 'resolution proof' named entity 'injective' named entity 'CDCL' named entity 'DPLL' named entity 'recursively' named entity 'make progress' named entity 'CDCL' named entity 'transition function' named entity 'decision strategy' named entity 'finite set' named entity 'DLL' named entity 'decision strategy' named entity 'base case' named entity 'Var' named entity 'axiom' named entity 'CDCL' named entity 'finite sequence' named entity 'decision strategy' named entity 'unit propagation' named entity 'Var' named entity 'directed path' named entity 'lower and upper bounds' named entity 'CNF' named entity 'CDCL' named entity 'MINCE' named entity 'graph' named entity 'resolution proof' named entity 'CDCL' named entity 'Decision rule' named entity 'recursively' named entity 'CDCL' named entity 'Var' named entity 'Var' named entity 'unit clause' named entity 'topological order' named entity 'axiom' named entity 'resolution rule' named entity 'chosen uniformly at random' named entity 'integer' named entity 'negation' named entity 'Boolean' named entity 'decision strategy' named entity 'CDCL' named entity 'CDCL' named entity 'proof systems' named entity 'CNF' named entity 'CDCL' named entity 'Hilbert' named entity 'resolution rule' named entity 'CDCL' named entity 'CDCL' named entity 'Wigderson' named entity 'CDCL' named entity 'Var' named entity 'CDCL' named entity 'acyclic directed graph' named entity 'resolution proofs' named entity 'decision strategy' named entity 'C 1' named entity 'Var' named entity 'propositional variable' named entity 'proper subsets' named entity 'unit clause' named entity 'decision variables' named entity 'unit propagation' named entity 'proof systems' named entity 'SAT-solver' named entity 'unit propagation' named entity 'CDCL'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software