README.md

Random systems

This library holds the concrete objects and their laws: deterministic systems, automata and environments (System), distributions over deterministic systems (PDS), random systems given by their cumulative probabilities, with their presentations (Cumulative), deterministic converters and their compositions (DDC), probabilistic converters, programs, attachment and parallel composition (Converter), the transcript distance and distinguishers (Distance), games (Game), and typed systems on interfaces (Typed). It knows nothing of the classes of ConstructiveCryptography, whose instances on interfaces take their fields from here. Citations refer to the numbered references of THEORY.md.

Systems over finite alphabets, answering exactly on a bounded domain [1], [2, Chapter 2], [3, Chapter 3]. Laws are finitely supported distributions and $\delta$ is the statistical distance (Probability).

Deterministic systems

A deterministic system (DDS) is a partial function from input histories to the next output, $s : \mathcal X^{*} \rightharpoonup \mathcal Y$, silent at the empty history, whose domain is closed under nonempty prefixes. Systems are wired together, each output leaving the wiring or returning as an input. A system replies $y_1 \dots y_n$ to $x_1 \dots x_n$ when it answers each prefix with the next output, and a DDS is determined by its completed replies. An automaton is a transition function started in a state, and bisimilar automata have the same system. An environment (DDE) chooses the next query from the replies so far.

Probabilistic systems

A transcript follows a query strategy when every exchange prefix $p\mathbin{+\!+}[(x,y)]$ has $x\in\sigma(\operatorname{replies}(p))$, the rule $x_i = e(y_1,\dots,y_{i-1})$ of [1, Definition 7, printed p. 12] (FollowsStrategy in CumulativeObservation). This states the next-query rule directly; FollowsStrategy.iff_getElem supplies the equivalent indexed form when needed for list calculations.

A domain $\mathcal D$ admits next queries after each transcript, with a bound on the length. A PDS is a finite distribution over DDSs with domain $\mathcal D$ [1, Definition 8]. A random system is given by its cumulative probabilities $p$ on transcripts [1, after Lemma 5], normalized on the domain:

$$p(\varepsilon) = 1, \qquad p \ge 0, \qquad \sum_{y} p\big(h \cdot (x, y)\big) = \begin{cases} p(h) & \text{if } x \text{ is admitted after } h, \\ 0 & \text{otherwise.} \end{cases}$$

A PDS has a random system, and equivalent PDSs have the same one. Every random system has a finite presentation, so random systems are exactly the classes of equivalent PDSs. Two random systems are equal exactly when their transcript laws agree in every compatible environment, and on a domain of input histories fixed query sequences suffice [1, Lemma 5]. Random systems on one domain form mixtures, and two random systems run independently in parallel form one on the combined alphabets. For a finite tagged family, the n-ary product multiplies component transcript masses on consistent interleavings and keeps each component's input domain. Independent deterministic component presentations present the same joint cumulative law. The n-ary converter canonicalizes its complete-history rule and combines component domain certificates; stochastic converter families sample their components independently.

Aggregate serial accounting uses costs of actual intermediate query values. The inner component's partial-transcript bound includes pending calls. An input-only composite budget additionally requires the outer weighted sum to be bounded on every reply trace; consecutive-query bounds alone do not provide this result. Direct call rules supply their aggregate bound from the arbitrary-reply phase contract.

A probabilistic automaton answers a query from its state with a law on the next state and the reply, a probabilistic step; its random system follows the sub-law of the states reached with the replies of a transcript, whose weight is the probability of the transcript. On an input domain, two probabilistic automata have the same random system along a simulation, a kernel between their states through which their steps commute. A deterministic automaton with a random initial state is the probabilistic automaton of its point steps, and a probabilistic automaton is a deterministic automaton reading pre-sampled draws, sampled once with the initial state: a random automaton [4, Definition 2].

A random system is memoryless when the law of its reply depends only on the current query, never on the history: a source "can be memoryless or have memory" [3, Definition 3.1], and a single-input system given by a conditional distribution is a "discrete memoryless channel" [3, §3.6.1]. With the reply law $\nu$, its probabilities obey the chain rule

