Word Problem of the Perkins Semigroup via Directed Acyclic Graphs
Word Problem of the Perkins Semigroup via Directed Acyclic Graphs
复制标题
基于有向无环图的珀金斯半群文字问题
作者：
S. Kitaev;S. Seif
对于字母表Γ中的一个词，给出了一个与w相关联的有向无圈图交替词有向图Alt（w），作为分析Perkins幺半群自由谱的一种手段.设为自由谱，设为字母表包含在{x1，...，xn}，并且letpn表示{1，.，n}。Perkins半群的字问题在这里用交替字有向图来解决：粗略地说，两个字suandv在上等价当且仅当与uandv相关联的某些交替图相等。此解决方案提供了主要应用程序，即边界：。第二作者在一篇配套论文中的一个结果指出，由此也可以得出。交替词有向图在组合上具有独立的意义。这里示出了具有作为实例{u，v}的计算复杂性问题，其中u，v是有限长度的字，并且问题“IsAlt（u）=Alt（v）？"，是co-NP-complete。此外，交替词有向图是非循环的，并且其中某些是偏序集的自然扩张;有限偏序集的每个实现子通过交替词有向图确定扩张。
For a wordwin an alphabet Γ, the alternation word digraphAlt(w), a certain directed acyclic graph associated withw, is presented as a means to analyze the free spectrum of the Perkins monoid. Letdenote the free spectrum of, letanbe the number of distinct alternation word digraphs on words whose alphabet is contained in {x1,...,xn}, and letpndenote the number of distinct labeled posets on {1,...,n}. The word problem for the Perkins semigroupis solved here in terms of alternation word digraphs: Roughly speaking, two wordsuandvare equivalent overif and only if certain alternation graphs associated withuandvare equal. This solution provides the main application, the bounds:. A result of the second author in a companion paper states that, from which it follows thatas well. Alternation word digraphs are of independent interest combinatorially. It is shown here that the computational complexity problem that has as instance {u,v} whereu,vare words of finite length, and question “IsAlt(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.