: The following table illustrates that is strictly monotonic with respect to proper swaps. Hence so when there is a proper swap that takes into . Now if we assume that both and , then there are non-empty sequences of proper swaps such is taken into and vice versa. But then which is nonsensical. Therefore, whenever both and are in , we have , hence is antisymmetric. The partial ordered set is shown in the illustration accompanying the introduction if we interpret a [ as going up and ] as going down. Generalizations There exist variants of the Dyck language with multiple delimiters, e.g., D2 on the alphabet "(", ")", "[", and "]". The words of such a language are the ones which are well-parenthesized for all delimiters, i.e., one can read the word from left to right, push every opening delimiter on the stack, and whenever we reach a closing delimiter then we must be able to pop the matching opening delimiter from the top of the stack. (The counting algorithm above does not generalise). See also Dyck congruence Lattice word Notes References A proof of the Chomsky Schützenberger theorem An AMS blog entry on Dyck words Formal languages