deduxit 0.5.0

A collection of logic suites: decides, checks, proves step by step and exports sequents of linear logic and of classical, intuitionistic and minimal propositional logic, with checked proofs, Kripke countermodels and Rocq certificates.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
// deduxit © Fabian Lukas Grubmüller 2026
// Licensed under the EUPL

//! Essential nets: a proof structure of an intuitionistic sequent read as
//! Lamarche's polarized structure, a directed graph, and decided by
//! directed acyclicity and the dominator condition (Lamarche; Murawski
//! and Ong), independently of the switchings.
//!
//! The sequent's [`Reading`](crate::linear::occurrences::Reading) puts
//! every occurrence on one side of `⊢`: *input*, the side of the
//! hypotheses, or *output*, the side of the goal. The edges run from an
//! output occurrence to its parent, from an input connective to each of
//! its input premises, and along every link from its input literal (`~a`)
//! to its output literal (`a`).
//!
//! The one premise that nothing leads into is the antecedent of an
//! implication in output position. `A ⊸ B` is stored as `A⊥ ⅋ B`, and its
//! input premise `A⊥` is where the hypothesis `A` enters. So every path
//! runs from the hypotheses and the antecedents toward the goal. Once
//! every literal is linked, the goal is the one occurrence without an
//! edge out.
//!
//! A linking is an essential net when the graph has no directed cycle and
//! every implication in output position, other than the goal itself,
//! dominates its antecedent. That is, every path from the antecedent to
//! the goal passes through the implication, so the hypothesis it binds is
//! used inside its body only. For the structure of an intuitionistic
//! sequent this is the same verdict as the Danos–Regnier criterion
//! without Mix.

use super::{NetError, ProofStructure, STOPPED, VertexId};
use crate::limits::{Phase, Progress};
use crate::linear::fragment::{Mode, Order};
use crate::linear::occurrences::{Forest, OccId, Reading, ShapeError, Side};
use crate::linear::sequents::Kind;

/// The raw index that stands for "no occurrence".
const NONE: u32 = u32::MAX;

/// The bytes per vertex `is_essential` holds at most: two successors, the
/// state of the search for a cycle, the stamp and the predecessor of the
/// searches around each implication, and their stack and queue, whose
/// growth by doubling may hold twice their entries.
const ESSENTIAL_BYTES: u64 = 8 + 4 + 4 + 4 + 2 * 16 + 2 * 4;

/// Returns the edges of the essential net that leave `o` whatever is
/// linked: to its parent for an output occurrence that is no root, to
/// each input premise for an input connective, and none for a literal in
/// input position, whose edge is its link.
pub(crate) fn fixed_successors(
    forest: &Forest,
    reading: &Reading<'_>,
    o: OccId,
) -> impl Iterator<Item = OccId> {
    let output = reading.position(o) == Side::Output;
    let parent = forest.parent(o).filter(|_| output);
    let premises = forest
        .children(o)
        .filter(move |&c| !output && reading.position(c) == Side::Input);
    parent.into_iter().chain(premises)
}

/// Returns whether `o` is an implication in output position, `A ⊸ B`
/// stored as `A⊥ ⅋ B`, whose left premise is the antecedent, or in the
/// Lambek calculus's ordered reading either division.
pub(crate) fn is_implication(forest: &Forest, reading: &Reading<'_>, o: OccId) -> bool {
    forest.kind(o) == Kind::Par && reading.position(o) == Side::Output
}

