Word problem of the Perkins semigroup via directed acyclic graphs

Sergey Kitaev, Steven Seif

Research output: Contribution to journalArticle

18 Citations (Scopus)

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

LanguageEnglish
Pages177-194
Number of pages18
JournalOrder
Volume25
Issue number3
Early online date30 Aug 2008
DOIs
Publication statusPublished - Aug 2008

Fingerprint

Word problem
Alternation
Directed Acyclic Graph
Computational complexity
Digraph
Semigroup
Poset
Denote
Distinct
Natural Extension
Computational Complexity
NP-complete problem
If and only if
Graph in graph theory

Keywords

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

Cite this

Kitaev, Sergey ; Seif, Steven. / Word problem of the Perkins semigroup via directed acyclic graphs. In: Order. 2008 ; Vol. 25, No. 3. pp. 177-194.
@article{e4f7c906ec034611a8df11cd8989272c,
title = "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 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.",
keywords = "directed acyclic graph, partially order set, poset, Perkins semigroup, free semigroup, word problem, computational complexity",
author = "Sergey Kitaev and Steven Seif",
year = "2008",
month = "8",
doi = "10.1007/s11083-008-9083-7",
language = "English",
volume = "25",
pages = "177--194",
journal = "Order",
issn = "0167-8094",
number = "3",

}

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

In: Order, Vol. 25, No. 3, 08.2008, p. 177-194.

Research output: Contribution to journalArticle

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

T2 - Order

JF - Order

SN - 0167-8094

IS - 3

ER -