Take a specification language and keep applying a handful of natural operations to it: "the safety part of it", "it eventually holds", "some suffix satisfies it", and "not". Do you get infinitely many different languages, or does the process stop? For languages of finite words, Charlier, Domaratzki, Harju and Shallit showed that it stops. Kleene star, prefix, suffix, factor, subword, reversal, positive closure and complement together produce at most 5,676 distinct languages from any starting language (Composition and orbits of language operations: finiteness and upper bounds). The proof is an algebraic argument in the style of Kuratowski's 1922 "14-set" theorem from topology, finished by a mechanical search. Nobody has asked the same question for languages of infinite words (ω-languages). These are the languages that temporal specifications in verification actually denote. Over infinite words, the cheap step in the finite-word story becomes the expensive one. Complement is free on a deterministic automaton for finite words, but complementing a nondeterministic Büchi automaton (an automaton over infinite words that accepts when it visits an accepting state infinitely often) costs $2^{O(n\log n)}$ states in general (On the power of finite ambiguity in Büchi complementation).
This note proposes to build the infinite-word analogue of orbit finiteness and to use it computationally. The plan has two steps. First, prove which chains of ω-closure operations and complement collapse to a finite set, and compute the rewrite identities that cause the collapse. Second, use those identities as a compiler: before building any automaton, rewrite an operation chain into a normal form with as few complementations as possible, and place each remaining complementation where it is provably cheap. The claim is that orbit algebra controls automaton cost, not just set identity. In particular, every complement that directly follows the safety closure acts on a safety language, so it can be done with a subset construction ($2^n$ states) instead of rank- or slice-based complementation.
Core Claim
Let $L \subseteq \Sigma^\omega$. We study four operations. Each is extensive ($L \subseteq x(L)$), monotone, and idempotent, which means each is a closure operator in the sense used by Charlier et al. The first, $\mathrm{cl}$, is safety closure: the infinite words all of whose finite prefixes extend into $L$. This is topological closure in the standard topology on infinite words. The second, $e(L)=\Sigma^*L$, is the "eventually" extension. The third, $s(L)$, keeps every suffix of a word in $L$. The fourth, $d$, closes downward under infinite scattered subsequences. To these we add complement $c$. Reversal has no infinite-word counterpart, so one of the involutions the finite-word normal forms depend on is missing. This makes the analogue a genuinely different monoid, not a relabelling.
The Charlier et al. meta-identity holds for any two closure operators $x,y$:
$$x\,c\,y\,c\,x\,c\,y \;\equiv\; x\,c\,y .$$
It applies unchanged here. Finiteness of the whole orbit therefore reduces to finiteness of the products of closures without complement. That in turn depends on commutation and absorption identities among $\mathrm{cl}, e, s, d$, which nobody has worked out. Safety closure plus complement alone gives at most 14 sets, because that is literally Kuratowski's theorem in this topology. Everything beyond that pair is open.
The proposal makes three falsifiable claims.
The first is that the orbit under $\{\mathrm{cl}, e, s, c\}$ is finite with a computable bound. With $d$ added, it is either finite or has an explicit infinite witness, and either outcome is a result.
The second concerns a quantity we call the complementation profile of a normal form: the number of $c$'s, each tagged by the operation it follows. Every orbit element has a normal form in which at most a small constant number of complements are "expensive", meaning they do not follow $\mathrm{cl}$.
The third is that a pipeline which rewrites to normal form and then uses closure-aware complementation computes full orbits of real specification automata. It should finish on more seeds, and produce smaller intermediate automata, than evaluating chains directly with a general complementation tool.
Research Program
The theory track adapts the Charlier et al. method. It has three parts:
- Derive pairwise identities among the four closures. Example: is $s\,e \equiv e\,s$? Is $\mathrm{cl}\,e$ absorbed by $e\,\mathrm{cl}$?
- Instantiate the meta-identity across all closure pairs.
- Bound the closure-only monoid, then the full orbit.
Identities will be proposed by search and then proved by hand. Before $d$ is admitted, we must show that downward closure of ω-regular languages is effectively ω-regular. If we cannot, $d$ is dropped and the core result rests on $\{\mathrm{cl}, e, s, c\}$. For lower bounds, we search for single starting automata whose orbits reach the derived upper bound. The finite-word global bound of 5,676 has no matching witness, so we expect tightness to be the hard part here too.
The search engine is where complementation limits enter. In the finite-word setting, checking whether two orbit elements are the same language is cheap with DFAs. Over infinite words, every equality test is a language-containment check, and each check hides a complementation. The engine therefore needs a cheap complement wherever one exists. We will implement it on top of Spot, the same base library COLA uses.
The complementation dispatcher routes each $c$ according to what precedes it:
- After $\mathrm{cl}$: the operand is a safety language, so the dispatcher trims the automaton, applies the subset construction, and treats it as a co-safety automaton.
- After $c$: the double complement is erased syntactically.
- On a finitely ambiguous automaton: it uses the $O(4^n)$ slice-based construction of On the power of finite ambiguity in Büchi complementation.
- Otherwise: it falls back to general complementation.
We will also measure whether the closures preserve finite ambiguity, the property that each accepted word has a bounded number of accepting runs. We expect $e$ and $s$ to destroy it. Each can start a run at arbitrarily many points, and that is exactly the failure mode that sends complementation back to the super-exponential regime. Confirming or refuting this tells us how far the Feng et al. collapse can be used along an orbit. The question is untouched in that work, which treats complementation only as a single final step.
Baselines
The naive reference point is left-to-right evaluation. Each operation in a chain is applied in turn, and every complement uses Spot's general complementation, with no algebraic rewriting. This is what a practitioner would do today. It shows how much the algebra buys.
The strongest competitor is "determinize once, then compute". Each seed is determinized with COLA (Divide-and-Conquer Determinization of Büchi Automata Based on SCC Decomposition), complements are done by swapping acceptance on the deterministic automaton, and the result is re-determinized only when a closure breaks determinism. COLA is the best determinizer reported in the file. On the 15,710 cases of Automata-Benchmarks that COLA, Spot and Owl all solved, it averaged 44 states against 65 for Spot and 87 for Owl. It solved 15,903 of 15,913 instances within a 10-minute timeout, against 15,862 for Spot and 15,749 for Owl. For LTL-derived NBAs it averaged 9 states against 11 for Spot.
The file reports no complementation numbers on these benchmarks: no reported result found on Lacuna for Büchi complementation size or runtime on Automata-Benchmarks. It also reports none for computing orbits of ω-languages, since no such work exists. We will therefore run all baselines ourselves.
Fairness rules:
- every method gets the same seeds, the same 10-minute per-orbit budget matching COLA's protocol, and the same memory cap;
- the same final minimization pass is applied everywhere;
- no method gets tuned heuristics that the others lack.
Two ablations isolate the key ingredients. One uses normal-form rewriting with general complementation everywhere. The other uses closure-aware complementation without rewriting. Beating the strongest baseline means two things. The full pipeline must completely compute strictly more seed orbits within budget, and its median of the largest intermediate automaton must be smaller on the orbits both methods finish. The ablations should show which ingredient carries the gain.
Why not just…?
Why not just appeal to Kuratowski's theorem in this topology? It does settle safety closure plus complement, giving 14 sets, and we inherit that for free. It says nothing once $e$, $s$ or $d$ enter. These are not topological closures of the same space, so their interaction with $\mathrm{cl}$ is exactly the new algebra. The finite-word work shows the jump in difficulty: $\{p,c\}$ is a tidy 14, while adding star gives 1,066 and only a computer-assisted bound (Finite Orbits of Language Operations).
Why not just determinize once and complement for free? This is the real threat, and it is why it is our strongest baseline. Two things work against it. The closures $e$ and $s$ reintroduce nondeterminism, because they guess where to start, so a deterministic representation must be rebuilt after each one at $2^{O(n\log n)}$ worst-case cost (Can Nondeterminism Help Complementation?). Our pipeline instead pays a $2^n$ subset construction wherever a complement follows $\mathrm{cl}$. If benchmark orbits rarely place $e$ or $s$ between complements, the deterministic baseline may match us, and the head-to-head comparison above will show this directly. In that case the contribution narrows to the theory and the profile bound, and we will say so.
Why not just switch to families of DFAs, where complement is constant cost? Saturated families of DFAs do make complement trivial. But reaching them from a Büchi automaton costs $2^{\Omega(n\log n)}$, returning to parity automata can cost $2^{n-1}$ states, and checking saturation is only known to be in PSPACE (Families of DFAs as Acceptors of ω-Regular Languages). Closures such as $e$ and $s$ on this representation have no known constructions. Swapping representations moves the cost; it does not remove it.
Why not just restrict seeds to finitely ambiguous automata? The $O(4^n)$ bound is attractive, but it helps only while ambiguity stays bounded. Our ambiguity-preservation measurement tests whether one application of $e$ or $s$ already destroys it. If it does, this restriction cannot carry an orbit computation past the first step.
Proposed Experiments
Seeds. Seeds come from two sources: the 644 LTL-derived NBAs, which represent realistic specifications, and Automata-Benchmarks with its 15,913 NBAs, used for scale. Both are used in the COLA evaluation. We add exhaustively enumerated Büchi automata with at most 4 states over binary and ternary alphabets, which serve the witness search.
Measurements. For each seed we record:
- the number of distinct languages in its orbit;
- the complementation profile of each element;
- the largest automaton built;
- whether the full orbit finished within budget.
Decisive checks. The theory track succeeds if the search terminates with a closure-only monoid that hand proofs confirm, and if the exhaustive small seeds reach a lower bound of documented distance from the upper bound. It fails informatively if some chain over two closures keeps producing new languages on a small seed. That would be an infinite-orbit witness, and the result would be as interesting as the proper-prefix breakdown in the finite-word case. The algorithmic track succeeds under two conditions:
- the full pipeline beats COLA-based determinize-once on fully computed orbits within the same budget;
- the ablations attribute the gain mainly to placing complements after safety closure rather than to generic rewriting.
The ambiguity measurement is reported regardless of outcome, as the fraction of finitely ambiguous seeds that remain finitely ambiguous after each closure.
References
- Composition and orbits of language operations: finiteness and upper bounds
- On the power of finite ambiguity in Büchi complementation
- Divide-and-Conquer Determinization of Büchi Automata Based on SCC Decomposition
- Finite Orbits of Language Operations
- Can Nondeterminism Help Complementation?
- Families of DFAs as Acceptors of ω-Regular Languages