impl ProofStructure {
    /// Returns the intuitionistic reading of the structure's sequent: the
    /// side of `⊢` every vertex stands on, which orients its essential
    /// net.
    ///
    /// Under a criterion of the cyclic order it is the ordered reading of
    /// the Lambek calculus ([`Reading::of_mode`]), with empty antecedents
    /// allowed. It is recomputed on each call, in time linear in the
    /// forest.
    ///
    /// # Errors
    ///
    /// The [`ShapeError`] of a sequent with no intuitionistic reading.
    pub fn reading(&self) -> Result<Reading<'_>, ShapeError> {
        match self.criterion.order {
            Order::Commutative => Reading::new(&self.forest),
            Order::Cyclic => Reading::of_mode(&self.forest, Mode::LAMBEK.with_empty_antecedents()),
        }
    }

    /// Decides whether the structure is an essential net of its sequent's
    /// intuitionistic reading, independently of any search and of the
    /// proof checker.
    ///
    /// An essential net has every literal linked, and its directed graph
    /// has no cycle. Every implication in output position (on the goal's
    /// side of `⊢` in the [`reading`](Self::reading)) but the goal
    /// dominates its antecedent: every path from the antecedent to the
    /// goal passes through it. For a structure of an
    /// intuitionistic sequent the verdict is that of
    /// [`is_correct`](Self::is_correct) without Mix, whatever the
    /// structure's criterion. A structure with cut links has no essential
    /// net here: its verdict is that of [`is_correct`](Self::is_correct)
    /// without Mix.
    ///
    /// The call holds working memory linear in the structure. It takes
    /// time linear in it for the cycle and for each implication. It asks
    /// `stop` once after the search for a cycle and once per implication.
    ///
    /// # Errors
    ///
    /// [`NetError::Empty`], [`NetError::Unlinked`],
    /// [`NetError::NotIntuitionistic`] for a sequent without a reading,
    /// [`NetError::DirectedCycle`] or [`NetError::NoDominator`] with a
    /// witness; [`NetError::Refused`] when `stop` ended it.
    ///
    /// # Examples
    ///
    #[cfg_attr(feature = "parse", doc = "```")]
    #[cfg_attr(not(feature = "parse"), doc = "```ignore")]
    /// use deduxit::linear::{Criterion, Forest, ProofStructure, Sequent, VertexId};
    ///
    /// // a ⊸ b, a ⊢ b is ⊢ a ⊗ ~b, ~a, b, with the vertices 0: a ⊗ ~b,
    /// // 1: a, 2: ~b, 3: ~a, 4: b.
    /// let sequent: Sequent = "a -o b, a |- b".parse()?;
    /// let v = VertexId::new;
    /// let links = [(v(1), v(3)), (v(2), v(4))];
    /// let net = ProofStructure::from_links(Forest::new(&sequent)?, Criterion::MLL, &links)?;
    /// assert_eq!(net.is_essential(|_| false), Ok(()));
    /// # Ok::<(), deduxit::Error>(())
    /// ```
    pub fn is_essential(&self, mut stop: impl FnMut(Progress) -> bool) -> Result<(), NetError> {
        let forest = &self.forest;
        if forest.is_empty() {
            return Err(NetError::Empty);
        }
        if let Some(l) = self.unlinked().next() {
            return Err(NetError::Unlinked { vertex: l });
        }
        let reading = self
            .reading()
            .map_err(|shape| NetError::NotIntuitionistic { shape })?;
        if !self.is_cut_free() {
            let mut plain = self.clone();
            plain.criterion.mix = false;
            return plain.is_correct(stop);
        }
        let n = forest.len();
        // Every vertex has at most two successors: an input `⅋` its two
        // premises, any other vertex one.
        let mut successors = vec![[NONE; 2]; n];
        for o in forest.ids() {
            let out = &mut successors[o.index()];
            let fixed = fixed_successors(forest, &reading, o);
            let link = self.mate(VertexId::of(o)).map(VertexId::occ);
            let link = link.filter(|_| reading.position(o) == Side::Input);
            for (slot, s) in out.iter_mut().zip(fixed.chain(link)) {
                *slot = s.get();
            }
        }
        let next = |v: u32| successors[v as usize].into_iter().filter(|&s| s != NONE);
        let held_bytes = n as u64 * ESSENTIAL_BYTES;
        let mut rounds = 0;
        let mut poll = |stop: &mut dyn FnMut(Progress) -> bool| {
            rounds += 1;
            stop(Progress {
                held_bytes,
                ..Progress::new(Phase::Net, 1, rounds)
            })
        };

        // A depth-first search from every vertex not yet seen. Its stack
        // is the path from where it started, so an edge back into the
        // stack closes a cycle. `state` holds per vertex `UNSEEN`, `NONE`
        // once its search is done, or its place on the stack, which is
        // below the vertices' count.

        const UNSEEN: u32 = NONE - 1;
        let mut state = vec![UNSEEN; n];
        let mut stack: Vec<(u32, usize)> = Vec::new();
        for start in 0..n as u32 {
            if state[start as usize] != UNSEEN {
                continue;
            }
            state[start as usize] = 0;
            stack.push((start, 0));
            while let Some(&mut (v, ref mut i)) = stack.last_mut() {
                let Some(w) = next(v).nth(*i) else {
                    state[v as usize] = NONE;
                    stack.pop();
                    continue;
                };
                *i += 1;
                match state[w as usize] {
                    UNSEEN => {
                        state[w as usize] = stack.len() as u32;
                        stack.push((w, 0));
                    }
                    NONE => {}
                    place => {
                        let cycle = stack[place as usize..]
                            .iter()
                            .map(|&(u, _)| VertexId::new(u))
                            .collect();
                        return Err(NetError::DirectedCycle { cycle });
                    }
                }
            }
        }
        if poll(&mut stop) {
            return Err(STOPPED);
        }

        // For each implication, a search from its antecedent that does not
        // enter the implication: reaching the goal is a path around it.
        let goal = reading.goal();
        let mut seen = vec![0u32; n];
        let mut from = vec![NONE; n];
        let mut round = 0u32;
        let mut queue = Vec::new();
        for l in forest.ids() {
            let Some((antecedent, _)) = reading
                .implication(l)
                .filter(|_| l != goal && is_implication(forest, &reading, l))
            else {
                continue;
            };
            if poll(&mut stop) {
                return Err(STOPPED);
            }
            // One round per implication, of which there are fewer than
            // the vertices, so the stamp never wraps.
            round += 1;
            let antecedent = antecedent.get();
            seen[l.index()] = round;
            seen[antecedent as usize] = round;
            queue.clear();
            queue.push(antecedent);
            let mut i = 0;
            while let Some(&v) = queue.get(i) {
                i += 1;
                if v == goal.get() {
                    let mut path = vec![VertexId::new(v)];
                    let mut u = v;
                    while u != antecedent {
                        u = from[u as usize];
                        path.push(VertexId::new(u));
                    }
                    path.reverse();
                    return Err(NetError::NoDominator {
                        implication: VertexId::of(l),
                        path,
                    });
                }
                for w in next(v) {
                    if seen[w as usize] != round {
                        seen[w as usize] = round;
                        from[w as usize] = v;
                        queue.push(w);
                    }
                }
            }
        }
        Ok(())
    }
}

