Graded Monads in the Semantics of Nominal Automata
Hannes Schulze, Lutz Schröder, Üsame Cengiz · 2025
Read Graded Monads in the Semantics of Nominal Automata by Hannes Schulze, Lutz Schröder, Üsame Cengiz (2025) 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-2510-24353.txt.
Introduction
Hannes Schulze and two co-authors build graded meanings for nominal systems, which are models of languages and processes that carry data. Name allocation in these systems eases the known hardness of register based models. There is a trade off between how much the model can express and how fast it can be checked. One class, regular nondeterministic nominal automata, matches a lossy form of register automata when names must be fresh locally.
Full register automata are much harder to check. The nominal class, by contrast, allows inclusion tests in a bounded space class. Trace inclusion in the base systems shares that bound. The graded meanings refine how these systems are read. The aim is to keep the speed gains while drawing finer lines between data carrying processes.
Catalog record
| CREATOR | Hannes Schulze, Lutz Schröder, Üsame Cengiz |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 147 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-24353
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graded Monads in the Semantics of Nominal Automata Hannes Schulze, Lutz Schröder, Üsame Cengiz Abstract Nominal automata models serve as a formalism for data languages, and in fact often relate closely to classical register models. The paradigm of name allocation in nominal automata helps alleviate the pervasive computational hardness of register models in a tradeoff between expressiveness and computational tractability. For instance, regular nondeterministic nominal automata (RNNAs) correspond, under their local freshness semantics, to a form of lossy register automata, and unlike the full register automaton model allow for inclusion checking in elementary complexity. The semantic framework of graded monads provides a unified algebraic treatment of spectra of behavioural equivalences in the setting of universal coalgebra. In the present work, we extend the associated notion of graded algebraic theory to the nominal setting. In the arising framework of graded nominal algebra, we give an algebraic theory capturing the local freshness semantics of RNNAs. 1 Introduction Languages over infinite alphabets are often briefly termed data languages , in a view where letters are understood as abstracting elements of data types that are either infinite or prohibitively large. Typical examples include data values in XML documents [ 34 ] , object identities [ 23 ] , or nonces in cryptographic protocols [ 28 ] . One of the most prominent formalisms for data languages are register automata (originally introduced under the name finite memory automata [ 25 ] ), which have a fixed finite number of registers in which letters encountered in the input word can be stored for later comparison with other letters. The world of register automata differs markedly from that of standard finite automata. In particular, non-deterministic register automata cannot in general be determinized. Inclusion checking of register automata is undecidable unless either the number of registers or the power of control (deterministic/non-deterministic/alternating) is severely restricted. For instance, inclusion checking of non-deterministic register automata is undecidable unless the number of registers is restricted to at most two [ 25 ] ) or the power of control is restricted to unambiguous automata [ 33 , 7 ] ; and inclusion checking of alternating register automata is undecidable unless the number of registers is restricted to one, and even then is not primitive recursive [ 8 ] . An alternative view of register automata is provided by automata based on nominal sets [ 4 ] , in which, roughly speaking, the underlying set of names plays the role of the infinite alphabet. In particular, non-deterministic orbit-finite automata (NOFA) are equivalent to register automata with non-deterministic update [ 26 ] , and as such inherit the computational difficulty of register automata. Regular non-deterministic nominal automata (RNNA) [ 39 ] have been proposed as a model that trades some of the expressiveness of register automata for computational tractability; in particular, RNNA allow inclusion checking in exponential space, and more precisely even in parametrized polynomial space with the number of registers as the parameter (recall that already inclusion checking of standard non-deterministic finite automata is PSpace -complete). Technically, RNNAs (unlike NOFAs and register automata) disallow infinite branching but instead feature explicit name-allocating transitions that effectively read fresh names from the input string. Here, the relevant notion of freshness is governed by the discipline imposed on renaming bound names in name-allocating transitions: A global freshness semantics, where newly read names are required to be fresh w.r.t. all previous names, is enforced by a discipline of clean renaming (avoiding shadowing of bound names), while local freshness , i.e. freshness w.r.t. (some of) the names currently stored in the registers, is induced by unrestricted renaming according to the usual rules of \alpha -equivalence familiar from \lambda -calculus. These concepts have been extended to nominal automata models processing trees [ 37 ] and infinite words [ 43 ] , as well as to alternating nominal automata [ 16 ] . The categorical framework of graded semantics [ 32 ] provides a unified treatment of spectra of semantics of automata models and concurrent systems, such as the well-known linear-time / branching-time spectrum of semantics of labelled transition systems [ 9 ] . This is achieved by combining the setting of universal coalgebra [ 38 ] with additional algebraic laws introduced via the choice of a graded monad [ 40 ] , a categorical structure that abstractly represents a graded algebraic theory . Here, the notion of grade intuitively corresponds to depth of look-ahead, measured in (exact) numbers of transition steps. The notion of graded theory has originally been introduced for set-based graded monads [ 40 ] ; it has been extended to graded monads on the category of posets [ 12 ] , the category of metric spaces [ 14 ] , and more generally to graded monads on categories of relational structures [ 11 , 15 ] . Benefits of casting a given semantics as a graded semantics include instantiation of generic results obtained for graded semantics, such as logical characterizations [ 32 , 9 , 12 , 14 ] and game characterizations [ 13 , 15 ] . In the present work, we launch into extending the core results of graded theories to graded monads on nominal sets (a case that is not covered by the above-mentioned results on categories of relational structures). Specifically, we introduce a notion of graded nominal algebra, based on a simplification of Gabbay and Mathijsen’s framework of nominal algebra [ 21 ] . We show that graded nominal theories induce graded monads on the category of nominal sets and, crucially, that graded nominal theories of depth 1 induce graded monads that are depth- 1 in an abstract categorical sense [ 32 ] , a key prerequisite for most technical results in graded semantics (e.g. [ 32 , 9 , 13 , 15 ] ). As our main result, we then present a graded algebraic theory that captures the local freshness semantics of RNNAs. Related work We have already mentioned previous work on graded semantics [ 32 , 9 , 12 , 13 , 14 , 15 ] and nominal algebra [ 21 ] . We note that alternative systems of varying expressiveness for universal algebra over nominal sets have been proposed [ 6 , 30 ] ; one of them has been shown to correspond to a subclass of (finitary) monads on nominal sets, the so-called fb-monads [ 31 ] . The global freshness semantics of RNNAs has been modelled coalgebraically using categorical distributive laws (in what has been termed Eilenberg-Moore-type [ 1 ] and Kleisli-type [ 24 ] coalgebraic trace semantics), which by general results [ 32 ] entails a modelling as a graded semantics, without however providing a syntactic algebraic presentation [ 17 ] . Categorical distributive laws have also been used to obtain up-to techniques for proving language equivalence of NOFAs [ 5 ] . We mostly restrict the presentation to a variant of RNNAs with all states final; these structures are particular nominal transition systems [ 35 ] . Fresh labelled transition systems [ 3 ] combine global and local freshness in one system, in a similar way as in fresh register automata [ 42 ] . 2 Preliminaries We assume basic familiarity with category theory (e.g. [