Amount of Nonconstructivity in Finite Automata
Amount of Nonconstructivity in Finite Automata
复制标题
有限自动机中的非构造性量
DOI：
10.1007/978-3-642-02979-0_26
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
R. Freivalds
中科院分区：
文献类型：
--
作者：
R. Freivalds
When D. Hilbert used nonconstructive methods in his famous paper on invariants (1888), P.Gordan tried to prevent the publication of this paper considering these methods as non-mathematical. L. E. J. Brouwer in the early twentieth century initiated intuitionist movement in mathematics. His slogan was ”nonconstructive arguments have no value for mathematics”. However, P. Erdös got many exciting results in discrete mathematics by nonconstructive methods. It is widely believed that these results either cannot be proved by constructive methods or the proofs would have been prohibitively complicated. R.Freivalds [7] showed that nonconstructive methods in coding theory are related to the notion of Kolmogorov complexity.We study the problem of the quantitative characterization of the amount of nonconstructiveness in nonconstructive arguments. We limit ourselves to computation by deterministic finite automata. The notion of nonconstructive computation by finite automata is introduced. Upper and lower bounds of nonconstructivity are proved.
DOI：
10.1016/j.tcs.2009.08.031
发表时间：
2003-10
期刊：
ArXiv
影响因子：
--
作者：
K. Tadaki;T. Yamakami;Jack C. H. Lin
通讯作者：
K. Tadaki;T. Yamakami;Jack C. H. Lin