The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy
The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy
复制标题
Trotter-Weil 层级上的 Omega 项的文字问题
DOI：
10.1007/s00224-017-9763-z
复制
发表时间：
2018
影响因子：
0.5
通讯作者：
J. P. Wächter
中科院分区：
文献类型：
--
作者：
M. Kufleitner;J. P. Wächter
对于两个给定的ω-项α和β，V上的ω-项的字问题是问V中的所有么半群是否α=β。我们证明了Trotter-Weil层次的每一层上的ω-项的字问题是可判定的。更确切地说，对于Trotter-Weil层次中的每个固定品种，我们的方法在非确定性对数空间（NL）中产生一个算法。此外，我们提供了确定性的多项式时间算法，这是更有效的比直接翻译的NL算法。作为我们结果的一个应用，我们证明了Trotter-Weil族的所谓角的可分性由ω-项证明（该性质也称为ω-约化）。特别地，Trotter-Weil层次的角的分离问题是可判定的。
For two givenω-termsαandβ, the word problem forω-terms over a varietyVasks whetherα=βin all monoids inV. We show that the word problem forω-terms over each level of the Trotter-Weil Hierarchy is decidable. More precisely, for every fixed variety in the Trotter-Weil Hierarchy, our approach yields an algorithm in nondeterministic logarithmic space (NL). In addition, we provide deterministic polynomial time algorithms which are more efficient than straightforward translations of the NL-algorithms. As an application of our results, we show that separability by the so-called corners of the Trotter-Weil Hierarchy is witnessed byω-terms (this property is also known asω-reducibility). In particular, the separation problem for the corners of the Trotter-Weil Hierarchy is decidable.
登录
查看更多内容
影响因子：
0.6
作者：
Ghani N
通讯作者：
Ghani N
无计数器自动机（麻省理工学院研究专着第 65 号）
影响因子：
0.7
作者：
R. McNaughton;S. Papert
通讯作者：
S. Papert
DOI：
--
发表时间：
1997
期刊：
影响因子：
--
作者：
P. G. Trotter;Pascal Weil
通讯作者：
Pascal Weil
论激进同余系统
DOI：
--
发表时间：
1999
期刊：
影响因子：
--
作者：
T. Hall;P. Weil
通讯作者：
P. Weil
欧米茄条款上的 Ehrenfeucht-Fraisse Games
DOI：
--
发表时间：
2013
期刊：
Symposium on Theoretical Aspects of Computer Science
影响因子：
--
作者：
Martin Huschenbett;Manfred Kufleitner
通讯作者：
Manfred Kufleitner