case class TwoThreeTreePolynomialRing(variableOrdering: Ordering[Term], monomialOrdering: Ordering[IndexedSeq[(Term, Int)]]) extends PolynomialRing with Product with Serializable
A polynomial is represented as a set of monomials stored in a 2-3 Tree, the ordering is lexicographic A monomial is represented as a coefficient and a power-product. A coefficient is represented as a pair of BigDecimals for num/denom. A power product is represented densely as a list of exponents
All data-structures maintain a proof of input term = representation of data structure as Term
Representations of data structures (recursively applied on rhs):
- 3-Node (l, v1, m, v2, r) is "l + v1 + m + v2 + r"
- 2-Node (l, v, r) is "l + v + r"
- monomial (c, pp) is "c * pp"
- coefficient (num, denom) is "num / denom"
- power product [e1, ..., en] is "x1e1 * ... * xn en", where instead of "x0", we write "1" in order to avoid trouble with 00, i.e., nonzero-assumptions on x or the like
All operations on the representations update the proofs accordingly.
- Alphabetic
- By Inheritance
- TwoThreeTreePolynomialRing
- Serializable
- Serializable
- Product
- Equals
- PolynomialRing
- AnyRef
- Any
- Hide All
- Show All
- Public
- All
Instance Constructors
Type Members
-
trait
Polynomial extends AnyRef
Interface to Polynomials: - a term that keeps track of how the polynomial was constructed - a proof for the internal representation of the polynomial - arithmetic - test for zero
Interface to Polynomials: - a term that keeps track of how the polynomial was constructed - a proof for the internal representation of the polynomial - arithmetic - test for zero
- Definition Classes
- PolynomialRing
-
trait
PowerProduct extends AnyRef
- Definition Classes
- PolynomialRing
- case class Branch2(left: TreePolynomial, value: Monomial, right: TreePolynomial, prvO: Option[ProvableSig]) extends TreePolynomial with Product with Serializable
- case class Branch3(left: TreePolynomial, value1: Monomial, mid: TreePolynomial, value2: Monomial, right: TreePolynomial, prvO: Option[ProvableSig]) extends TreePolynomial with Product with Serializable
-
case class
Coefficient(num: BigDecimal, denom: BigDecimal, prvO: Option[ProvableSig] = None) extends Product with Serializable
prv: lhs = rhs lhs: input term (arbitrary, trace of construction) rhs: Divide(Number(num), Number(denom))
- case class Empty(prvO: Option[ProvableSig]) extends TreePolynomial with Product with Serializable
-
sealed
trait
Growth extends AnyRef
2-3 Tree for monomials, keeping track of proofs.
-
case class
Monomial(coeff: Coefficient, powerProduct: SparsePowerProduct, prvO: Option[ProvableSig] = None) extends Product with Serializable
prv: lhs = rhs lhs: input term (arbitrary, trace of construction) rhs: representation of
coeff*powers.map(^)
- case class SparsePowerProduct(sparse: Seq[(Term, Int)]) extends PowerProduct with Product with Serializable
- case class Sprout(sprout: Branch2) extends Growth with Product with Serializable
- case class Stay(p: TreePolynomial) extends Growth with Product with Serializable
- sealed trait TreePolynomial extends Polynomial
- final case class UnknownPolynomialImplementationException(other: TwoThreeTreePolynomialRing.Polynomial) extends RuntimeException with Product with Serializable
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
Const(num: BigDecimal): TreePolynomial
- Definition Classes
- TwoThreeTreePolynomialRing → PolynomialRing
-
def
Const(num: BigDecimal, denom: BigDecimal): TreePolynomial
- Definition Classes
- TwoThreeTreePolynomialRing → PolynomialRing
- lazy val One: TreePolynomial
-
def
Var(term: Term, power: Int): TreePolynomial
- Definition Classes
- TwoThreeTreePolynomialRing → PolynomialRing
-
def
Var(term: Term): TreePolynomial
- Definition Classes
- TwoThreeTreePolynomialRing → PolynomialRing
-
final
def
asInstanceOf[T0]: T0
- Definition Classes
- Any
-
lazy val
branch2GrowLeft: ProvableSig
- Note
for the Left case, could actually just use branch2Left
- lazy val branch2GrowRight: ProvableSig
- lazy val branch2Left: ProvableSig
- lazy val branch2Right: ProvableSig
- lazy val branch2Value: ProvableSig
- lazy val branch3GrowLeft: ProvableSig
- lazy val branch3GrowMid: ProvableSig
- lazy val branch3GrowRight: ProvableSig
- lazy val branch3Left: ProvableSig
- lazy val branch3Mid: ProvableSig
- lazy val branch3Right: ProvableSig
- lazy val branch3Value1: ProvableSig
- lazy val branch3Value2: ProvableSig
-
def
clone(): AnyRef
- Attributes
- protected[java.lang]
- Definition Classes
- AnyRef
- Annotations
- @native() @throws( ... )
- lazy val coefficientBigDecimalPrv: ProvableSig
- lazy val coefficientNegPrv: ProvableSig
- lazy val coefficientPlusPrv: ProvableSig
- lazy val coefficientTimesPrv: ProvableSig
- val constC: FuncOf
- val constCl: FuncOf
- val constCr: FuncOf
- val constF: UnitFunctional
- val constL: FuncOf
- val constLd: FuncOf
- lazy val constLemma: ProvableSig
- val constLn: FuncOf
- val constR_: FuncOf
- val constRd: FuncOf
- val constRn: FuncOf
- val constX: UnitFunctional
- lazy val divideIdentity: ProvableSig
- lazy val divideNeg: ProvableSig
- lazy val divideNumber: ProvableSig
- lazy val divideRat: ProvableSig
- lazy val emptySprout: ProvableSig
-
final
def
eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- lazy val equalReflexive: ProvableSig
- lazy val equalityBySubtraction: ProvableSig
-
def
equate(t1: Term, t2: Term): Option[ProvableSig]
- Definition Classes
- TwoThreeTreePolynomialRing → PolynomialRing
-
val
equate: DependentPositionTactic
- Definition Classes
- TwoThreeTreePolynomialRing → PolynomialRing
-
def
finalize(): Unit
- Attributes
- protected[java.lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( classOf[java.lang.Throwable] )
-
final
def
getClass(): Class[_]
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
- lazy val identityTimes: ProvableSig
-
final
def
isInstanceOf[T0]: Boolean
- Definition Classes
- Any
- lazy val minusBranch2: ProvableSig
- lazy val minusBranch3: ProvableSig
- lazy val minusEmpty: ProvableSig
- lazy val monTimesBranch2: ProvableSig
- lazy val monTimesBranch3: ProvableSig
- lazy val monTimesZero: ProvableSig
- val monomialOrdering: Ordering[IndexedSeq[(Term, Int)]]
-
lazy val
monomialTimesLemma: ProvableSig
l = cl * xls r = cr * xrs c = cl*cr xs = xls ** xrs -> l*r=c*xs
-
final
def
ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- lazy val negTimes: ProvableSig
- lazy val negateBranch2: ProvableSig
- lazy val negateBranch3: ProvableSig
- lazy val negateEmpty: ProvableSig
-
def
normalize(term: Term): ProvableSig
- Definition Classes
- TwoThreeTreePolynomialRing → PolynomialRing
-
val
normalizeAt: DependentPositionTactic
- Definition Classes
- TwoThreeTreePolynomialRing → PolynomialRing
- lazy val normalizeBranch2: ProvableSig
- lazy val normalizeBranch3: ProvableSig
- lazy val normalizeCoeff0: ProvableSig
- lazy val normalizeCoeff1: ProvableSig
- lazy val normalizeMonom0: ProvableSig
- lazy val normalizeMonomCS: ProvableSig
- lazy val normalizeMonomNCS: ProvableSig
- lazy val normalizePowers1R: ProvableSig
- lazy val normalizePowers1V: ProvableSig
- lazy val normalizePowersC1: ProvableSig
- lazy val normalizePowersCP: ProvableSig
- lazy val normalizePowersCV: ProvableSig
- lazy val normalizePowersRP: ProvableSig
- lazy val normalizePowersRV: ProvableSig
-
final
def
notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
-
final
def
notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
-
implicit
def
ofInt(i: Int): Polynomial
- Definition Classes
- PolynomialRing
-
def
ofSparse(powers: (Term, Int)*): SparsePowerProduct
- Definition Classes
- TwoThreeTreePolynomialRing → PolynomialRing
-
def
ofSparse(seq: Seq[(Term, Int)]): SparsePowerProduct
- Definition Classes
- TwoThreeTreePolynomialRing → PolynomialRing
-
def
ofTerm(t: Term): Polynomial
- Definition Classes
- PolynomialRing
- lazy val partition2: ProvableSig
- lazy val plusBranch2: ProvableSig
- lazy val plusBranch3: ProvableSig
- lazy val plusEmpty: ProvableSig
- lazy val plusMinus: ProvableSig
- lazy val plusTimes: ProvableSig
-
def
powerDivideLemma(i: Int): ProvableSig
lookup or prove lemma of the form "(x_(||) / y_(||))i = x_(||)i / y_(||)^i "
- lazy val powerEven: ProvableSig
- lazy val powerLemma: ProvableSig
- lazy val powerOdd: ProvableSig
- lazy val powerOne: ProvableSig
- lazy val powerPoly: ProvableSig
- lazy val powerZero: ProvableSig
-
def
ratForm(term: Term): (Polynomial, Polynomial, ProvableSig)
- Definition Classes
- TwoThreeTreePolynomialRing → PolynomialRing
- lazy val rationalLemma: ProvableSig
-
def
reassoc(prv: ProvableSig): ProvableSig
drop parentheses of a sum of terms on the rhs of prv to the left, e.g., t = a + (b + c) ~~> t = a + b + c
- lazy val reassocLeft0RightConst: ProvableSig
- lazy val reassocRight0: ProvableSig
- lazy val reassocRightConst: ProvableSig
- lazy val reassocRightPlus: ProvableSig
- lazy val splitBranch2: ProvableSig
- lazy val splitBranch3: ProvableSig
- lazy val splitCoefficient: ProvableSig
- def splitCoefficientNumericCondition(n: Term, d: Term, n1: Term, d1: Term, n2: Term, d2: Term): And
- lazy val splitEmpty: ProvableSig
- lazy val splitMonomial: ProvableSig
-
def
symbols(t: Term): Seq[Term]
- Definition Classes
- PolynomialRing
-
final
def
synchronized[T0](arg0: ⇒ T0): T0
- Definition Classes
- AnyRef
- lazy val timesBranch2: ProvableSig
- lazy val timesBranch3: ProvableSig
- lazy val timesEmpty: ProvableSig
- lazy val timesIdentity: ProvableSig
- lazy val timesPowers1Left: ProvableSig
- lazy val timesPowers1Right: ProvableSig
- lazy val timesPowersBoth: ProvableSig
- lazy val timesPowersLeft: ProvableSig
- lazy val timesPowersRight: ProvableSig
- lazy val varLemma: ProvableSig
- lazy val varPowerLemma: ProvableSig
- val variableOrdering: Ordering[Term]
-
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
- @native() @throws( ... )
- lazy val zez: ProvableSig
KeYmaera X: An aXiomatic Tactical Theorem Prover
KeYmaera X is a theorem prover for differential dynamic logic (dL), a logic for specifying and verifying properties of hybrid systems with mixed discrete and continuous dynamics. Reasoning about complicated hybrid systems requires support for sophisticated proof techniques, efficient computation, and a user interface that crystallizes salient properties of the system. KeYmaera X allows users to specify custom proof search techniques as tactics, execute tactics in parallel, and interface with partial proofs via an extensible user interface.
http://keymaeraX.org/
Concrete syntax for input language Differential Dynamic Logic
Package Structure
Main documentation entry points for KeYmaera X API:
edu.cmu.cs.ls.keymaerax.core
- KeYmaera X kernel, proof certificates, main data structuresExpression
- Differential dynamic logic expressions:Term
,Formula
,Program
Sequent
- Sequents of formulasProvable
- Proof certificates transformed by rules/axiomsRule
- Proof rules as well asUSubstOne
for (one-pass) uniform substitutions and renaming.StaticSemantics
- Static semantics with free and bound variable analysisKeYmaeraXParser
.edu.cmu.cs.ls.keymaerax.parser
- Parser and pretty printer with concrete syntax and notation for differential dynamic logic.KeYmaeraXPrettyPrinter
- Pretty printer producing concrete KeYmaera X syntaxKeYmaeraXParser
- Parser reading concrete KeYmaera X syntaxKeYmaeraXArchiveParser
- Parser reading KeYmaera X model and proof archive.kyx
filesDLParser
- Combinator parser reading concrete KeYmaera X syntaxDLArchiveParser
- Combinator parser reading KeYmaera X model and proof archive.kyx
filesedu.cmu.cs.ls.keymaerax.infrastruct
- Prover infrastructure outside the kernelUnificationMatch
- Unification algorithmRenUSubst
- Renaming Uniform Substitution quickly combining kernel's renaming and substitution.Context
- Representation for contexts of formulas in which they occur.Augmentors
- Augmenting formula and expression data structures with additional functionalityExpressionTraversal
- Generic traversal functionality for expressionsedu.cmu.cs.ls.keymaerax.bellerophon
- Bellerophon tactic language and tactic interpreterBelleExpr
- Tactic language expressionsSequentialInterpreter
- Sequential tactic interpreter for Bellerophon tacticsedu.cmu.cs.ls.keymaerax.btactics
- Bellerophon tactic library for conducting proofs.TactixLibrary
- Main KeYmaera X tactic library including many proof tactics.HilbertCalculus
- Hilbert Calculus for differential dynamic logicSequentCalculus
- Sequent Calculus for propositional and first-order logicHybridProgramCalculus
- Hybrid Program Calculus for differential dynamic logicDifferentialEquationCalculus
- Differential Equation Calculus for differential dynamic logicUnifyUSCalculus
- Unification-based uniform substitution calculus underlying the other calculi[edu.cmu.cs.ls.keymaerax.btactics.UnifyUSCalculus.ForwardTactic ForwardTactic]
- Forward tactic framework for conducting proofs from premises to conclusionsedu.cmu.cs.ls.keymaerax.lemma
- Lemma mechanismLemma
- Lemmas are Provables stored under a name, e.g., in files.LemmaDB
- Lemma database stored in files or database etc.edu.cmu.cs.ls.keymaerax.tools.qe
- Real arithmetic back-end solversMathematicaQETool
- Mathematica interface for real arithmetic.Z3QETool
- Z3 interface for real arithmetic.edu.cmu.cs.ls.keymaerax.tools.ext
- Extended back-ends for noncritical ODE solving, counterexamples, algebra, simplifiers, etc.Mathematica
- Mathematica interface for ODE solving, algebra, simplification, invariant generation, etc.Z3
- Z3 interface for real arithmetic including simplifiers.Entry Points
Additional entry points and usage points for KeYmaera X API:
edu.cmu.cs.ls.keymaerax.launcher.KeYmaeraX
- Command-line launcher for KeYmaera X supports command-line argument-help
to obtain usage informationedu.cmu.cs.ls.keymaerax.btactics.AxIndex
- Axiom indexing data structures with keys and recursors for canonical proof strategies.edu.cmu.cs.ls.keymaerax.btactics.DerivationInfo
- Meta-information on all derivation steps (axioms, derived axioms, proof rules, tactics) with user-interface info.edu.cmu.cs.ls.keymaerax.bellerophon.UIIndex
- Index determining which canonical reasoning steps to display on the KeYmaera X User Interface.edu.cmu.cs.ls.keymaerax.btactics.Ax
- Registry for derived axioms and axiomatic proof rules that are proved from the core.References
Full references on KeYmaera X are provided at http://keymaeraX.org/. The main references are the following:
1. André Platzer. A complete uniform substitution calculus for differential dynamic logic. Journal of Automated Reasoning, 59(2), pp. 219-265, 2017.
2. Nathan Fulton, Stefan Mitsch, Jan-David Quesel, Marcus Völp and André Platzer. KeYmaera X: An axiomatic tactical theorem prover for hybrid systems. In Amy P. Felty and Aart Middeldorp, editors, International Conference on Automated Deduction, CADE'15, Berlin, Germany, Proceedings, volume 9195 of LNCS, pp. 527-538. Springer, 2015.
3. André Platzer. Logical Foundations of Cyber-Physical Systems. Springer, 2018. Videos