## 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 Perkinsmonoid **B½.** Let *( f ***B½ ***n ) *denote the free spectrum of **B½**, let *an *be the number of distinct alternation word digraphs on words whose alphabet is contained in {*x*1*, . . . , xn*}, and let *pn *denote the number of distinct labeled posets on {1*, . . . , n*}. The word problem for the Perkins semigroup **B½ **is solved here in terms of alternation word digraphs: Roughly speaking, two words *u *and *v *are equivalent over **B½ **if and only if certain alternation graphs associated with *u *and *v *are equal. This solution provides the main application, the bounds: *pn *≤ *an *≤ *f ***B½ ***n *≤ 2*na*2 2*n*. A result of the second author in a companion paper states that *(*log *an) *∈ *O(n*3*)*, from which it follows that *(*log *f ***B½ ***n ) *∈ *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.

Original language | English |
---|---|

Pages (from-to) | 177-194 |

Number of pages | 18 |

Journal | Order |

Volume | 25 |

Issue number | 3 |

Early online date | 30 Aug 2008 |

DOIs | |

Publication status | Published - Aug 2008 |

## Keywords

- directed acyclic graph
- partially order set
- poset
- Perkins semigroup
- free semigroup
- word problem
- computational complexity