Nominal Monoids
- PDF / 875,240 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 77 Downloads / 200 Views
Nominal Monoids ´ Mikołaj Bojanczyk
Published online: 4 April 2013 © The Author(s) 2013. This article is published with open access at Springerlink.com
Abstract We develop an algebraic theory for languages of data words. We prove that, under certain conditions, a language of data words is definable in first-order logic if and only if its syntactic monoid is aperiodic. Keywords Monoids · Nominal sets · Data words 1 Introduction This paper is an attempt to combine two fields. The first field is the algebraic theory of regular languages. In this theory, a regular language is represented by its syntactic monoid, which is a finite monoid. It turns out that many important properties of the language are reflected in the structure of its syntactic monoid. One particularly beautiful result is the Schützenberger-McNaughtonPapert theorem, which describes the expressive power of first-order logic. A regular language of finite words is definable in first-order logic if and only if its syntactic monoid is aperiodic. For instance, the language “words where there exists a position with label a” is defined by the first-order logic formula (this example does not even use the order on positions J (−3, 3, 0) >J · · · That is why the implication in the theorem fails: the monoid is aperiodic, but the language L is not definable in first-order logic. Example 9 Let A be an infinite but orbit-finite alphabet, e.g. D in the equality symmetry. Consider the set of words where the number of distinct letters is even. The syntactic monoid of this language is the family of finite subsets of A, with union as the monoid operation. The monoid is aperiodic (and therefore a language that talks about parity can have an aperiodic syntactic monoid). However, the monoid is not 4 I would like to thank an anonymous reviewer for pointing this out.
Theory Comput Syst (2013) 53:194–222
217
orbit-finite, because subsets of different sizes are in different orbits. Also, the J order is not well-founded (because the J -order is the superset relation, which is not well-founded).5 Observe that in Example 8 we used the total order symmetry, and not the simpler equality symmetry. Indeed, it is impossible to provide an example that uses the equality symmetry, as shown by the following lemma. Lemma 9.3 In the equality symmetry, the J -order is well-founded in every orbitfinite monoid. Proof Consider an orbit-finite monoid M. Suppose that there is an infinite decreasing chain m1 >J m2 >J m3 >J · · · Let C be a support of M. Because the monoid is orbit-finite, there must be some i < j such that mi is in the same orbit as j , with respect to GC . We will show that mi and mj are in the same J -class, contradicting the assumption on the decreasing chain. Because mj comes later in the chain than mi , there must be elements x, y ∈ M such that mj = xmi y. Because mi and mj are in the same orbit, there must be some π ∈ GC such that mi = mj π . Choose π so that, as a permutations on data values, it is the identity on all but a finite set of data values. This can be done in th
Data Loading...
