Word Problem of the Perkins Semigroup via Directed Acyclic Graphs

Abstract

For a word w in an alphabet Γ, the alternation word digraph Alt(w), a certain directed acyclic graph associated with w, is presented as a means to analyze the free spectrum of the Perkins monoid $\mathbf{B_2^1}$. Let $(f_n^{\mathbf{B_2^1}})$ denote the free spectrum of $\mathbf{B_2^1}$, let a _n be the number of distinct alternation word digraphs on words whose alphabet is contained in {x ₁,..., x _n }, and let p _n denote the number of distinct labeled posets on {1,..., n}. The word problem for the Perkins semigroup $\mathbf{B_2^1}$ is solved here in terms of alternation word digraphs: Roughly speaking, two words u and v are equivalent over $\mathbf{B_2^1}$ if and only if certain alternation graphs associated with u and v are equal. This solution provides the main application, the bounds: $p_n \leq a_n \leq f_n^{\mathbf{B_2^1}} \leq 2^{n}a_{2n}^2$. A result of the second author in a companion paper states that $(\operatorname{log} \; a_n)\in O(n^3)$, from which it follows that $(\operatorname{log} f_n^{\mathbf{B_2^1}})\in O(n^3)$ as well. Alternation word digraphs are of independent interest combinatorially. It is shown here that the computational complexity problem that has as instance {u,v} where u,v are words of finite length, and question “Is Alt(u) = Alt(v)?”, is co-NP-complete. Additionally, alternation word digraphs are acyclic, and certain of them are natural extensions of posets; each realizer of a finite poset determines an extension by an alternation word digraph.