fram-lang / fram-lang/dbl

Scopes of propositional variables

Open
#203 0 comments 0 reactions 0 assignees View on GitHub
2.2. sat proposal
Dominant language
OCaml
Stars
45
Forks
28
PR merge metrics
No merged PRs in 30d

Description

The SAT-solver could take advantage of the fact, that some of propositional variables have very ephemeral character and from some point they will never occur in newly added clauses. For example, variables that simplifies translation of implication to CNF (those generated by `IncrSAT.Formula.imp_to_cnf`) or variables that appear in local definitions, but don't leak to public interfaces. There are many useful simplifications that can be made with such variables. For instance, with such a variable *p*, we can do the following:
- if it has only negative occurrences — set to to false;
- if it has only positive occurrences — set to true;
- if there is only one positive occurrence, and it has a form *p* ∨ ¬*q* — set to *q*;
- it there is only one negative occurrence, and it has a form ¬*p* ∨ *q* — set to *q*.

We can also perform some simplifications on variables that will never appear positively (or negatively, respectively) in new clauses.

We can detect such variables on-line, by assigning a scope to propositional variable, and lifting it in returned types, when the scope is leaved. Alternative (and probably simpler) solution is to:
- don't care about such variables in a batch mode — we always solve all constraints anyway.
- find non-ephemeral variables by traversing the environment in a REPL mode.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.