How deduxit searches
This page explains how deduxit prove finds a proof or shows there is
none: which engine searches which sequent, why the search with
exponentials deepens a bound, how a sequent is refuted, and how threads
share the work. You need none of it to use the command; it helps to
read --stats, to choose --engine, and to understand an "unknown".
Which engine searches
deduxit looks at the sequent's connectives (its fragment) and picks
an engine. The verdict line names it, and --engine forces another:
- The additive engine decides a sequent of two formulas built from
atoms with
&,⊕,⊤and0alone. It recurses on pairs of subformulas, so it runs in time linear in the product of their sizes. - The Horn engine decides a Horn program: atoms, implications
between tensors of atoms, such implications under
!, and a goal that is a tensor of atoms (below). - The focus engine searches everything else in classical linear logic: a focused sequent search over bitsets, which applies the rules that need no choice at once and makes choices only at stable sequents.
- The two-sided engine is the focus engine's counterpart in intuitionistic linear logic. It keeps one goal on every branch.
- The net engine searches MLL without units for an axiom linking that makes the sequent's formula trees a proof net. It decides cyclic linear logic, and in classical linear logic it takes over where the focus engine stops at its recursion limit on a sequent whose atoms occur once with each sign (a chain of thousands of links), or at its memory bound under Mix.
- The inverse method (
--engine inverse) searches forward, from the axioms up. Without Mix, it takes over where the focus engine meets its memory bound (some sequents of thousands of distinct atoms), three to four times as fast there, and the net engine takes over after it where it meets a bound of its own. It also takes short turns beside the engine on some goals (below). - The essential engine (
--engine essential) searches IMLL without units for an essential net. It decides the Lambek calculus, and in intuitionistic linear logic it runs only when asked.
--fragment asserts the fragment, and a sequent outside it is an error.
--stats prints the counters of the engine that ran. The focus engine
counts the stable sequents it visited, those it found in its memo (the
sequents already decided), and the splits it examined (the ways to
divide a context between the two premises of a ⊗). The net engine
counts the literals it chose to link, the links it tried and the
correctness tests it ran. Units of work are each engine's steps; on one
thread they are the same on every machine.
$ deduxit prove --mix --stats --deterministic --engine net "|- A par B, ~A, ~B"
provable (MLL, classical with Mix, net engine)
─────── ax ─────── ax
⊢ A, ~A ⊢ B, ~B
──────────────────── mix
⊢ A, B, ~A, ~B
─────────────── ⅋
⊢ A ⅋ B, ~A, ~B
literals chosen: 2
links tried: 2
exact tests run: 2
units of work: 2
time: 63.45µs
$ deduxit prove --engine focus --stats --quiet --deterministic "|- A * B, C * (~A par ~B), ~C"
provable (MLL, classical, focus engine)
stable sequents visited: 2
from the memo: 0
memo entries at most: 2
splits examined: 3
units of work: 35
time: 56.66µs
Exponentials and the copy bound
With ! and ? (MELL and full linear logic) a proof may copy a ?
formula any number of times. The focus engine searches under a bound on
how often a ? formula is copied on one branch, and deepens the bound
from zero: it goes on to the next bound until it decides or the time
limit passes. --copies N caps the bound at N. The derivation shows the
standard rules: dereliction (?d), contraction (?c), weakening (?w)
and promotion (!).
$ deduxit prove "!A |- !(A * A)"
provable (MELL, classical, focus engine)
─────── ax ─────── ax
⊢ ~A, A ⊢ ~A, A
──────── ?d ──────── ?d
⊢ ?~A, A ⊢ ?~A, A
────────────────────── ⊗
⊢ ?~A, ?~A, A ⊗ A
───────────────── ?c
⊢ ?~A, A ⊗ A
─────────────── !
⊢ ?~A, !(A ⊗ A)
Deepening is why a call without flags answers within its time limit whatever it is given, and why an answer near the limit depends on the machine.
The bias
The focused engines treat one literal of every atom as positive. This
decides where a proof keeps its focus, never what is provable. --bias
names the rule: factors makes positive the literal that is more often
a direct factor of a ⊗ (such a ⊗ needs no search for its split),
rarer the one with fewer occurrences. Without exponentials the
default, auto, is factors, and under --affine it is rarer.
With exponentials neither always wins. On Horn clauses under !,
factors chains forward from the facts and is often faster by orders
of magnitude, but a forward chain takes one copy per step on a single
branch, where rarer chains backward from the goal within a few copies.
So on a sequent with exponentials auto runs both searches and answers
with the first that decides: in turns, in slices of work, on one core,
so that the run stays a function of the input, and side by side on
several. Under --copies N the backward search keeps to the bound, and
so does the forward one, except on a Horn program, where it runs within
--forward-copies (30 by default), a bound in steps of the chain:
$ deduxit prove -q --deterministic --stats --engine focus "!(a * a -o b), !(b * b -o c), !(c * c -o d), a, a, a, a, a, a, a, a |- d"
provable (MELL, classical, focus engine)
stable sequents visited: 47
from the memo: 5
memo entries at most: 9
splits examined: 151
copy bound reached: 7
forward search's copy bound reached: 7
units of work: 1297
time: 136.45µs
$ deduxit prove -q --deterministic --stats --engine focus --bias rarer "!(a * a -o b), !(b * b -o c), !(c * c -o d), a, a, a, a, a, a, a, a |- d"
provable (MELL, classical, focus engine)
stable sequents visited: 230
from the memo: 178
memo entries at most: 34
splits examined: 1036
copy bound reached: 3
units of work: 4256
time: 181.10µs
$ deduxit prove -q --deterministic --stats --engine focus --bias factors --copies 3 "!(a * a -o b), !(b * b -o c), !(c * c -o d), a, a, a, a, a, a, a, a |- d"
unknown (MELL, classical, focus engine): the copy bound of 3 was reached after 55.51µs; raise it with --copies N, or lift it with --copies none to deepen it while the time limit lasts
stable sequents visited: 11
from the memo: 0
memo entries at most: 5
splits examined: 31
copy bound reached: 3
units of work: 322
time: 55.51µs
$ deduxit prove -q --engine focus --copies 1 "!A, !(A -o B), !(B -o C) |- C"
provable (MELL, classical, focus engine)
$ deduxit prove -q --engine focus --copies 1 --forward-copies 1 "!A, !(A -o B), !(B -o C) |- C"
unknown (MELL, classical, focus engine): the copy bound of 1 was reached after 149.56µs; raise it with --copies N, or lift it with --copies none to deepen it while the time limit lasts
The Horn engine
A Horn program is a Petri net. !(a * b -o c * d) is a transition that
takes the tokens a and b and gives c and d; the atoms left of
⊢ are the starting marking, and the goal is the marking to reach. With
a clause under !, the sequent goes to the Horn engine. It searches the
markings in place of sequents, each reached once and the one nearest the
goal first. It reads the proof off the firing sequence it finds: each
firing is a copy of its clause, whose body takes its atoms by axioms.
It needs no copy bound. It answers "unprovable" when it has seen every reachable marking without the goal, or when the counts of an atom rule the goal out. It also answers "unprovable" when the net's state equation has no solution, which a simplex beside the search finds out. Then weights for the atoms, checked exactly, show that no firing raises the weighted count of the tokens while the goal needs it raised, however many markings the net has. A net whose markings grow without end and whose equation has a solution is searched until the time or the memory limit.
Two more refutations reach nets whose markings grow without end. A clause with an atom no reachable marking holds can never fire, and is left out. And once the search has run a while, the same search runs backward from the goal beside it, where such a net often has few markings.
In affine mode, the tokens and clauses left over may be weakened, so
the question is whether some reachable marking covers the goal. The
engine decides it backward from the goal: it keeps the least markings
from which a firing covers the goal, until one lies below the start or
none is new, which always comes. --stats counts the markings:
$ deduxit prove "!A, !(A -o B), !(B -o C) |- C"
provable (MELL, classical, horn engine)
─────── ax ─────── ax
⊢ ~B, B ⊢ ~C, C
──────────────────── ⊗
⊢ ~B, B ⊗ ~C, C
─────── ax ────────────────── ?d
⊢ ~A, A ⊢ ~B, ?(B ⊗ ~C), C
──────────────────────────────── ⊗
⊢ ~A, A ⊗ ~B, ?(B ⊗ ~C), C
───────────────────────────── ?d
⊢ ~A, ?(A ⊗ ~B), ?(B ⊗ ~C), C
────────────────────────────── ?d
⊢ ?~A, ?(A ⊗ ~B), ?(B ⊗ ~C), C
$ deduxit prove -q --deterministic --stats "!(a * a -o b), !(b * b -o c), !(c * c -o d), a, a, a, a, a, a, a, a |- d"
provable (MELL, classical, horn engine)
markings reached: 7
markings met again: 0
markings kept: 7
units of work: 6
time: 45.06µs
$ deduxit prove -q --deterministic --stats "!(a * a -o b), !(b * b -o c), !(c * c -o d), a, a, a, a, a, a, a, a |- d * a"
unprovable (MELL, classical, horn engine): the search was exhaustive
markings reached: 12
markings met again: 2
markings kept: 10
units of work: 13
time: 31.81µs
$ deduxit prove -q "!(a -o a * a), !(b * b -o c), a, b |- c"
unprovable (MELL, classical, horn engine): the state equation of the Petri net has no solution, so no firing of its clauses yields the goal's atoms: weighting each a by −2, b by 1 and c by 2, no clause that can fire raises the weighted count of the atoms, and the goal asks it raised
$ deduxit prove -q --affine --stats "!(a * a -o b * b * b), a, a, a |- b * b * b"
provable (MELL, classical affine, horn engine)
markings computed backward: 1
markings covered already: 0
markings kept: 1
units of work: 2
time: 268.07µs
$ deduxit prove -q --affine "!(a * a -o b * b * b), a, a, a |- b * b * b * b"
unprovable (MELL, classical affine, horn engine): read as a Petri net, the goal's target cannot be covered: a backward search from it saturated, and none of the 3 markings it kept is at most the initial marking
The last goal's state equation has a solution, one and a third firings
of the clause, so only the search refutes it. The a left over in the
proof before it is weakened.
Such a refutation carries the markings the backward search kept: every
marking from which the target can be covered is at least one of them,
and the initial marking is none of these. A check of its own verifies
them before the verdict, without the search: one of them is at most the
target, none is at most the initial marking, and every clause that can
fire, fired backward from any of them, needs a marking at least one of
them. --format json writes them, and deduxit check checks them
again (the chapter on checking); the Rocq export has no certificate for
them yet. Where the counts or an assignment refute too, those are
reported instead, being smaller.
The inverse method
--engine inverse searches forward by the focused inverse method. It
derives stable sequents from the axioms upward, each focusing phase of
the sequent's formulas one rule. It keeps a derived sequent unless one
already kept stands for every sequent it stands for, and proves the goal
once every stable sequent the goal decomposes into is derived. Without
exponentials it can derive finitely many sequents, so it decides. With
them it needs no copy bound: it proves what is provable given time, and
refutes where nothing new comes. This suits a small goal under many
hypotheses that ! makes reusable.
Where it refutes, the refutation is the set of sequents it saturated with. A check of its own verifies it before the verdict: it reads the rules off the sequent again and applies them to every choice of the set's sequents. Its counters are the sequents taken up, subsumed and kept, and it runs in every commutative mode.
Without --engine, on an intuitionistic goal with an exponential and on
a goal under Mix (not affine), the inverse method takes turns beside the
engine detection picks. That engine searches alone for some hundredths
of a second. Then, each time its work has doubled, the inverse method
takes a turn on the same thread, starting afresh, of at most a
thirty-second of that work, and the engine goes on where it stopped. The
turns cost at most a sixteenth of the engine's work, and a goal decided
within the head start sees none. A goal the inverse method decides in a
turn is answered by it, and the verdict line says inverse engine. On
the intuitionistic problems of the LLTP library, this decides in
milliseconds what the backward search leaves undecided after a minute.
$ deduxit prove -i --engine inverse --stats "!(a -o b), !(b -o c), a |- c"
provable (IMELL, intuitionistic, inverse engine)
───── ax ───── ax
b ⊢ b c ⊢ c
──────────────── ⊸L
b, b ⊸ c ⊢ c
───── ax ─────────────── !L
a ⊢ a b, !(b ⊸ c) ⊢ c
─────────────────────────── ⊸L
a ⊸ b, !(b ⊸ c), a ⊢ c
───────────────────────── !L
!(a ⊸ b), !(b ⊸ c), a ⊢ c
sequents taken up: 2
sequents subsumed: 0
sequents kept: 3
units of work: 50
time: 102.44µs
$ deduxit prove -i --engine inverse -q "!(a -o b), a |- b * b"
unprovable (IMELL, intuitionistic, inverse engine): the search saturated: its 2 sequents are closed under the rules, and none of them yields the goal
Intuitionistic linear logic
Under -i a sequent of two additive-only formulas goes to the additive
engine, in every mode, and a Horn program with a clause under ! to
the Horn engine, as in classical logic. Everything else goes to the
two-sided engine, with the same copy bound and affine mode as the focus
engine. IMLL without units, each atom once with each sign, goes to the
net engine where the two-sided engine stops at its recursion limit or
memory bound: the classical net of the one-sided sequent is always an
intuitionistic proof.
$ deduxit prove -i -q --stats "(A & B) + (A & C) |- A & (B + C)"
provable (IALL, intuitionistic, additive engine)
pairs of subformulas visited: 20
from the memo: 0
memo entries: 20
units of work: 20
time: 89.90µs
--engine essential searches IMLL without units for an essential net.
The intuitionistic reading directs every edge from the hypotheses toward
the goal. A linking is then a proof net when the directed graph has no
cycle and every implication A ⊸ B on the goal's side dominates its
antecedent: every path from A to the goal passes through it. The
engine keeps which occurrence reaches which, a matrix of bits that
--memory-limit bounds. It was slower than the two-sided engine on all
but the smallest sequents it was measured on, so under -i it runs only when
asked:
$ deduxit prove -i --engine essential --net "A -o B, B -o C |- A -o C"
provable (IMLL, intuitionistic, essential engine)
A ⊸ B, B ⊸ C ⊢ A ⊸ C
A[1] — A[7]
B[2] — B[4]
C[5] — C[8]
proof net (the correctness criterion holds)
Why a sequent is unprovable
An "unprovable" verdict carries a reason, which deduxit check
verifies without the search (Check a proof or a
refutation):
- An atom's count. In every axiom an atom meets its negation. So if
an atom occurs more often with one sign than the other, whichever
additive alternatives a proof takes, the occurrences cannot all meet
in axioms. Under
!and?a copy adds occurrences; the count still refutes where all of the atom's occurrences there have one sign. Of a sequent written with two sides, the reason speaks of the sides:Aon the right meetsAon the left, and a negated formula or an implication's antecedent counts on the other side. Where a hypothesis is the atom left over and nothing is missing on the right, the line adds that-alets a hypothesis go unused. - The count equation. A provable one-sided sequent of MLL has exactly #⊗ − #⅋ − #1 + #⊥ + 2 formulas.
- The state equation of a Horn program, above.
- The classical reading. After a search that did not prove the
sequent, the command reads it in classical propositional logic:
!and?erased,*and&as "and",parand+as "or",-oas implication,1andtoptrue,botand0false. It looks for truth values of the atoms that make it false. No provable sequent has them, in any mode, so an unknown search becomes unprovable with the values as its reason, and an exhausted one gets them as a certificate. This search runs after the proof search, past the time limit, within--classical-work Nformulas evaluated (2²⁶ by default;0turns it off), and never changes a verdict the proof search gave. - A saturated set of the inverse method, and the basis of the Horn engine's backward search in affine mode, above.
- "The search was exhaustive": the search tried everything within
its bounds and none of the above applies. Only the search vouches for
it, so
checkcannot verify it.
The JSON output holds the same reason as refutation, written
one-sided.
Threads
By default the search runs on one thread first. If that has not
decided within a tenth of a second (--pool-after), a pool of the
machine's other cores searches beside it, and the first to decide
answers. So a small sequent is decided at once and always the same way,
a hard one gets the machine, and what one thread decides within the
limit stays decided. The additive, Horn, essential and inverse engines
run on one thread and get no pool.
--jobs N (-j) runs N threads from the start (after one thread, with
--pool-after). --deterministic runs the sequential engines
throughout, whose proof and statistics are a function of the input. A
parallel run may find a different proof of the same sequent, never a
different verdict. The focus engine splits the choices nearest the root
among the threads and shares its memo; on a first-order sequent it
splits only the choices that no rule around them may ask for another
witness. The net engine splits its search into cubes at its first
choices, and where every link is forced it makes each link once, as one
thread does. A search never uses more threads than the machine runs at
once, and a larger --jobs is taken as that many, with a note:
$ deduxit prove -q -j 4 --copies 3 --classical-work 0 "!(A -o A * A), !(B * B -o C), A, B |- A * A * A * ?D"
unknown (MELL, classical, focus engine): the copy bound of 3 was reached after 1.79ms; raise it with --copies N, or lift it with --copies none to deepen it while the time limit lasts
$ deduxit prove -q --deterministic --copies 3 --classical-work 0 "!(A -o A * A), !(B * B -o C), A, B |- A * A * A * ?D"
unknown (MELL, classical, focus engine): the copy bound of 3 was reached after 2.55ms; raise it with --copies N, or lift it with --copies none to deepen it while the time limit lasts
$ deduxit prove -q -j 10000 "A |- A"
note: --jobs 10000 is more than this machine runs at once; a search uses 16
provable (MLL, classical, focus engine)