scala.tools.nsc.transform.patmat.Solving.CNF

TransformToCnf

class TransformToCnf extends CnfBuilder

Plaisted transformation: used for conversion of a propositional formula into conjunctive normal form (CNF) (input format for SAT solver). A simple conversion into CNF via Shannon expansion would also be possible but it's worst-case complexity is exponential (in the number of variables) and thus even simple problems could become untractable. The Plaisted transformation results in an _equisatisfiable_ CNF-formula (it generates auxiliary variables) but runs with linear complexity. The common known Tseitin transformation uses bi-implication, whereas the Plaisted transformation uses implication only, thus the resulting CNF formula has (on average) only half of the clauses of a Tseitin transformation. The Plaisted transformation uses the polarities of sub-expressions to figure out which part of the bi-implication can be omitted. However, if all sub-expressions have positive polarity (e.g., after transformation into negation normal form) then the conversion is rather simple and the pseudo-normalization via NNF increases chances only one side of the bi-implication is needed.

Source: Solving.scala

Linear Supertypes

CnfBuilder, AnyRef, Any

Type Hierarchy

Ordering

Alphabetic
By Inheritance

Inherited

TransformToCnf
CnfBuilder
AnyRef
Any

Implicitly

by any2stringadd
by StringFormat
by Ensuring
by ArrowAssoc

Hide All
Show All

Visibility

Public
All

Instance Constructors

new TransformToCnf(symbolMapping: SymbolMapping)

Value Members

final def !=(arg0: Any): Boolean

Definition Classes
AnyRef → Any
final def ##(): Int

Definition Classes
AnyRef → Any
def +(other: String): String

Implicit
This member is added by an implicit conversion from TransformToCnf to any2stringadd[TransformToCnf] performed by method any2stringadd in scala.Predef.
Definition Classes
any2stringadd
def ->[B](y: B): (TransformToCnf, B)

Implicit
This member is added by an implicit conversion from TransformToCnf to ArrowAssoc[TransformToCnf] performed by method ArrowAssoc in scala.Predef.
Definition Classes
ArrowAssoc
Annotations
@inline()
final def ==(arg0: Any): Boolean

Definition Classes
AnyRef → Any
def addClauseProcessed(clause: Clause): Unit

Definition Classes
CnfBuilder
def apply(p: CNF.Prop): Solvable
final def asInstanceOf[T0]: T0

Definition Classes
Any
def buildCnf: Array[Clause]

Definition Classes
CnfBuilder
def clone(): AnyRef

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( ... )
def constFalse: Lit

Definition Classes
CnfBuilder
lazy val constTrue: Lit

Definition Classes
CnfBuilder
def convertSym(sym: CNF.Sym): Lit
def ensuring(cond: (TransformToCnf) ⇒ Boolean, msg: ⇒ Any): TransformToCnf

Implicit
This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
def ensuring(cond: (TransformToCnf) ⇒ Boolean): TransformToCnf

Implicit
This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
def ensuring(cond: Boolean, msg: ⇒ Any): TransformToCnf

Implicit
This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
def ensuring(cond: Boolean): TransformToCnf

Implicit
This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
final def eq(arg0: AnyRef): Boolean

Definition Classes
AnyRef
def equals(arg0: Any): Boolean

Definition Classes
AnyRef → Any
def finalize(): Unit

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( classOf[java.lang.Throwable] )
def formatted(fmtstr: String): String

Implicit
This member is added by an implicit conversion from TransformToCnf to StringFormat[TransformToCnf] performed by method StringFormat in scala.Predef.
Definition Classes
StringFormat
Annotations
@inline()
final def getClass(): Class[_]

Definition Classes
AnyRef → Any
def hashCode(): Int

Definition Classes
AnyRef → Any
def isConst(l: Lit): Boolean

Definition Classes
CnfBuilder
final def isInstanceOf[T0]: Boolean

Definition Classes
Any
var literalCount: Int

Definition Classes
TransformToCnf → CnfBuilder
final def ne(arg0: AnyRef): Boolean

Definition Classes
AnyRef
def newLiteral(): Lit
returns
new Tseitin variable

Definition Classes
CnfBuilder
final def notify(): Unit

Definition Classes
AnyRef
final def notifyAll(): Unit