#[cfg(all(test, feature = "parse"))]
mod tests {
    use super::super::{Criterion, NetError, ProofStructure, VertexId};
    use super::{fixed_successors, is_implication};
    use crate::linear::occurrences::{Forest, OccId, Side, Sign};
    use crate::linear::search::generate::{self, IllRules, Rng};
    use crate::linear::sequents::{Atom, Sequent};

    /// Unit-free IMLL.
    const IMLL: IllRules = IllRules {
        units: false,
        additives: false,
        zero: false,
        exponentials: false,
    };

    /// Builds the forest of `input`, or panics.
    fn forest(input: &str) -> Forest {
        let s: Sequent = input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"));
        Forest::new(&s).unwrap()
    }

    /// Links, each as a pair of vertices.
    type Links = [(VertexId, VertexId)];

    /// Calls `each` with every complete linking of the forest, each atom's
    /// literals paired in every way, unless there are more than `most`.
    fn linkings(forest: &Forest, most: usize, each: &mut dyn FnMut(&Links)) {
        let atoms = forest.sequent().atom_names().len();
        let mut count = 1usize;
        for a in 0..atoms {
            let n = forest.literals(Atom::new(a as u32), Sign::Atom).len();
            if n != forest.literals(Atom::new(a as u32), Sign::Dual).len() {
                return;
            }
            count = (1..=n).fold(count, |c, k| c.saturating_mul(k));
        }
        if count > most {
            return;
        }
        let duals: Vec<OccId> = forest
            .all_literals()
            .iter()
            .copied()
            .filter(|&x| forest.sign(x) == Some(Sign::Dual))
            .collect();
        let mut links = Vec::new();
        let mut used = vec![false; forest.len()];
        fn go(
            forest: &Forest,
            duals: &[OccId],
            used: &mut [bool],
            links: &mut Vec<(VertexId, VertexId)>,
            each: &mut dyn FnMut(&Links),
        ) {
            let Some((&x, rest)) = duals.split_first() else {
                each(links);
                return;
            };
            for &y in forest.literals(forest.atom(x).unwrap(), Sign::Atom) {
                if !used[y.index()] {
                    used[y.index()] = true;
                    links.push((VertexId::of(x), VertexId::of(y)));
                    go(forest, rest, used, links, each);
                    links.pop();
                    used[y.index()] = false;
                }
            }
        }
        go(forest, &duals, &mut used, &mut links, each);
    }

