Counting nondeterministic computations
Counting nondeterministic computations
复制标题
计算不确定性计算
DOI：
10.1016/j.tcs.2021.08.022
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Yuxi Fu
中科院分区：
文献类型：
--
作者：
Qizhe Yang;Yuxi Fu
The structure of nondeterministic computations is extremely complicated. C-graphs are abstract representations of the branching structure of nondeterministic computations. The paper investigates the structure of finite state nondeterministic computations by showing that the complexity of the structure increases non-elementarily while the number of computation steps increases. This is achieved by establishing a recursive equation relating the number of C-graphs of a certain height to the number of C-graphs of smaller height.
登录
查看更多内容
DOI：
10.1016/j.tcs.2015.07.043
发表时间：
2016-01
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Yuxi Fu
通讯作者：
Yuxi Fu
DOI：
10.1109/mahc.1981.10004
发表时间：
1981
期刊：
Annals of the History of Computing
影响因子：
--
作者：
S. Kleene
通讯作者：
S. Kleene
DOI：
10.23638/lmcs-16(3:14)2020
发表时间：
2018-01
期刊：
ArXiv
影响因子：
--
作者：
R. V. Glabbeek;B. Luttik;L. Spaninks
通讯作者：
R. V. Glabbeek;B. Luttik;L. Spaninks
DOI：
--
发表时间：
1990
期刊：
--
影响因子：
--
作者：
P. E. Boas
通讯作者：
P. E. Boas
DOI：
10.1016/j.ic.2008.05.001
发表时间：
2008-08
期刊：
Inf. Comput.
影响因子：
--
作者：
D. Gorla
通讯作者：
D. Gorla