Definition Classes
AnyRef
final def synchronized[T0](arg0: ⇒ T0): T0

Definition Classes
AnyRef
def toString(): String

Definition Classes
AnyRef → Any
final def wait(): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
final def wait(arg0: Long, arg1: Int): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
final def wait(arg0: Long): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
def →[B](y: B): (TransformToCnf, B)

Implicit
This member is added by an implicit conversion from TransformToCnf to ArrowAssoc[TransformToCnf] performed by method ArrowAssoc in scala.Predef.
Definition Classes
ArrowAssoc

Inherited from CnfBuilder

Value Members

def addClauseProcessed(clause: Clause): Unit

Definition Classes
CnfBuilder
def buildCnf: Array[Clause]

Definition Classes
CnfBuilder
def constFalse: Lit

Definition Classes
CnfBuilder
lazy val constTrue: Lit

Definition Classes
CnfBuilder
def isConst(l: Lit): Boolean

Definition Classes
CnfBuilder
def newLiteral(): Lit
returns
new Tseitin variable

Definition Classes
CnfBuilder

Inherited from AnyRef

Value Members

final def !=(arg0: Any): Boolean

Definition Classes
AnyRef → Any
final def ##(): Int

Definition Classes
AnyRef → Any
final def ==(arg0: Any): Boolean

Definition Classes
AnyRef → Any
def clone(): AnyRef

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( ... )
final def eq(arg0: AnyRef): Boolean

Definition Classes
AnyRef
def equals(arg0: Any): Boolean

Definition Classes
AnyRef → Any
def finalize(): Unit

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( classOf[java.lang.Throwable] )
final def getClass(): Class[_]

Definition Classes
AnyRef → Any
def hashCode(): Int

Definition Classes
AnyRef → Any
final def ne(arg0: AnyRef): Boolean

Definition Classes
AnyRef
final def notify(): Unit

Definition Classes
AnyRef
final def notifyAll(): Unit

Definition Classes
AnyRef
final def synchronized[T0](arg0: ⇒ T0): T0

Definition Classes
AnyRef
def toString(): String

Definition Classes
AnyRef → Any
final def wait(): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
final def wait(arg0: Long, arg1: Int): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
final def wait(arg0: Long): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )

Inherited from Any

Value Members

final def asInstanceOf[T0]: T0

Definition Classes
Any
final def isInstanceOf[T0]: Boolean

Definition Classes
Any

Inherited by implicit conversion any2stringadd from TransformToCnf to any2stringadd[TransformToCnf]

Value Members

def +(other: String): String

Implicit
This member is added by an implicit conversion from TransformToCnf to any2stringadd[TransformToCnf] performed by method any2stringadd in scala.Predef.
Definition Classes
any2stringadd

Inherited by implicit conversion StringFormat from TransformToCnf to StringFormat[TransformToCnf]

Value Members

def formatted(fmtstr: String): String

Implicit
This member is added by an implicit conversion from TransformToCnf to StringFormat[TransformToCnf] performed by method StringFormat in scala.Predef.
Definition Classes
StringFormat
Annotations
@inline()

Inherited by implicit conversion Ensuring from TransformToCnf to Ensuring[TransformToCnf]

Value Members

def ensuring(cond: (TransformToCnf) ⇒ Boolean, msg: ⇒ Any): TransformToCnf

Implicit
This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
def ensuring(cond: (TransformToCnf) ⇒ Boolean): TransformToCnf

Implicit
This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
def ensuring(cond: Boolean, msg: ⇒ Any): TransformToCnf

Implicit
This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
def ensuring(cond: Boolean): TransformToCnf

Implicit
This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring

Inherited by implicit conversion ArrowAssoc from TransformToCnf to ArrowAssoc[TransformToCnf]

Value Members

def ->[B](y: B): (TransformToCnf, B)

Implicit
This member is added by an implicit conversion from TransformToCnf to ArrowAssoc[TransformToCnf] performed by method ArrowAssoc in scala.Predef.
Definition Classes
ArrowAssoc
Annotations
@inline()
def →[B](y: B): (TransformToCnf, B)

Implicit
This member is added by an implicit conversion from TransformToCnf to ArrowAssoc[TransformToCnf] performed by method ArrowAssoc in scala.Predef.
Definition Classes
ArrowAssoc

