Strathprints logo
Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

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.

Full text not available in this repository. (Request a copy from the Strathclyde author)

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
Related URLs:
    Depositing user: Pure Administrator
    Date Deposited: 13 Oct 2011 20:20
    Last modified: 05 Sep 2014 12:06
    URI: http://strathprints.strath.ac.uk/id/eprint/34552

    Actions (login required)

    View Item