Abstract
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.
The research was supported by Grant No. 09.1570 from the Latvian Council of Science and by Project 2009/0216/1DP/1.1.2.1.2/09/IPIA/VIA/004 from the European Social Fund.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ablayev, F.M., Freivalds, R.: Why Sometimes Probabilistic Algorithms Can Be More Effective. LNCS, vol. 233, pp. 1–14. Springer, Heidelberg (1986)
Alon, N., Spencer, J.H.: The Probabilistic Method. John Wiley & Sons, Chichester (2000)
Bach, E., Shallit, J.: Algorithmic Number Theory, vol. 1. MIT Press, Cambridge (1996)
Bārzdiņš, J. (Barzdin, J.M.): On a Class of Turing Machines (Minsky Machines). Algebra i Logika 3(1) (1963) (Russian); Review in The Journal of Symbolic Logic 32(4), 523–524 (1967)
Damm, C., Holzer, M.: Automata that take advice. In: Hájek, P., Wiedermann, J. (eds.) MFCS 1995. LNCS, vol. 969, pp. 565–613. Springer, Heidelberg (1995)
Dwork, C., Stockmeyer, L.: Finite state verifiers I: the power of interaction. Journal of the Association for Computing Machinery 39(4), 800–828 (1992)
Erdös, P.: Some remarks on the theory of graphs. Bulletin of the American Mathematical Society 53(4), 292–294 (1947)
Fagin, R.: Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. In: Karp, R. (ed.) SIAM-AMS Proceedings of Complexity of Computation, vol. 7, pp. 27–41 (1974)
Freivalds, R. (Freivald, R.V.): Recognition of languages with high probability on different classes of automata. Dolady Akademii Nauk SSSR 239(1), 60–62 (1978) (Russian)
Freivalds, R.: Projections of Languages Recognizable by Probabilistic and Alternating Finite Multitape Automata. Information Processing Letters 13(4/5), 195–198 (1981)
Freivalds, R.: Complexity of Probabilistic Versus Deterministic Automata. In: Barzdins, J., Bjorner, D. (eds.) Baltic Computer Science. LNCS, vol. 502, pp. 565–613. Springer, Heidelberg (1991)
Freivalds, R.: Non-Constructive Methods for Finite Probabilistic Automata. International Journal of Foundations of Computer Science 19(3), 565–580 (2008)
Freivalds, R.: Amount of nonconstructivity in finite automata. In: Maneth, S. (ed.) CIAA 2009. LNCS, vol. 5642, pp. 227–236. Springer, Heidelberg (2009)
Freivalds, R.: Multiple usage of random bits by finite automata. Unpublished manuscript (2010)
Hilbert, D.: Uber die Theorie der algebraischen Formen. Mathematische Annalen 36, 473–534 (1890)
Karp, R.M., Lipton, R.: Turing machines that take advice. L’ Enseignement Mathematique 28, 191–209 (1982)
Kolmogorov, A.N.: Three approaches to the quantitative definition of information. Problems in Information Transmission 1, 1–7 (1965)
Levin, L.A.: On the notion of a random sequence. Soviet Mathematics Doklady 14, 1413–1416 (1973)
Martin-Löf, P.: The definition of random sequences. Information and Control 9(6), 602–619 (1966)
Li, M., Vitányi, P.M.B.: An Introduction to Kolmogorov Complexity and its Applications, 2nd edn. Springer, Heidelberg (1997)
Nishimura, H., Yamakami, T.: Polynomial time quantum computation with advice. Information Processing Letters 90(4), 195–204 (2004)
Schnorr, C.-P.: A unified approach to the definition of random sequences. Mathematical Systems Theory 5(3), 246–258 (1971)
Schnorr, C.-P.: Process Complexity and Effective Random Tests. Journal of Computer and System Sciences 7(4), 376–388 (1973)
Spencer, J.: Nonconstructive methods in discrete mathematics. In: Rota, G.-C. (ed.) Studies in Mathematics, MAA, vol. 17, pp. 142–178 (1978)
Stearns, R.E., Hartmanis, J., Lewis II, P.M.: Hierarchies of memory limited computations. In: Proceedings of FOCS, pp. 179–190 (1965)
Tadaki, K., Yamakami, T., Lin, J.C.H.: Theory of One Tape Linear Time Turing Machines. In: Van Emde Boas, P., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2004. LNCS, vol. 2932, pp. 335–348. Springer, Heidelberg (2004)
Yamakami, T.: Swapping lemmas for regular and context-free languages with advice. The Computing Research Repository (CoRR), CoRR abs/0808.4122 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Agadzanyan, R., Freivalds, R. (2010). Finite State Transducers with Intuition. In: Calude, C.S., Hagiya, M., Morita, K., Rozenberg, G., Timmis, J. (eds) Unconventional Computation. UC 2010. Lecture Notes in Computer Science, vol 6079. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13523-1_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-13523-1_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13522-4
Online ISBN: 978-3-642-13523-1
eBook Packages: Computer ScienceComputer Science (R0)