6533b82cfe1ef96bd128eb3d

RESEARCH PRODUCT

Amount of nonconstructivity in deterministic finite automata

Rsi Freivalds

subject

General Computer ScienceKolmogorov complexityKolmogorov complexityMathematical proofConstructiveTheoretical Computer ScienceAlgebraDeterministic finite automatonProbabilistic methodIntuitionismDeterministic automatonNonconstructive methodsCalculusFinite automataMethod of conditional probabilitiesMathematicsComputer Science(all)

description

AbstractWhen 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. The author (Freivalds, 2008) [10] 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.

yearjournalcountryeditionlanguage
2010-08-01Theoretical Computer Science
10.1016/j.tcs.2010.05.038http://dx.doi.org/10.1016/j.tcs.2010.05.038