On the Stability and Realizability of Recurrent Polynomial Surrogate Ternary Logic Gate Networks
Sai Sandeep Damera, Ryan Matheu, Aniruddh G. Puranic, John S. Baras, Calin Belta · 2026
Read On the Stability and Realizability of Recurrent Polynomial Surrogate Ternary Logic Gate Networks by Sai Sandeep Damera, Ryan Matheu, Aniruddh G. Puranic, John S. Baras, Calin Belta (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-24649.txt.
Introduction
Sai Sandeep Damera and others build a recurrent monitor that can say it does not know. Standard recurrent nets predict Signal Temporal Logic verdicts from partial traces. Yet one dropped reading can quietly flip safe to unsafe. Their ternary gate network works in three-valued logic, where zero means unknown. It trains through smooth polynomial stand-ins, then hardens into a discrete circuit. Numeric-order gates keep dynamics stable, while information-order gates guarantee principled abstention. Tests on PointMaze navigation data back the design.
Catalog record
| CREATOR | Sai Sandeep Damera, Ryan Matheu, Aniruddh G. Puranic, John S. Baras, Calin Belta |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48033 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.24649
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Stability and Realizability of Recurrent Polynomial Surrogate Ternary Logic Gate Networks Sai Sandeep Damera, Ryan Matheu, Aniruddh G. Puranic, John S. Baras, Calin Belta Abstract Recurrent Neural Networks (RNNs) can learn to predict Signal Temporal Logic (STL) verdicts online from partial trajectories, but deploying them as runtime monitors in safety-critical systems demands more than predictive accuracy. When sensor inputs degrade or become unavailable, standard architectures such as RNNs offer no structural guarantee that their outputs degrade gracefully; a dropped input can silently flip a verdict from safe to unsafe. We introduce the Recurrent Differentiable Ternary Logic Gate Network (R-DTLGN), a recurrent architecture that operates over Kleene’s three-valued logic { − 𝟏 , 𝟎 , + 𝟏 } \bm{\{-1,0,+1\}} , where 𝟎 \bm{0} explicitly represents unknown . The R-DTLGN trains through continuous polynomial surrogates and hardens to a discrete ternary logic circuit at inference. We analyze the hardened circuit through two gate vocabularies derived from two orderings on the ternary domain: numerically monotone gates ensure stable recurrent dynamics, while information-monotone gates, when present, guarantee principled abstention (unknown inputs never produce wrong outputs) and monotonicity in input certainty (more information can only improve the verdict). We show that the recurrent connections required by bounded STL operators use exclusively AND and OR, which belong to both vocabularies, linking the monitoring task’s structure to the architecture’s guarantees. A realizability bound derived from the STL formula’s temporal operators directly sizes the network’s hidden state, replacing hyperparameter search with a formula-driven specification. We evaluate these results on STL specifications over D4RL PointMaze navigation data, testing prediction accuracy, degradation behavior under predicate dropout, and the accuracy-versus-safety tradeoff between two label construction pipelines. The R-DTLGN is, to our knowledge, the first recurrent architecture that couples learned temporal prediction with formal degradation guarantees rooted in three-valued logic. I Introduction Monitoring a safety specification online requires evaluating temporal properties as data arrives. Signal Temporal Logic (STL) [ 11 ] provides a formal language for such properties over real-valued signals, and its quantitative robustness semantics assign a continuous score measuring the degree of satisfaction or violation. For bounded temporal operators (e.g., \square_{[0,5]}\,\mu_{\mathrm{safe}} ), the ground-truth robustness at time t depends on signal values up to t{+}5 , which a causal monitor cannot observe. Tools such as STLCG++ [ 9 ] compute the exact robustness offline; when restricted to the available observations, they define a non-learned baseline that can evaluate only the portion of the specification whose temporal horizon has already elapsed. Fig. 1: Schematic of the Recurrent Differentiable Ternary Logic Gate Network. (a) The R-DTLGN cell. (b) Unrolled cell. (c) Hardening into Logic Circuit. The gap between this causal baseline and the oracle (full-trajectory) evaluation is fundamental: it exists for every bounded formula with a non-trivial future time horizon. Any learned monitor attempts to bridge this gap by exploiting spatio-temporal patterns in training data to predict verdicts that a causal evaluator cannot resolve from the available observations alone. Standard recurrent architectures such as LSTM and GRU can serve this role, but they provide no structural guarantees about what happens when input information degrades. Their continuous-valued hidden states carry no inherent distinction between “determined” and “uncertain,” so degraded inputs (sensor dropout, indeterminate predicates) can produce arbitrarily wrong outputs. Kleene’s strong three-valued logic [ 7 ] is the natural formalism for reasoning about temporal properties under partial information. It extends classical Boolean logic with a third value, 0 , representing “unknown.” The Kleene connectives (AND, OR, NOT) propagate this unknown value conservatively: a conjunction with one false input is false regardless of the other, but a conjunction of true and unknown yields unknown. This conservative propagation is precisely what a monitor operating under input uncertainty should exhibit. A learned monitor that operates natively in Kleene’s three-valued domain acquires two complementary capabilities. First, like any learned monitor, it exploits temporal patterns in training data to predict verdicts that a causal evaluator cannot resolve; this prediction capability is what makes it useful over the causal baseline. Second, unlike standard recurrent architectures, it provides structural degradation guarantees : when input information is lost (predicates become indeterminate, sensors fail), the monitor’s verdicts degrade toward “unknown” rather than flipping to wrong answers. The prediction capability bridges the causal gap; the degradation guarantee ensures robustness to input-level uncertainty. These two capabilities are complementary and non-overlapping. We propose the Recurrent Differentiable Ternary Logic Gate Network (R-DTLGN) as a learned monitor that operates natively in Kleene’s domain. Differentiable Logic Gate Networks (DLGNs) [ 12 , 13 ] replace conventional arithmetic neurons with discrete two-input logic gates, producing pure logic circuits at inference. Polynomial Surrogate Training (PST) [ 4 ] extends DLGNs to Kleene’s ternary domain \mathbb{T}=\{-1,0,+1\} by representing each neuron as a degree- (2,2) polynomial with 9 learnable coefficients; at inference, the network hardens to an exact ternary logic circuit (Section III-D ). The R-DTLGN augments this feedforward architecture with a persistent hidden state for temporal reasoning: at each timestep the cell ingests the current predicate values and its previous state, processes them through L layers of ternary PST gates, and produces an updated state and output verdict. The hidden state is initialized to (0,\ldots,0) , the all-unknown state, so the monitor begins with no prior commitment. Because every neuron in the hardened circuit is a ternary gate on \mathbb{T} , the R-DTLGN’s inference-time computation is a composition of Kleene connectives, inheriting the conservative uncertainty propagation that standard RNNs lack. Contributions We analyze the R-DTLGN as a causal STL monitor and provide four contributions: 1) The R-DTLGN architecture. We introduce the Recurrent Differentiable Ternary Logic Gate Network, a recurrent cell whose neurons are degree- (2,2) polynomial surrogates during training and exact ternary logic gates at inference. Operating natively in Kleene’s three-valued domain, the R-DTLGN combines the predictive capacity of a learned monitor with the conservative uncertainty propagation of ternary logic. We introduce a novel hardening routine for converting the soft learned network into logic gate circuits in the recurrent setting based on trajectory distillation. 2) Degradation guarantees from Kleene structure. We prove that R-DTLGN cells composed of information-monotone gates satisfy two per-timestep properties: principled abstention (all-unknown inputs produce all-unknown outputs) and input certainty monotonicity (replacing a determined input with unknown can only make outputs less determined, never flip them). These properties guarantee graceful degradation under input loss, a structural advantage over standard recurrent monitors. 3) Realizability bounds from STL formula structure. Given a bounded STL formula \varphi , we derive a lower bound B(\varphi) on the cell’s hidden state dimension, decomposed additively by temporal operator type. This connects STL formula complexity to neural architecture sizing, replacing hyperparameter search with a formula-driven specification. 4) Empirical validation. On a suite of 6 bounded STL specifications over PointMaze navigation data, we evaluate both prediction performance (R-DTLGN vs. causal STLCG++ vs. vanilla RNN) and degradation behavior (predicate dropout experiments confirming principled abstention and input certainty monotonicity in the learned cell). II Related Work II-A STL Monitoring and the Causal Gap Offline STL monitoring tools such as Breach [ 6 ] , S-TaLiRo [ 1 ] , STLCG++ [ 9 ] compute quantitative robustness given the complete signal trajectory. Online monitoring algorithms process the signal incrementally but still require future samples to resolve bounded