In mathematical logic, focused proofs are a particular family of analytic proofs which arise through goal-directed proof-search, and are a topic of study in structural proof theory and reductive logic. They form the most general definition of goal-directed proof-search which is essentially identified by choosing a formula and performing hereditary reductions until some condition is met . The extremal case where reduction only terminates when axioms are reached forms the sub-family of uniform proofs. Focused proofs The focusing principle was originally classified through the disambiguation between synchronous and asynchronous connective in Linear Logic i.e., connectives which interact with the context and those which do not, as consequence of research on logic programming. They are now an increasingly important example of control in reductive logic, and can drastically improve proof-search procedures in industry. The essential idea of focusing is to identify and coalesce the non-deterministic choices in a proof, so that a proof can be seen as an alternation of negative phases ( where invertible rules are applied eagerly), and positive phases (where applications of the other rules are confined and controlled). Focused system A sequent calculus is often shown to have the focusing property by working in a related calculus where polarity explicitly controls which rules may be applied . Proofs in such systems are in focused, unfocused, or neutral phases, where the first two are characterised by hereditary decomposition; and the latter by forcing a choice of focus. One of the most important operational behaviours a procedure can undergo is backtracking i.e., returning to an earlier stage in the computation where a choice was made. In focused systems for classical and Intuitionistic logic, the use of backtracking can be simulated by pseudo-contraction. Let and denote change of polarity, the former making a formula negative, and the latter positive; and call a formula with an arrow neutral. Recall that is positive, and consider the neutral polarized sequent , which is interpreted as the actual sequent . For neutral sequents such as this, the focused system forces on to make an explicit choice of which formula to focus on, denoted by . To perform a proof-search the best thing is to chose the left formula, since is positive, indeed (as discussed above) in some cases there are no proofs where the focus is on the right formula. To overcome this, some focused calculi create a backtracking point such that focusing on the right yields  which is still as . The second formula on the right can be removed only when the focused phase has finished, but if proof-search gets stuck before this happens the sequent may remove the focused component thereby returning to the choice e.g., has to be taken to as no other reductive inference can be made. This is a pseudo-contraction since it has the syntactic form of a contraction on the right, but the actual formula doesn't exist i.e., in the interpretation of the proof in the focused system the sequent has only one formula on the right.
In mathematical logic, focused proofs are a family of analytic proofs that arise through goal-directed proof-search, and are a topic of study in structural proof theory and reductive logic. They form the most general definition of goal-directed proof-search —in which someone chooses a formula and performs hereditary reductions until the result meets some condition . The extremal case where reduction only terminates when axioms are reached forms the sub-family of uniform proofs. Focused proofs The focusing principle was originally classified through the disambiguation between synchronous and asynchronous connective in Linear Logic i.e., connectives that interact with the context and those that do not, as consequence of research on logic programming. They are now an increasingly important example of control in reductive logic, and can drastically improve proof-search procedures in industry. The essential idea of focusing is to identify and coalesce the non-deterministic choices in a proof, so that a proof can be seen as an alternation of negative phases ( where invertible rules are applied eagerly), and positive phases (where applications of the other rules are confined and controlled). Focused system A sequent calculus is often shown to have the focusing property by working in a related calculus where polarity explicitly controls which rules apply . Proofs in such systems are in focused, unfocused, or neutral phases, where the first two are characterised by hereditary decomposition; and the latter by forcing a choice of focus. One of the most important operational behaviours a procedure can undergo is backtracking i.e., returning to an earlier stage in the computation where a choice was made. In focused systems for classical and Intuitionistic logic, the use of backtracking can be simulated by pseudo-contraction. Let and denote change of polarity, the former making a formula negative, and the latter positive; and call a formula with an arrow neutral. Recall that is positive, and consider the neutral polarized sequent , which is interpreted as the actual sequent . For neutral sequents such as this, the focused system forces on to make an explicit choice of which formula to focus on, denoted by . To perform a proof-search the best thing is to chose the left formula, since is positive, indeed (as discussed above) in some cases there are no proofs where the focus is on the right formula. To overcome this, some focused calculi create a backtracking point such that focusing on the right yields , which is still as . The second formula on the right can be removed only when the focused phase has finished, but if proof-search gets stuck before this happens the sequent may remove the focused component thereby returning to the choice e.g., must be taken to as no other reductive inference can be made. This is a pseudo-contraction since it has the syntactic form of a contraction on the right, but the actual formula doesn't exist i.e., in the interpretation of the proof in the focused system the sequent has only one formula on the right.
D
particular
R
which
that
R
which is essentially identified by choosing
—in which someone chooses
R
performing
performs
R
some condition is met
the result meets some condition
R
which
that
R
which
that
R
may be applied
apply
A
,
R
has to
must