# Word problem of the Perkins semigroup via directed acyclic graphs

Kitaev, Sergey and Seif, Steven
(2008)
*Word problem of the Perkins semigroup via directed acyclic graphs.*
Order, 25 (3).
pp. 177-194.

## 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 {x1, . . . , 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 ≤ 2na2 2n. A result of the second author in a companion paper states that (log an) ∈ O(n3), from which it follows that (log f B½ n ) ∈ O(n3) 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.

Item type: | Article |
---|---|

ID code: | 34552 |

Keywords: | directed acyclic graph, partially order set, poset, Perkins semigroup, free semigroup, word problem, computational complexity, Probabilities. Mathematical statistics, Computational Theory and Mathematics, Algebra and Number Theory, Geometry and Topology |

Subjects: | Science > Mathematics > Probabilities. Mathematical statistics |

Department: | Faculty of Science > Computer and Information Sciences |

Depositing user: | Pure Administrator |

Date Deposited: | 13 Oct 2011 19:20 |

Last modified: | 04 May 2016 20:10 |

URI: | http://strathprints.strath.ac.uk/id/eprint/34552 |