Ungrouped

final def !=(arg0: Any): Boolean

Definition Classes
AnyRef → Any
final def ##(): Int

Definition Classes
AnyRef → Any
def +(other: String): String

Implicit
This member is added by an implicit conversion from TransformToCnf to any2stringadd[TransformToCnf] performed by method any2stringadd in scala.Predef.
Definition Classes
any2stringadd
def ->[B](y: B): (TransformToCnf, B)

Implicit
This member is added by an implicit conversion from TransformToCnf to ArrowAssoc[TransformToCnf] performed by method ArrowAssoc in scala.Predef.
Definition Classes
ArrowAssoc
Annotations
@inline()
final def ==(arg0: Any): Boolean

Definition Classes
AnyRef → Any
def addClauseProcessed(clause: Clause): Unit

Definition Classes
CnfBuilder
def apply(p: CNF.Prop): Solvable
final def asInstanceOf[T0]: T0

Definition Classes
Any
def buildCnf: Array[Clause]

Definition Classes
CnfBuilder
def clone(): AnyRef

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( ... )
def constFalse: Lit

Definition Classes
CnfBuilder
lazy val constTrue: Lit

Definition Classes
CnfBuilder
def convertSym(sym: CNF.Sym): Lit
def ensuring(cond: (TransformToCnf) ⇒ Boolean, msg: ⇒ Any): TransformToCnf

Implicit
This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
def ensuring(cond: (TransformToCnf) ⇒ Boolean): TransformToCnf

Implicit
This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
def ensuring(cond: Boolean, msg: ⇒ Any): TransformToCnf

Implicit
This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
def ensuring(cond: Boolean): TransformToCnf

Implicit
This member is added by an implicit conversion from TransformToCnf to Ensuring[TransformToCnf] performed by method Ensuring in scala.Predef.
Definition Classes
Ensuring
final def eq(arg0: AnyRef): Boolean

Definition Classes
AnyRef
def equals(arg0: Any): Boolean

Definition Classes
AnyRef → Any
def finalize(): Unit

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( classOf[java.lang.Throwable] )
def formatted(fmtstr: String): String

Implicit
This member is added by an implicit conversion from TransformToCnf to StringFormat[TransformToCnf] performed by method StringFormat in scala.Predef.
Definition Classes
StringFormat
Annotations
@inline()
final def getClass(): Class[_]

Definition Classes
AnyRef → Any
def hashCode(): Int

Definition Classes
AnyRef → Any
def isConst(l: Lit): Boolean

Definition Classes
CnfBuilder
final def isInstanceOf[T0]: Boolean

Definition Classes
Any
var literalCount: Int

Definition Classes
TransformToCnf → CnfBuilder
final def ne(arg0: AnyRef): Boolean

Definition Classes
AnyRef
def newLiteral(): Lit
returns
new Tseitin variable

Definition Classes
CnfBuilder
final def notify(): Unit

Definition Classes
AnyRef
final def notifyAll(): Unit

Definition Classes
AnyRef
final def synchronized[T0](arg0: ⇒ T0): T0

Definition Classes
AnyRef
def toString(): String

Definition Classes
AnyRef → Any
final def wait(): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
final def wait(arg0: Long, arg1: Int): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
final def wait(arg0: Long): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
def →[B](y: B): (TransformToCnf, B)

Implicit
This member is added by an implicit conversion from TransformToCnf to ArrowAssoc[TransformToCnf] performed by method ArrowAssoc in scala.Predef.
Definition Classes
ArrowAssoc

Packages

TransformToCnf 

class TransformToCnf extends CnfBuilder

Instance Constructors

Value Members

Inherited from CnfBuilder

Value Members

Inherited from AnyRef

Value Members

Inherited from Any

Value Members

Inherited by implicit conversion any2stringadd from TransformToCnf to any2stringadd[TransformToCnf]

Value Members

Inherited by implicit conversion StringFormat from TransformToCnf to StringFormat[TransformToCnf]

Value Members

Inherited by implicit conversion Ensuring from TransformToCnf to Ensuring[TransformToCnf]

Value Members

Inherited by implicit conversion ArrowAssoc from TransformToCnf to ArrowAssoc[TransformToCnf]

Value Members

Ungrouped

TransformToCnf