    /// The successors of a vertex in the essential net of a complete
    /// structure.
    fn successors(net: &ProofStructure, v: OccId) -> Vec<OccId> {
        let forest = net.forest();
        let reading = net.reading().unwrap();
        let mut out: Vec<OccId> = fixed_successors(forest, &reading, v).collect();
        if reading.position(v) == Side::Input
            && let Some(w) = net.partner(VertexId::of(v))
        {
            out.push(w.occ());
        }
        out
    }

    /// The dominator condition read off its definition: every simple
    /// path from the antecedent of every implication but the goal to the
    /// goal passes through the implication, all paths enumerated.
    fn dominated_by_every_path(net: &ProofStructure) -> bool {
        let forest = net.forest();
        let reading = net.reading().unwrap();
        let goal = reading.goal();
        let mut paths = 0u32;
        fn around(
            net: &ProofStructure,
            v: OccId,
            l: OccId,
            goal: OccId,
            on: &mut Vec<OccId>,
            paths: &mut u32,
        ) -> bool {
            *paths += 1;
            assert!(*paths < 1 << 20, "too many paths to enumerate");
            if v == goal {
                return !on.contains(&l);
            }
            on.push(v);
            let found = successors(net, v)
                .into_iter()
                .any(|w| !on.contains(&w) && around(net, w, l, goal, on, paths));
            on.pop();
            found
        }
        forest
            .ids()
            .filter(|&l| is_implication(forest, &reading, l) && l != goal)
            .all(|l| {
                !around(
                    net,
                    forest.left(l).unwrap(),
                    l,
                    goal,
                    &mut Vec::new(),
                    &mut paths,
                )
            })
    }

