Проблемы передачи информации
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Пробл. передачи информ.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Проблемы передачи информации, 1979, том 15, выпуск 3, страницы 99–106 (Mi ppi1504)  
Теория языков

Распознавание языков на конечных вероятностных многоленточных и многоголовочных автоматах

Р. В. Фрейвалд
PDF полного текста (1378 kB)
Аннотация: М. О. Рабин [1] доказал, что на конечных вероятностных автоматах с изолированной точкой сечения можно распознавать только те языки, которые распознаваемы на конечных детерминированных автоматах. В настоящей работе для конечных автоматов со многими лентами или со многими головками на одной ленте доказан противоположный результат: существует язык, распознаваемый с вероятностью $1-\varepsilon$ для любого $\varepsilon>0$, но не распознаваемый детерминированно.
Поступила в редакцию: 03.11.1977
Реферативные базы данных:
Тип публикации: Статья
УДК: 621.391.19:62-507
Образец цитирования: Р. В. Фрейвалд, “Распознавание языков на конечных вероятностных многоленточных и многоголовочных автоматах”, Пробл. передачи информ., 15:3 (1979), 99–106; Problems Inform. Transmission, 15:3 (1979), 235–241
Цитирование в формате AMSBIB
\RBibitem{Fre79}
\by Р.~В.~Фрейвалд
\paper Распознавание языков на конечных вероятностных многоленточных и многоголовочных автоматах
\jour Пробл. передачи информ.
\yr 1979
\vol 15
\issue 3
\pages 99--106
\mathnet{http://mi.mathnet.ru/ppi1504}
\mathscinet{https://mathscinet.ams.org/mathscinet-getitem?mr=572723}
\zmath{https://zbmath.org/?q=an:0449.68040|0433.68063}
\transl
\jour Problems Inform. Transmission
\yr 1979
\vol 15
\issue 3
\pages 235--241
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/ppi1504
  • https://www.mathnet.ru/rus/ppi/v15/i3/p99
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Проблемы передачи информации Problems of Information Transmission
    Статистика просмотров:
    Страница аннотации:296
    PDF полного текста:143
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2026