Nominal monoids
The author develops an algebraic theory for languages of data words, i.e. words over an alphabet \(\Sigma\times \mathbb{D}\) where \(\Sigma\) is a finite set of labels and \(\mathbb{D}\) is an infinite set of data values. Some of the key notions of the paper are defined relative to a given data symmetry \((\mathbb{D},G)\) in which \(G\) is a subgroup of the symmetric group on \(\mathbb{D}\). Syntactic monoids of data word languages and data word logics have quite natural definitions. However, since data alphabets are infinite, the syntactic monoids are almost always infinite, and therefore the author employs the notions of nominality and orbit-finiteness that are extensively discussed and illustrated by examples. The main result of the paper is a partial counterpart to a classical theorem that characterizes the first-order definable languages by their syntactic monoids. It states that the syntactic monoid of any first-order definable data word language is aperiodic, and that for a nominal language also the converse implication holds if the syntactic monoid is orbit-finite and has a well-founded \(\mathcal{J}\)-order.
- A new approach to abstract syntax with variable binding
- An algebraic approach to data languages and timed languages
- An algebraic characterization of deterministic regular languages over infinite alphabets.
- Automata and Logics for Words and Trees over an Infinite Alphabet
- Automata vs. Logics on Data Words
- Data monoids
- Finite-memory automata
- scientific article; zbMATH DE number 52907 (Why is no real title available?)
- scientific article; zbMATH DE number 618821 (Why is no real title available?)
- Towards nominal computation
- Simple and subdirectly irreducible finitely supported \(Cb\)-sets
- Free functor from the category of G-nominal sets to that of 01-G-nominal sets
- Logical theory of the monoid of languages over a non tally alphabet
- On the use of guards for logics with data
- Data monoids
- Toward model theory with data values
- Logics with rigidly guarded data tests
- Recognisable languages over monads
- A Kleene theorem for nominal automata
- scientific article; zbMATH DE number 7561623 (Why is no real title available?)
- From equational specifications of algebras with structure to varieties of data languages (invited paper)
- Single-use automata and transducers for infinite alphabets
- Function spaces for orbit-finite sets
- Recognizing number
This page was built for publication: Nominal monoids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q372971)
