Abstract
Saturation is a fundamental game-semantic property satisfied by strategies that interpret higher-order concurrent programs. It states that the strategy must be closed under certain rearrangements of moves, and corresponds to the intuition that program moves (P-moves) may depend only on moves made by the environment (O-moves). We propose an automata model over an infinite alphabet, called saturating automata, for which all accepted languages are guaranteed to satisfy a closure property mimicking saturation. We show how to translate the finitary fragment of Idealized Concurrent Algol (FICA) into saturating automata, confirming their suitability for modelling higher-order concurrency. Moreover, we find that, for terms in normal form, the resultant automaton has linearly many transitions and states with respect to term size, and can be constructed in polynomial time. This is in contrast to earlier attempts at finding automata-theoretic models of FICA, which did not guarantee saturation and involved an exponential blow-up during translation, even for normal forms.
Introduction
In the formal verification of higher-order concurrent programs, game semantics provides a robust framework by modeling program execution as a dialogue between a Proponent (the program) and an Opponent (the environment). A critical requirement for these models is saturation: the principle that the meaning of a concurrent program should be invariant under the reordering of independent actions. If an environment and a program perform unrelated moves, the model must account for all valid interleavings.
Historically, automata-based models for concurrency have struggled with two primary issues. First, they did not natively guarantee saturation; the property had to be enforced through complex, manual closure operations. Second, the translation from program code to automata often triggered an exponential "state-space explosion," making these models computationally expensive and impractical for large-scale verification tasks.
Saturating Automata (SATA)
To address these challenges, this research introduces Saturating Automata (SATA). Unlike traditional finite-state machines, SATA operate over an infinite alphabet. This allows the model to represent "justification pointers"—the dependencies between moves in a game—without requiring an infinite state space.
The SATA model incorporates several key technical innovations:
- Tree-Structured Configurations: SATA maintain a hierarchical tree of "jobs" or sub-processes rather than a flat state.
- Restricted Communication: Transitions are carefully constrained so that a node in the configuration tree can only communicate with its direct parent or children. By preventing direct communication between "sibling" parallel processes, the model naturally enforces the saturation property by design.
- Inductive Translation: The authors provide a systematic method for translating terms from the Finitary fragment of Idealized Concurrent Algol (FICA) into SATA.
Key Insights
The core innovation of this work is that saturation can be a structural byproduct of the automaton rather than a secondary check. By limiting information flow between branches of the configuration tree, independent moves can be swapped without altering the automaton's acceptance, ensuring native closure.
Furthermore, the use of data values from an infinite set (data languages) provides an elegant solution for modeling justification pointers. This approach avoids the complexity of previous "split" or "leafy" automata models, which were inherently prone to exponential growth even for simple program terms.
Results and Efficiency
The SATA model achieves significant performance gains over prior methods:
- Linear Complexity: For FICA terms in $\beta$-normal $\eta$-long form, the resulting SATA has a number of states and transitions that grows linearly with the size of the program term.
- Polynomial Construction: The translation process is efficient, with the automaton being constructible in polynomial time (specifically quadratic time).
- Full Abstraction: The model is "fully abstract," meaning it captures exactly the observational behavior of FICA programs, ensuring that two programs are equivalent in the model if and only if they behave identically in any context.
Conclusion and Future Work
While SATA offers a linear-sized representation for normal forms, the conversion of arbitrary FICA terms into these forms can still be computationally intensive. Additionally, while the model is efficient to construct, the efficiency of "emptiness testing"—checking for the reachability of error states—remains a subject for future investigation. The authors anticipate that SATA will serve as a foundation for new software verification tools capable of handling higher-order concurrency with unprecedented efficiency.
Summary updated