closed under the operation of concatenation. By treating as an algebraic monoid under concatenation we see that the monoid structure transfers onto the quotient , resulting in the syntactic monoid of the Dyck language. The class will be denoted . The syntactic monoid of the Dyck language is not commutative: if and then . With the notation above, but neither nor are invertible in . The syntactic monoid of the Dyck language is isomorphic to the bicyclic semigroup by virtue of the properties of and described above. By the Chomsky–Schützenberger representation theorem, any context-free language is a homomorphic image of the intersection of some regular language with a Dyck language on one or more kinds of bracket pairs. The Dyck language with two distinct types of brackets can be recognized in the complexity class . The number of distinct Dyck words with exactly pairs of parentheses and innermost pairs (viz. the substring ) is the Narayana number . The number of distinct Dyck words with exactly pairs of parentheses is the -th Catalan number . Notice that the Dyck language of words with parentheses pairs is equal to the union, over all possible , of the Dyck languages of words of parentheses pairs with innermost pairs, as defined in the previous point. Since can range from 0 to , we obtain the following equality, which indeed holds: Examples We can define an equivalence relation on the Dyck language . For we have if and only if , i.e. and have the same length. This relation partitions the Dyck language: . We have where . Note that is empty for odd . Having introduced the Dyck words of length , we can introduce a relationship on them. For every we define a relation on ; for we have if and only if can be reached from by a series of proper swaps. A proper swap in a word swaps an occurrence of '][' with '[]'. For each the relation makes into a partially ordered set. The relation is reflexive because an empty sequence of proper swaps takes to . Transitivity follows because we can extend a sequence of proper swaps that takes to by concatenating it with a sequence of proper swaps that takes to forming a sequence that takes into . To see that is also antisymmetric we introduce an auxiliary function defined as a sum over all prefixes of