### 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 |

### Fingerprint

### Keywords

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

### Cite this

*Order*,

*25*(3), 177-194. https://doi.org/10.1007/s11083-008-9083-7

}

*Order*, vol. 25, no. 3, pp. 177-194. https://doi.org/10.1007/s11083-008-9083-7

**Word problem of the Perkins semigroup via directed acyclic graphs.** / Kitaev, Sergey; Seif, Steven.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Word problem of the Perkins semigroup via directed acyclic graphs

AU - Kitaev, Sergey

AU - Seif, Steven

PY - 2008/8

Y1 - 2008/8

N2 - 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.

AB - 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.

KW - directed acyclic graph

KW - partially order set

KW - poset

KW - Perkins semigroup

KW - free semigroup

KW - word problem

KW - computational complexity

U2 - 10.1007/s11083-008-9083-7

DO - 10.1007/s11083-008-9083-7

M3 - Article

VL - 25

SP - 177

EP - 194

JO - Order

JF - Order

SN - 0167-8094

IS - 3

ER -