6533b85ffe1ef96bd12c1942

RESEARCH PRODUCT

Finite State Transducers with Intuition

Ruben AgadzanyanRūsiņš Freivalds

subject

Discrete mathematicsTheoretical computer scienceNested wordKolmogorov complexityComputer scienceComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Nondeterministic algorithmTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonKolmogorov structure functionProbabilistic automatonQuantum finite automataNondeterministic finite automatonComputer Science::Formal Languages and Automata Theory

description

Finite automata that take advice have been studied from the point of view of what is the amount of advice needed to recognize nonregular languages. It turns out that there can be at least two different types of advice. In this paper we concentrate on cases when the given advice contains zero information about the input word and the language to be recognized. Nonetheless some nonregular languages can be recognized in this way. The help-word is merely a sufficiently long word with nearly maximum Kolmogorov complexity. Moreover, any sufficiently long word with nearly maximum Kolmogorov complexity can serve as a help-word. Finite automata with such help can recognize languages not recognizable by nondeterministic nor probabilistic automata. We hope that mechanisms like the one considered in this paper may be useful to construct a mathematical model for human intuition.

yearjournalcountryeditionlanguage
2010-01-01
https://doi.org/10.1007/978-3-642-13523-1_5