|
Problemy Peredachi Informatsii, 1979, Volume 15, Issue 4, Pages 96–101
(Mi ppi1515)
|
|
|
|
Theory of Languages
Language Recognition Using Probabilistic Turing Machines in Real Time, and Automata with a Push-Down Store
R. V. Freivald
Abstract:
For each of the two classes of machines, the following result is obtained: There exists a language that can be recognized with probability $1-\varepsilon$ for any $\varepsilon>0$, but which cannot be recognized. deterministically.
Received: 03.11.1977
Citation:
R. V. Freivald, “Language Recognition Using Probabilistic Turing Machines in Real Time, and Automata with a Push-Down Store”, Probl. Peredachi Inf., 15:4 (1979), 96–101; Problems Inform. Transmission, 15:4 (1979), 319–323
Linking options:
https://www.mathnet.ru/eng/ppi1515 https://www.mathnet.ru/eng/ppi/v15/i4/p96
|
Statistics & downloads: |
Abstract page: | 270 | Full-text PDF : | 141 |
|