Let \(p\) be a deterministic two-party communication protocol over input types \(X\) (Alice) and \(Y\) (Bob) with output type \(\alpha \), and let \(t\) be a syntactic transcript of \(p\). Then the input set of \(t\) — the set of all input pairs \((x, y) \in X \times Y\) whose execution of \(p\) follows exactly the path recorded by \(t\) — is a rectangle: there exist \(A \subseteq X\) and \(B \subseteq Y\) such that this set equals \(A \times B\).

Let \(p\) be a deterministic two-party communication protocol over input types \(X\) (Alice) and \(Y\) (Bob) with output type \(\alpha \), and let \((x, y) \in X \times Y\) be an input pair. Executing \(p\) on \((x, y)\) yields a syntactic transcript, and the pair \((x, y)\) itself belongs to the input set of that transcript.

Let \(p\) be a deterministic two-party communication protocol over input types \(X\) (Alice) and \(Y\) (Bob) with output type \(\alpha \), let \(t\) be a syntactic transcript of \(p\), and let \((x, y) \in X \times Y\) be an input pair. If \((x, y)\) belongs to the input set of \(t\), then executing \(p\) on \((x, y)\) produces exactly the transcript \(t\); that is, \(p.\mathrm{transcript}(x, y) = t\).

Let \(p\) be a deterministic two-party communication protocol over input types \(X\) (Alice) and \(Y\) (Bob) with output type \(\alpha \), and let \((x, y) \in X \times Y\) be an input pair. Running \(p\) on \(x\) and \(y\) produces the same value as first executing \(p\) on \((x,y)\) to obtain its syntactic transcript and then reading off the output value attached to the leaf of that transcript.

Let \(p\) be a deterministic two-party communication protocol over input types \(X\) (Alice) and \(Y\) (Bob) with outputs in \(\alpha \), and let \((x, y)\) and \((x', y')\) be two input pairs in \(X \times Y\). If executing \(p\) on \((x, y)\) produces the same syntactic transcript as executing \(p\) on \((x', y')\), then \(p\) returns the same output on both inputs: the value obtained by running \(p\) on \((x, y)\) equals the value obtained by running \(p\) on \((x', y')\).

Let \(a\), \(b\), \(c_a\), \(c_b\) be natural numbers with \(a \le 2^{c_a}\) and \(b \le 2^{c_b}\). Then

For every deterministic two-party communication protocol \(p\) with input types \(X\) and \(Y\) and output type \(\alpha \), the number of syntactic transcripts of \(p\) is at most \(2\) raised to its communication complexity:

Let \(p\) be a deterministic two-party communication protocol over input types \(X\) (Alice) and \(Y\) (Bob) with output type \(\alpha \), and let \(p'\) be the role-swapped protocol obtained by exchanging the roles of Alice and Bob throughout \(p\). The transcript-swap map, which sends each syntactic transcript of \(p\) to its corresponding transcript of \(p'\) by preserving the Boolean message sequence while reinterpreting each communication node as the opposite player, is injective: distinct transcripts of \(p\) are sent to distinct transcripts of \(p'\).

Let \(p\) be a deterministic two-party communication protocol over input types \(X\) (Alice) and \(Y\) (Bob), and let \(x \in X\) and \(y \in Y\) be inputs. Running \(p\) on the pair \((x,y)\) produces a syntactic transcript, and applying the transcript-swap operation to it — reinterpreting each communication node as the opposite player while preserving the Boolean message sequence — yields exactly the transcript obtained by running the role-swapped protocol (in which Alice and Bob exchange roles) on the reversed pair \((y,x)\).

Let \(p\) be a deterministic two-party communication protocol over input types \(X\) (Alice) and \(Y\) (Bob) with output type \(\alpha \), and let \(f_X : X' \to X\) and \(f_Y : Y' \to Y\) be maps on the input spaces. Consider the pulled-back protocol over \(X' \times Y'\) obtained by pre-composing every message function of \(p\) with \(f_X\) or \(f_Y\) as appropriate. Then the map that sends each syntactic transcript of \(p\) to the corresponding transcript of this pulled-back protocol — preserving the sequence of Boolean messages while re-routing through the input maps — is injective.

Let \(p\) be a deterministic two-party communication protocol over input types \(X\) (Alice) and \(Y\) (Bob) with output type \(\alpha \), and let \(f_X : X' \to X\) and \(f_Y : Y' \to Y\) be functions; write \(p'\) for the pulled-back protocol over \(X' \times Y'\) obtained by pre-composing each of Alice’s and Bob’s message functions with \(f_X\) and \(f_Y\) respectively. Then for every \(x' \in X'\) and \(y' \in Y'\), running \(p\) on the pair \((f_X(x'), f_Y(y'))\) to obtain its syntactic transcript and then re-routing that transcript through \(f_X\) and \(f_Y\) into a transcript of \(p'\) yields exactly the syntactic transcript produced by running \(p'\) directly on \((x', y')\).

Let \(\beta , \gamma : \{ \mathrm{false}, \mathrm{true}\} \to \mathrm{Type}\) be two Boolean-indexed families of types and let \(g_b : \beta _b \to \gamma _b\) be a map for each \(b \in \{ \mathrm{false}, \mathrm{true}\} \). If every \(g_b\) is injective, then the map \(\Sigma _b\, \beta _b \to \Sigma _b\, \gamma _b\) sending \((b, t)\) to \((b, g_b(t))\) — which keeps the Boolean index and applies the family fibrewise — is injective.