Word problem of the Perkins semigroup via directed acyclic graphs

Sergey Kitaev, Steven Seif

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)


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 n ) denote the free spectrum of , 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 is solved here in terms of alternation word digraphs: Roughly speaking, two words u and v are equivalent over 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 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 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.

Original languageEnglish
Pages (from-to)177-194
Number of pages18
Issue number3
Early online date30 Aug 2008
Publication statusPublished - Aug 2008


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


Dive into the research topics of 'Word problem of the Perkins semigroup via directed acyclic graphs'. Together they form a unique fingerprint.

Cite this