Answer set programming describes changing systems with rules that allow default conclusions: "if the light was on and nothing switched it off, it is still on." Temporal Equilibrium Logic (TEL) makes such rules precise over sequences of states. A sequence (a trace) counts as a model only if it is minimal, meaning no smaller set of facts would also satisfy the rules. For ordinary temporal logic over finite traces, there is a mature algebraic theory. Each property of traces is summarized by its syntactic monoid, the smallest algebra that tracks how trace prefixes compose. Properties are then classified by which equations that monoid satisfies. For example, "no internal group structure" (aperiodicity) means the property cannot count modulo any number. This note proposes computing and classifying the syntactic monoids of TEL's stable-trace languages. The central open question is whether the minimality step can create counting structure that the underlying rules lack.
This matters because the monoid class of a property determines how cheaply it can be monitored. The Transformation Logics shows that flip-flop-only monoids give AC⁰ data complexity, solvable groups give ACC⁰, and non-solvable groups give NC¹-completeness. No comparable ladder exists for non-monotonic temporal reasoning. The research file flags this explicitly as an absent algebraic structure theory. Monitoring cost for TEL is currently analyzed only syntactically.
Core Claim
Fix a finite set of atoms and consider finite traces. Let $\varphi$ be a TEL theory. A pair of traces $(h,t)$ has a "here" trace $h$ contained pointwise in a "there" trace $t$, and $\models$ is satisfaction in Temporal Here-and-There (THT), the monotonic base logic. The stable-trace language of $\varphi$ is
$$L(\varphi) = \{\, t \;:\; (t,t)\models\varphi \text{ and there is no } h \subsetneq t \text{ with } (h,t)\models\varphi \,\}.$$
The THT pair language $P(\varphi) = \{(h,t) : (h,t)\models\varphi\}$ is defined with the same temporal operators as linear temporal logic over finite traces. We therefore expect it to be star-free and its monoid aperiodic. $L(\varphi)$, however, is obtained from $P(\varphi)$ by projecting away $h$ and complementing, and projection is exactly the operation that can turn star-free languages into counting languages.
Our claim has two parts. The first part is that $L(\varphi)$ is regular over finite traces with a computable syntactic monoid. The second part is a question we will settle: either equilibrium selection preserves aperiodicity, or some explicit theory produces a group, with a precise description of which fragments do so. We conjecture a specific link to the fragment boundaries that Computational Aspects of Progression for Temporal Equilibrium Logic identifies:
- Normal and head-cycle-free (HCF) programs, whose progression is polynomial, yield stable-trace monoids in the flip-flop/aperiodic class.
- Any group structure can arise only from disjunctive rules with head cycles, the fragment where that paper's progression becomes $D^p$-complete.
If true, this gives the first variety-theoretic explanation of a complexity boundary in non-monotonic temporal reasoning. If false, the counterexample is itself a new expressiveness result about TEL.
Relation to Prior Work
Three lines of work supply the method.
- The Transformation Logics supplies the Krohn-Rhodes ladder: it decomposes a monoid into flip-flops and simple groups, and ties each layer to a circuit class. It is purely monotonic and past-looking. We apply its classification to languages produced by minimality, which it does not treat.
- An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic and Two-variable logics with some betweenness relations show that fine-grained fragment membership can be decided by checking monoid equations. That is the style of fragment characterization we want for normal and HCF programs.
Two lines of work motivate the proposal.
- The progression paper leaves the transition algebra of its operator unanalyzed.
- Contracted Temporal Equilibrium Logic removes stuttering (repeated identical states) with contractor functions and proves that stable models of next-free theories coincide with stutter-free stable models. We will test whether these contracted languages fall into stutter-invariant monoid classes. The paper leaves this algebraic reading open.
The static epistemic line constrains the design. Epistemic Equilibrium Logic and The Modal Logic S4F, the Default Logic, and the Logic Here-and-There prove that strong equivalence, meaning interchangeability inside any larger program, reduces to equivalence in a monotonic base logic (EHT or S4F). The temporal analogue says that two theories are strongly equivalent exactly when their THT pair languages coincide, and this is decidable through the pair monoid alone.
This division tells us where algebra can and cannot help. Variety theory is closed under homomorphisms and submonoids, but a sub-model of a stable model need not be stable. We therefore do not try to build a "non-monotonic variety." We keep the monotonic pair monoid for equivalence and study the stable-trace monoid only as an invariant of a single theory. This choice follows the research file's warning: pushing algebra onto the selection step naively risks inflating equivalence checking from the co-NP bound of Strong Equivalence for Epistemic Logic Programs Made Easy to EXPSPACE.
Research Program
Construction. We build a pipeline in four steps.
- Translate a TEL theory over finite traces into an automaton over pair-letters $(h_i, t_i)$, reusing the standard temporal-logic-to-automaton construction applied to THT semantics.
- Obtain $L(\varphi)$ by subset-style projection and complementation, followed by intersection with the diagonal condition $(t,t)\models\varphi$.
- Minimize the result.
- Compute its transition monoid.
Monoid computation is exponential in the worst case, which is consistent with TEL monitoring being EXPSPACE-complete. We will report sizes honestly rather than claim tractability.
Classification. For each monoid, we test the following:
- aperiodicity, via the equation $x^\omega = x^{\omega+1}$, where $x^\omega$ denotes the idempotent power of $x$;
- the presence and solvability of maximal subgroups;
- membership in the two-variable class DA;
- for next-free theories, stutter-invariance.
Theory. The theoretical track attempts two things. The first is a proof that head-cycle-free minimality can be simulated by a cascade of flip-flops. The intuition is that HCF programs can be shifted to normal ones, and normal-program minimality is checked by acyclic unfounded-set reasoning, which should not require counting. The second is a targeted search for a disjunctive theory whose stable traces have, for example, even length. Parity is the canonical sign of group structure.
Epistemic extension. If the temporal case resolves cleanly, we lift the construction to world views of Epistemic Here-and-There (EHT) over traces, using sets of traces as letters. We then ask whether the "ignorance maximization" step of Epistemic Equilibrium Logic adds a further algebraic layer. This extension is secondary and conditional on the first result.
Baselines
Naive reference. The do-nothing reference is bounded enumeration: for each trace length up to a bound, enumerate candidate traces and check minimality with a THT satisfiability call. This answers membership but gives no classification and no monitor. It anchors correctness, since every automaton we build must agree with it on all traces up to the bound. It also anchors per-step monitoring cost.
Strongest existing method. The strongest competitor is DAG-based formula progression from Computational Aspects of Progression for Temporal Equilibrium Logic. It rewrites the theory step by step, sharing subformulas in a directed acyclic graph, and is polynomial for normal and HCF programs. It is the best existing way to monitor TEL streams, and it already tracks the normal/HCF boundary we want to explain.
- Fair comparison. We implement it ourselves from the paper's description, since no released implementation is in the file. It runs on the same theories and the same streams on identical hardware.
- Metrics. We compare per-step latency, memory, and agreement of the three-valued verdicts.
- Reported numbers. No reported result was found on Lacuna for progression runtime on any benchmark, so there is no published number to beat.
- What counts as winning. The monoid monitor must agree exactly on verdicts and have strictly lower per-step latency on long streams for aperiodic theories. It must also supply a classification that progression cannot, namely a prediction of which theories admit constant-state flip-flop monitors.
Key ablation. The ablation computes the syntactic monoid of the THT pair language $P(\varphi)$ instead of $L(\varphi)$. If the two always land in the same Krohn-Rhodes class, equilibrium selection adds no algebraic content, and the interesting half of the claim is false.
Negative control. Theories that satisfy the equation (EM), which Contracted Temporal Equilibrium Logic shows collapses TEL to classical temporal logic, must yield aperiodic monoids.
Why not just…?
Why not just use SE-functions? Strong Equivalence for Epistemic Logic Programs Made Easy decides strong equivalence of epistemic programs in co-NP without any modal or algebraic detour. For static equivalence, this is the right tool and we do not compete with it. SE-functions are defined for single-state programs, however. They do not say what temporal property a theory defines or how hard it is to monitor. Our equivalence story also stays at the monotonic pair-language level, in the same spirit as SE-models.
Why not just use DAG progression, which is already polynomial? This is the real threat for monitoring speed. Progression may match a monoid monitor on normal programs, because both are polynomial. The comparison above settles the speed question empirically. The proposal's distinct contribution is explanatory: a monoid equation that predicts, before any stream arrives, whether a theory needs counting. If progression's cost profile tracks our algebraic classes exactly and the monoid monitor is never faster, we will report the algebra as an analysis tool only.
Why not just compile to SAT with lazy loop formulas? SAT-Based Answer Set Programming and Loop Formulas for Circumscription solve stable-model search efficiently. For tight theories, stable models reduce to Clark's completion, a direct classical translation of the rules. These methods find models of a fixed length and do not characterize the set of all stable traces across lengths, which is where group structure would show up. We will use a SAT-based minimality check as the oracle inside the naive baseline.
Proposed Experiments
The file contains no TEL benchmark with reported results, so we construct the suite.
- Synthetic theories. We generate theories over 2–5 atoms in three fragments (normal, HCF, and disjunctive with head cycles), with bounded operator nesting.
- Adapted instances. We add temporal encodings adapted from the benchmark families used by SAT-Based Answer Set Programming, namely Hamiltonian-circuit style path constraints and bounded-model-checking style transition systems. For these families, no reported number was found on Lacuna.
Measurements. For every theory, we report:
- the minimal automaton size and monoid size;
- the aperiodicity verdict;
- the maximal-subgroup structure;
- DA membership;
- stutter-invariance for next-free theories.
Decisive checks. Three outcomes settle the claims.
- Fragment boundary. If any normal or HCF theory yields a non-aperiodic stable-trace monoid, the fragment conjecture is refuted.
- Selection effect. If some disjunctive theory yields a group while its pair monoid is aperiodic, we have shown that equilibrium selection alone creates counting, and we extract that theory as a minimal counterexample to study by hand.
- Stuttering. Across next-free theories, contracted stable-trace languages should be stutter-invariant in every case. A single failure would show that the contraction of Contracted Temporal Equilibrium Logic is not algebraically what it appears to be.
The monitoring comparison against DAG progression then determines whether the classification also pays off in runtime.
References
- The Transformation Logics
- Computational Aspects of Progression for Temporal Equilibrium Logic
- An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic
- Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership
- Contracted Temporal Equilibrium Logic
- Epistemic Equilibrium Logic
- The Modal Logic S4F, the Default Logic, and the Logic Here-and-There
- Strong Equivalence for Epistemic Logic Programs Made Easy
- SAT-Based Answer Set Programming
- Loop Formulas for Circumscription