The complexity of weakly recognizing morphisms
The complexity of weakly recognizing morphisms
复制标题
弱识别态射的复杂性
DOI：
10.1051/ita/2018006
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
M. Kufleitner
中科院分区：
文献类型：
--
作者：
L. Fleischer;M. Kufleitner
从自由半群到有限半群的弱识别态射是定义ω-正则语言类的一种经典方法，即一组无限词被这样的态射弱识别当且仅当它被某个Büchi自动机所接受。我们研究了弱识别态射的各种结构的描述复杂性和各种决策问题的计算复杂性。我们考虑的结构是从Büchi自动机到Büchi自动机的转换，到强可识别态射的转换，以及互补。我们还证明了固定隶属度问题是nc1-完全的，一般隶属度问题是在L中的，包含、等价和普适性问题是nl-完全的。如果输入为非满射态射，则空性问题被证明是NL-完全的。
Weakly recognizing morphisms from free semigroups onto finite semigroups are a classical way for defining the class ofω-regular languages, i.e., a set of infinite words is weakly recognizable by such a morphism if and only if it is accepted by some Büchi automaton. We study the descriptional complexity of various constructions and the computational complexity of various decision problems for weakly recognizing morphisms. The constructions we consider are the conversion from and to Büchi automata, the conversion into strongly recognizing morphisms, as well as complementation. We also show that the fixed membership problem is NC1-complete, the general membership problem is in L and that the inclusion, equivalence and universality problems are NL-complete. The emptiness problem is shown to be NL-complete if the input is given as a non-surjective morphism.
登录
查看更多内容
关于布尔矩阵半群生成元的 Devadze 定理的证明
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
J. Konieczny
通讯作者：
J. Konieczny
布尔公式值问题在ALOGTIME中
DOI：
10.1145/28395.28409
发表时间：
1987
期刊：
Proceedings of the nineteenth annual ACM symposium on Theory of computing
影响因子：
--
作者：
S. Buss
通讯作者：
S. Buss
不确定性日志空间的新问题已完成
DOI：
--
发表时间：
1976
期刊：
Mathematical Systems Theory
影响因子：
--
作者：
Neil D. Jones;Y. Edmund Lien;William T. Laaser
通讯作者：
William T. Laaser
DOI：
--
发表时间：
1978
期刊：
影响因子：
--
作者：
Ki Hang Kim;F. Roush
通讯作者：
F. Roush