$$p\big(h \cdot (x, y)\big) = p(h)\, \nu_x(y) \qquad \text{for every query } x \text{ admitted after } h,$$

and a random system obeying it is the memoryless system. A probabilistic automaton whose step replies from every state with the same law $\nu$ is the memoryless system of this law. Two memoryless systems side by side are memoryless: a query to either system is answered with the reply law of that system.

Converters

A DDC is a system on the converter alphabets (outside queries and inside replies in; inside queries and outside replies out) with at most $b$ consecutive inside queries [3, Definition 3.8]. A DDC from $E$ to $F$ (IsDDCFrom) answers exactly the converter domain and queries only in $E$; attached to a system with domain $E$ it gives one with domain $F$. A PDC is a distribution over DDCs, and its behavior is a random system over the converter domain [3, Definitions 3.17–3.18]. A DDC from $E$ to $F$ whose transcripts are transcripts of a DDC $r$, not necessarily responsive, is a filter of $r$ [3, §3.4.3]: the restriction of $r$ to the input histories whose outside queries lie in $F$.

Serial composition $\beta \odot \alpha$ connects the inside of $\beta$ to the outside of $\alpha$, and DDCs compose with the product of their bounds. When the run of $\alpha$ in an invocation at the intermediate port $m$ is at most $\mathrm{cost}(m)$, and the outer converter carries a charge, raised by $\mathrm{cost}(m)$ with each query at $m$ and at most $B$, the composite is bounded by the charge: at most $B$ consecutive inside queries. This bounds one run, not the total over invocations.

PDC behaviors have a composition and an identity, with associativity and the left and right identity laws. Attachment samples the PDC, then attaches the sample deterministically: presentations attach to presentations, the identity leaves a system unchanged, and a composition attaches its inner converter first. Parallel composition samples two PDCs independently and runs them side by side, with interchange against serial composition.

A direct call rule reads from the complete history the current invocation, the latest outside query $u$ with the inside replies $r_1 \dots r_k$ received since, and either returns at the label of $u$ or issues the next inside query [7, Definition 2.2.2]. It depends on $u$ and $r_1 \dots r_k$ only. The one-way phase condition, an inside query only when $k < \mathrm{cost}(u)$, gives responsiveness and the query count $\#\text{inside queries} \le \sum_u \mathrm{cost}(u)$, including pending and interrupted invocations; the biconditional gives the exact length of a completed call. Canonicalization followed by outside-domain restriction yields a certified DDC from an inside domain; any further inside-domain predicate is proved on the actual transcripts. A rule following a schedule against a fixed function has the completed transcripts, and attached to that function it computes the indicated outside function through the existing deterministic attachment. A query router specializes this call to one input-dependent inside request. Its query history is the exact request-map image of the outside history, including a pending call; an explicit answer map translates the inside reply.

A program is a deterministic oracle body: from its state, the outside query and the inside exchanges of the current invocation, it computes the reply or the next inside query. A program can be bounded (at most $b$ inside queries per invocation), have exact costs, or preserve a partial port map $\iota : O \to \mathrm{Option}\ J$: an invocation at $o$ queries the labels in the image of $\iota$ only at $\iota(o)$, at most once, and none of them when $\iota(o)$ is none, so it queries $\iota(o)$ at most as often as it is queried at $o$. On an outside domain, a bounded program is a DDC from every inside domain containing its inside queries. Attached to an automaton, a program is inlined [4, §3.3]: the result is the combined automaton on pairs of states, also on domains.

Run against a probabilistic automaton, a program is the probabilistic automaton on pairs of states whose step runs one invocation, the automaton answering the inside queries with fresh steps; it respects simulations. Attaching the program's converter to a probabilistic automaton is the program run against it, the combined system $C(F)$ of a system $C(\cdot)$ invoking $F$ [4, §3.3]; for point steps it is the combined automaton. Against memoryless replies of the laws $\nu$, a program replies memorylessly when its reply law $\kappa$, the law of one invocation whose inside queries are answered by fresh samples of $\nu$, is the same from every program state. So the composition law holds, whatever the number of the program's inside queries:

$$\alpha_P\, \mathrm{mem}(\nu) = \mathrm{mem}(\kappa).$$