• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Order >Word Problem of the Perkins Semigroup via Directed Acyclic Graphs
【24h】

Word Problem of the Perkins Semigroup via Directed Acyclic Graphs

机译：有向无环图的珀金斯半群词问题

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 Perkins monoid B_2~1. Let (f_m~(B_2~1)) denote the free spectrum of B_2~1, let a_n be the number of distinct alternation word digraphs on words whose alphabet is contained in {x_1,..., x_n], and let p_n denote the number of distinct labeled posets on {1,...,n}. The word problem for the Perkins semigroup B_2~1 is solved here in terms of alternation word digraphs: Roughly speaking, two words u and v are equivalent over B_2~1 if and only if certain alternation graphs associated with u and v are equal. This solution provides the main application, the bounds: p_n ≤ a_n ≤ f_~(B_2~1) ≤ 2~n a_(2n)~2. A result of the second author in a companion paper states that (log a_n) ∈ O(n~3), from which it follows that (log f_n~(B_2~1)) ∈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.
机译：对于字母Γ中的单词w，提出了交替单词有向图Alt（w）（一种与w相关的有向无环图），作为分析珀金斯半体B_2〜1的自由光谱的一种手段。令（f_m〜（B_2〜1））表示B_2〜1的自由谱，令a_n是{x_1，...，x_n]中包含字母的单词的不同交替字图的数量，令p_n表示{1，...，n}上不同的带标签的球的数量。帕金斯半群B_2〜1的单词问题在这里用交替词有向图解决：粗略地说，当且仅当与u和v相关的某些交替图相等时，两个词u和v才等于B_2〜1。该解决方案提供了主要应用范围：p_n≤a_n≤f_〜（B_2〜1）≤2〜n a_（2n）〜2。第二位作者在同篇论文中的结果指出（log a_n）∈O（n〜3），从中得出（log f_n〜（B_2〜1））∈O（n〜3）。组合词有向图在组合上具有独立的重要性。这里显示了具有例如{u，v}的计算复杂性问题，其中u，v是有限长度的单词，以及问题“ Alt（u）= Alt（v）？”是完整的NP。另外，交替词有向图是非循环的，其中某些是位姿的自然扩展。有限位姿的每个实现者都通过交替词有向图来确定扩展。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号