AFTD Auto-Formalizing Theoretical Domains

protocol_leaf_count

def

The number of leaves of a deterministic communication protocol $p$ is $1$ if $p$ is an output node, and the sum of the leaf counts of both subtrees if $p$ branches on an Alice or Bob query.

Statement

def protocol_leaf_count {X Y α : Type*} (p : CommunicationComplexity.Deterministic.Protocol X Y α) : ℕ
Defined in
arXiv:2611.11488, Section 1.1 and Lemma 3.2
Verified
10 Nov 2026
Axioms
none listed
Built on 1
Used by 1
  • min_leaf_countGiven types $X$, $Y$, and $\alpha$ and a function $f : X \to Y \to \alpha$, the minimum protocol leaf count $\mathrm{min\_leaf\_count}(f)$…

Read back from the Lean

For arbitrary types X, Y, and α, protocol_leaf_count p recursively computes the number of leaves (as a natural number ℕ) of a deterministic communication protocol p : CommunicationComplexity.Deterministic.Protocol X Y α: - If p is an output node (CommunicationComplexity.Deterministic.Protocol.output _), it evaluates to 1. - If p is an Alice node (CommunicationComplexity.Deterministic.Protocol.alice _ P), it evaluates to protocol_leaf_count (P false) + protocol_leaf_count (P true). - If p is a Bob node (CommunicationComplexity.Deterministic.Protocol.bob _ P), it evaluates to protocol_leaf_count (P false) + protocol_leaf_count (P true).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The number of leaves in a deterministic communication protocol tree. -/
def protocol_leaf_count {X Y α : Type*} (p : CommunicationComplexity.Deterministic.Protocol X Y α) : ℕ := match p with
  | CommunicationComplexity.Deterministic.Protocol.output _ => 1
  | CommunicationComplexity.Deterministic.Protocol.alice _ P => protocol_leaf_count (P false) + protocol_leaf_count (P true)
  | CommunicationComplexity.Deterministic.Protocol.bob _ P => protocol_leaf_count (P false) + protocol_leaf_count (P true)
See it in the graphDiscuss this resultChallenge it