Nominal monoids (Q372971)

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.