This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
F.M.Ablaev, On the problem of reduction of automata, Izvestija VUZ. Matematika, 1980, No.3, 75–77 (Russian).
F.M.Ablaev, Capabilities of probabilistic machines to represent languages in real time, Izvestija VUZ. Matematika, 1985, No.7, 32–40 (Russian).
J.M. Barzdin, Complexity of recognition of palindromes by Turing machines, Problemy kibernetiki, v.15, Moscow, Nauka, 1965, 245–248 (Russian).
J.M. Barzdin, On computability by probabilistic machines, Doklady AN SSSR, 1969, v.189, No.4, 699–702 (Russian).
R.G. Bukharaev, Foundations of the theory of probabilistic automata, Moscow, Nauka, 1985.
W. Feller, An introduction to probability theory and its applications, v.1, New York et al., John Wiley, 1957.
R. Freivalds, Fast computation by probabilistic Turing machines, Ucenye Zapiski Latvijskogo Gosudarstvennogo Universiteta, 1975, v.233, 201–205 (Russian)
R.Freivalds, Probabilistic machines can use less running time, in: Information Processing '77, IFIP (North Holland, 1977), 839–842.
R. Freivalds, Language recognition with high probability by various classes of automata, Doklady AN SSSR, 1978, v.239, No.1, 60–62 (Russian).
R. Freivalds, Speeding of recognition of languages by usage of random number generators, Problemy kibernetiki, v.36, Moscow, Nauka, 1979, 209–224 (Russian).
R.Freivalds, Finite identification of general recursive functions by probabilistic strategies, Proc. Conference FCT, 1979, 138–145.
R.Freivalds, On principal capabilities of probabilistic algorithms in inductive inference, Semiotika i informatika, 1979, No.12, 137–140 (Russian).
R.Freivalds, A probabilistic reducibility of sets, Proc. USSR Conference on Mathematical Logics, 1979, 137 (Russian).
R. Freivalds, Probabilistic two-way machines, Lecture Notes in Computer Science, Springer, 1981, v.118, 33–45.
R.Freivalds, Capabilities of various models of probabilistic one-way automata, Izvestija VUZ. Matematika, 1981, No.5, 26–34 (Russian).
R. Freivalds, Characterization of capabilities of the simplest method for proving the advantages of probabilistic automata over deterministic ones, Latvijskij matematiceskij ezegodnik, 1983, v.27, 241–251 (Russian).
R. Freivalds, Advantages of probabilistic 3-head finite automata over deterministic multi-head ones, Latvijskij matematiceskij ezegodnik, 1985, v.29, 155–163 (Russian).
A.V. Gladkij, Formal grammars and languages, Moscow, Nauka, 1973.
E.M. Gold, Language identification in the limit, Information and Control, 1967, v.10, 447–474.
K. de Leeuw, E.F.Moore, C.E.Shannon and N.Shapiro, Computability by probabilistic machines, Automata Studies, Princeton University Press, 1956, 183–212.
N.R.Nigmatullin, Towards the problem of reduction of ω-automata, Verojatnostnye metodi i kibernetika, Kazan University Press, 1979, 61–67 (Russian).
L.Pitt, Probabilistic inductive inference, Yale University, YALEU /DCS/ TR-400, June 1985.
M.O. Rabin, Probabilistic automata, Information and Control, 1963, v.6, No.3, 230–245.
H. Rogers Jr., Theory of recursive functions and effective computability, New York, McGraw Hill, 1967.
R.E.Stearns, J.Hartmanis and P.M.Lewis II, Hierarchies of memory limited computation, Proc. IEEE Symposium on Switching Circuit Theory and Logical Design, 1965, 179–190.
P.Turakainen, On probabilistic automata and their generalizations, Suomalais, tiedenkat. toimituks., 1968, v.53.
A.V.Vaiser, Notes on complexity measures in probabilistic computations, in: Control systems, v.1, Tomsk University Press, 1975, 182–196 (Russian).
S.V.Yablonskiy, On lagorithmic difficulties in minimal circuit synthesis, Problemy kibernetiki, v.2, Moscow, Fizmatgiz, 75–121 (Russian).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1986 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ablaev, F.M., Freivalds, R. (1986). Why sometimes probabilistic algorithms can be more effective. In: Gruska, J., Rovan, B., Wiedermann, J. (eds) Mathematical Foundations of Computer Science 1986. MFCS 1986. Lecture Notes in Computer Science, vol 233. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0016230
Download citation
DOI: https://doi.org/10.1007/BFb0016230
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-16783-9
Online ISBN: 978-3-540-39909-4
eBook Packages: Springer Book Archive