Imagine you are monitoring a continuous stream of data—such as program execution traces, network packets, or sensor readings—that is supposed to adhere to a strict formal specification. Due to transmission noise, software bugs, or unexpected system behavior, the incoming sequence occasionally violates this specification. How do you "repair" the stream to fit the target language using the minimum number of edits?
In an offline setting, you have the luxury of inspecting the entire string before making any changes. You can compute the global edit distance and find an optimal sequence of insertions, deletions, or substitutions. However, in real-time systems, data must be processed as it arrives. You must make repair decisions character by character, with incomplete information about the future of the stream. This constraint defines the domain of streaming string repair.
Why Streaming Changes the Cost Landscape
The fundamental challenge of streaming repair is that local decisions can have catastrophic global consequences. When a streaming transducer encounters an unexpected character, it must immediately decide whether to delete it, substitute it, or insert a corrective character to keep the sequence valid up to that point.
As highlighted by Chaubal et al. in How to Travel between Languages, this lack of lookahead can cause finite edit distances to balloon into infinite "streaming costs." Without knowing what lies ahead, a transducer might make a series of local corrections that lead into a structural dead end, forcing it to continuously edit subsequent characters just to maintain validity.
To understand when a language can be reliably corrected, researchers study bounded repairability: the condition under which every string from a source language can be transformed into a target language without exceeding a fixed, uniform upper bound on the number of edits. In Bounded repairability of word languages, Puppis et al. developed formal structural conditions to determine when this is possible. By analyzing the alignment between the automata representing the source and target languages, they characterized the exact boundaries where uniform edit limits can be guaranteed.
The Complexity Paradox: When Streaming is Easier
Intuitively, making decisions with less information should make a problem computationally harder. However, the theoretical landscape of string repair presents a fascinating paradox: enforcing a streaming constraint can actually make the underlying computational problems more tractable.
Consider the problem of verifying whether a specification can always be repaired within a fixed number of edits. In Regular Repair of Specifications, Puppis et al. demonstrated that for Deterministic Finite Automata (DFAs), this bounded repair problem is coNP-complete in a non-streaming context, but drops to PTIME-complete in a streaming context.
Why does this happen?
- In the non-streaming setting, the algorithm must evaluate all possible global alignments and future paths across the entire string, leading to a combinatorial explosion of potential edit sequences.
- In the streaming setting, the strict requirement to process character-by-character restricts the strategy space. The problem effectively reduces to finding a winning strategy in a turn-based safety game played over the synchronized product of the source and target automata. Because the state space of this game is tightly constrained by the automata structures, it can be evaluated efficiently in polynomial time.
Similarly, Puppis et al. showed in The Cost of Traveling between Languages that the asymptotic cost—the worst-case percentage of edits required per input character over infinitely long strings—is polynomial-time computable for streaming setups. This tractability makes real-time sequence correction highly viable for practical deployment.
Maximizing Partial Repairs via MDPs
What happens if a complete, bounded repair is impossible for a given source language? If some strings simply require too many edits, a rigid framework would declare the language "unrepairable." To handle these scenarios gracefully, we can pivot to a softer question: what is the maximum fraction of strings that can be successfully repaired under a strict edit budget?
This is known as the partial-repair problem. To solve it, Chaubal et al. introduced a framework based on $(\eta, \alpha)$-streaming transducers, where $\eta$ represents the achievable repair fraction and $\alpha$ represents the cost bound.
The authors proved that this problem can also be solved in polynomial time by modeling the streaming repair process as a Markov Decision Process (MDP). By converting the source and target DFAs into an MDP where transitions represent character arrivals and actions represent edit operations, the problem of finding the optimal repair strategy translates into finding a policy that maximizes conditional probabilities. This allows systems to optimize resource allocation and maximize data recovery even when perfect repair is mathematically impossible.
The Non-Deterministic Frontier
While the picture for deterministic automata is clean and polynomial, non-determinism introduces significant hurdles. When the target specification is represented by a Non-deterministic Finite Automaton (NFA), a streaming repair agent faces a double layer of uncertainty: it does not know the future of the input stream, nor does it know which internal state path the target NFA will ultimately prefer.
As noted in both Regular Repair of Specifications and Bounded repairability of word languages, the exact computational complexity for streaming repair with NFA specifications remains an open frontier. The current theoretical bounds exhibit a significant gap, established as PSPACE-hard from below but only bounded from above within EXPTIME. Resolving this gap remains a key challenge for fully unlocking online sequence correction in complex, non-deterministic environments.
Key Foundational Work
Bounded repairability of word languages (2013) — contributed 9 concept elements to this direction.
Regular Repair of Specifications (2011) — contributed 9 concept elements to this direction.
How to Travel between Languages (2013) — contributed 6 concept elements to this direction.