Abstract
We present examples where theorems on complexity of computation are proved using methods in algorithmic information theory. The first example is a non-effective construction of a language for which the size of any deterministic finite automaton exceeds the size of a probabilistic finite automaton with a bounded error exponentially. The second example refers to frequency computation. Frequency computation was introduced by Rose and McNaughton in early sixties and developed by Trakhtenbrot, Kinber, Degtev, Wechsung, Hinrichs and others. A transducer is a finite-state automaton with an input and an output. We consider the possibilities of probabilistic and frequency transducers and prove several theorems establishing an infinite hierarchy of relations. We consider only relations where for each input value there is exactly one allowed output value. Relations computable by weak finite-state transducers with frequency \(\frac{km}{kn} \) but not with frequency \(\frac{m}{n} \) are presented in a non-constructive way using methods of algorithmic information theory.
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. In: Wiedermann, J., Gruska, J., Rovan, B. (eds.) MFCS 1986. LNCS, vol. 233, pp. 1–14. Springer, Heidelberg (1986)
Austinat, H., Diekert, V., Hertrampf, U., Petersen, H.: Regular frequency computations. Theoretical Computer Science 330(1), 15–20 (2005)
Beigel, R., Gasarch, W.I., Kinber, E.B.: Frequency computation and bounded queries. Theoretical Computer Science 163(1/2), 177–192 (1996)
Case, J., Kaufmann, S., Kinber, E.B., Kummer, M.: Learning recursive functions from approximations. Journal of Computer and System Sciences 55(1), 183–196 (1997)
Degtev, A.N.: On (m,n)-computable sets. In: Moldavanskij, I., Gos, I. (eds.) Algebraic Systems, pp. 88–99. Universitet (1981)
Freivalds, R., Karpinski, M.: Lower Space Bounds for Randomized Computation. In: Shamir, E., Abiteboul, S. (eds.) ICALP 1994. LNCS, vol. 820, pp. 580–592. Springer, Heidelberg (1994)
Freivalds, R., Karpinski, M.: Lower Time Bounds for Randomized Computation. In: Fülöp, Z. (ed.) ICALP 1995. LNCS, vol. 944, pp. 183–195. Springer, Heidelberg (1995)
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.: Models of computation, Riemann Hypothesis and classical mathematics. In: Rovan, B. (ed.) SOFSEM 1998. LNCS, vol. 1521, pp. 89–106. Springer, Heidelberg (1998)
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. Theoretical Computer Science 411(38-39), 3436–3443 (2010)
Freivalds, R., Zeugmann, T., Pogosyan, G.R.: On the Size Complexity of Deterministic Frequency Automata. In: Dediu, A.-H., Martín-Vide, C., Truthe, B. (eds.) LATA 2013. LNCS, vol. 7810, pp. 287–298. Springer, Heidelberg (2013)
Garret, P.: The Mathematics of Coding Theory. Pearson Prentice Hall, Upper Saddle River (2004)
Gurari, E.: An Introduction to the Theory of Computation, ch. 2.2. Computer Science Press, an imprint of E. H. Freeman (1989)
Harizanova, V., Kummer, M., Owings, J.: Frequency computations and the cardinality theorem. The Journal of Symbolic Logic 57(2), 682–687 (1992)
Hinrichs, M., Wechsung, G.: Time bounded frequency computations. Information and Computation 139, 234–257 (1997)
Kaņeps, J., Freivalds, R.: Minimal Nontrivial Space Complexity of Probabilistic One-Way Turing Machines. In: Rovan, B. (ed.) MFCS 1990. LNCS, vol. 452, pp. 355–361. Springer, Heidelberg (1990)
Kinber, E.B.: Frequency calculations of general recursive predicates and frequency enumeration of sets. Soviet Mathematics Doklady 13, 873–876 (1972)
Kinber, E.B.: Frequency computations in finite automata. Kibernetika (2), 7–15 (1976), Russian; English translation in Cybernetics 12, 179–187 (1976)
Kinber, E.B., Gasarch, W.I., Zeugmann, T., Pleszkoch, M.G., Smith, C.H.: Learning Via Queries With Teams and Anomalies. In: Proceedings of COLT 1990, pp. 327–337 (1990)
Kolmogorov, A.N.: Three approaches to the quantitative definition of information. Problems in Information Transmission 1, 1–7 (1965)
McNaughton, R.: The Theory of Automata, a Survey. Advances in Computers 2, 379–421 (1961)
Rabin, M.O.: Probabilistic automata. Information and Control 6(3), 230–245 (1963)
Michael, O.: Rabin and Dana Scott. Finite automata and their decision problems. IBM Journal of Research and Development 3(2), 115–125 (1959)
Rose, G.F.: An extended notion of computability. In: Abstracts of International Congress for Logic, Methodology and Philosophy of Science, p. 14 (1960)
Solomonoff, R.: A Formal Theory of Inductive Inference, Part II. Information and Control 7(2), 224–254 (1964)
Trakhtenbrot, B.A.: On the frequency computation of functions. Algebra i Logika 2, 25–32 (1964) (Russian)
Trakhtenbrot, B.A.: Frequency Algorithms and Computations. In: Becvar, J. (ed.) MFCS 1975. LNCS, vol. 32, pp. 148–161. Springer, Heidelberg (1975)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Freivalds, R. (2013). Algorithmic Information Theory and Computational Complexity. In: Dowe, D.L. (eds) Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence. Lecture Notes in Computer Science, vol 7070. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-44958-1_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-44958-1_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-44957-4
Online ISBN: 978-3-642-44958-1
eBook Packages: Computer ScienceComputer Science (R0)