    /// Checks a witness against the structure: a directed cycle follows
    /// edges and closes; a path around an implication starts at its
    /// antecedent, follows edges, avoids it and ends at the goal.
    #[expect(
        clippy::wildcard_enum_match_arm,
        reason = "the criterion fails with these two witnesses only"
    )]
    fn check_witness(net: &ProofStructure, error: &NetError) {
        let edge = |a: VertexId, b: VertexId| successors(net, a.occ()).contains(&b.occ());
        match error {
            NetError::DirectedCycle { cycle } => {
                assert_ne!(*cycle, []);
                for (i, &a) in cycle.iter().enumerate() {
                    assert!(edge(a, cycle[(i + 1) % cycle.len()]), "{cycle:?}");
                }
            }
            NetError::NoDominator { implication, path } => {
                let forest = net.forest();
                let reading = net.reading().unwrap();
                assert_eq!(path[0].occ(), forest.left(implication.occ()).unwrap());
                assert_eq!(path.last().unwrap().occ(), reading.goal());
                assert!(!path.contains(implication));
                assert!(path.windows(2).all(|w| edge(w[0], w[1])), "{path:?}");
            }
            other => panic!("not a witness of the essential criterion: {other}"),
        }
    }

    /// On every linking of generated intuitionistic sequents and their
    /// mutants, the essential criterion and the Danos–Regnier criterion
    /// without Mix agree, the dominator condition agrees with its reading
    /// over every path, and every witness is one.
    #[test]
    #[expect(
        clippy::wildcard_enum_match_arm,
        reason = "the criterion fails with these two witnesses only"
    )]
    fn agrees_with_the_switchings() {
        let mut rng = Rng::new(35);
        let (mut structures, mut nets, mut cycles, mut dominators) = (0, 0, 0, 0);
        for _ in 0..400 {
            let budget = 2 + rng.below(9);
            let generate::Ill {
                mut hypotheses,
                mut goal,
                ..
            } = generate::ill(&mut rng, IMLL, 3, budget);
            for mutated in [false, true] {
                if mutated && !generate::mutate_two_sided(&mut rng, &mut hypotheses, &mut goal, 3) {
                    continue;
                }
                let text = generate::two_sided(&hypotheses, &goal);
                let forest = forest(&text);
                linkings(&forest, 120, &mut |links| {
                    let net =
                        ProofStructure::from_links(forest.clone(), Criterion::MLL, links).unwrap();
                    let switchings = net.is_correct(|_| false);
                    let essential = net.is_essential(|_| false);
                    assert_eq!(
                        switchings.is_ok(),
                        essential.is_ok(),
                        "{text:?} {links:?}: {switchings:?} against {essential:?}"
                    );
                    match &essential {
                        Ok(()) => nets += 1,
                        Err(error) => {
                            check_witness(&net, error);
                            match error {
                                NetError::DirectedCycle { .. } => cycles += 1,
                                _ => {
                                    dominators += 1;
                                    assert!(!dominated_by_every_path(&net), "{text:?} {links:?}");
                                }
                            }
                        }
                    }
                    if !matches!(essential, Err(NetError::DirectedCycle { .. })) {
                        assert_eq!(essential.is_ok(), dominated_by_every_path(&net));
                    }
                    structures += 1;
                });
            }
        }
        assert!(
            nets > 300 && cycles > 300 && dominators > 100,
            "{structures} structures: {nets} nets, {cycles} cycles, {dominators} without a dominator"
        );
    }

    /// A sequent without an intuitionistic reading has no essential net,
    /// and the witnesses of the two ways to fail are the expected ones.
    #[test]
    fn witnesses() {
        let links = |pairs: &[(u32, u32)]| -> Vec<(VertexId, VertexId)> {
            pairs
                .iter()
                .map(|&(x, y)| (VertexId::new(x), VertexId::new(y)))
                .collect()
        };
        let classical = ProofStructure::from_links(
            forest("|- a par b, ~a, ~b"),
            Criterion::MLL,
            &links(&[(1, 3), (2, 4)]),
        )
        .unwrap();
        assert!(matches!(
            classical.is_essential(|_| false),
            Err(NetError::NotIntuitionistic { .. })
        ));
        // `a ⊸ a` used as its own argument: `a ⊗ ~a` linked inside.
        let cycle = ProofStructure::from_links(
            forest("a -o a |- b -o b"),
            Criterion::MLL,
            &links(&[(2, 1), (4, 5)]),
        )
        .unwrap();
        let Err(error) = cycle.is_essential(|_| false) else {
            panic!("a cycle is no net");
        };
        assert_eq!(
            error.to_string(),
            "a directed cycle of the essential net runs through 0, 2, 1"
        );
        // `⊢ (a ⊸ b) ⊗ (b ⊸ a)` with each antecedent linked into the other
        // factor.
        let around = ProofStructure::from_links(
            forest("|- (a -o b) * (b -o a)"),
            Criterion::MLL,
            &links(&[(2, 6), (5, 3)]),
        )
        .unwrap();
        let Err(error) = around.is_essential(|_| false) else {
            panic!("a hypothesis used outside its body is no net");
        };
        assert_eq!(
            error.describe(&around).to_string(),
            "the implication ~a ⅋ b[1] does not dominate its antecedent: the path ~a[2], a[6], ~b ⅋ a[4], (~a ⅋ b) ⊗ (~b ⅋ a)[0] reaches the goal around it"
        );
        assert!(matches!(
            cycle.is_essential(|_| true),
            Err(NetError::DirectedCycle { .. })
        ));
        let net = ProofStructure::from_links(
            forest("a -o b, a |- b"),
            Criterion::MLL,
            &links(&[(3, 1), (2, 4)]),
        )
        .unwrap();
        assert_eq!(net.is_essential(|_| false), Ok(()));
    }
}