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

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

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



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






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


ПДМ, 2010, номер 2(8), страницы 104–116 (Mi pdm169)  

Прикладная теория автоматов

О построении минимальных детерминированных конечных автоматов, распознающих префиксный код заданной мощности

И. Р. Акишев, М. Э. Дворкин

Санкт-Петербургский государственный университет информационных технологий, механики и оптики, г. Санкт-Петербург, Россия

Аннотация: Рассматривается задача о построенни минимального по числу состояний детерминированного конечного автомата, который принимает произвольный префиксный код заданной мощности над алфавитом $\{0,1\}$. Доказывается, что данная задача является эквивалентной задаче о поиске кратчайшей аддитивной цепочки, заканчивающейся числом $n$.

Ключевые слова: префиксный код, детерминированный конечный автомат, автомат Мура, аддитивная цепочка.

Полный текст: PDF файл (754 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.713+519.766

Образец цитирования: И. Р. Акишев, М. Э. Дворкин, “О построении минимальных детерминированных конечных автоматов, распознающих префиксный код заданной мощности”, ПДМ, 2010, № 2(8), 104–116

Цитирование в формате AMSBIB
\RBibitem{AkiDvo10}
\by И.~Р.~Акишев, М.~Э.~Дворкин
\paper О построении минимальных детерминированных конечных автоматов, распознающих префиксный код заданной мощности
\jour ПДМ
\yr 2010
\issue 2(8)
\pages 104--116
\mathnet{http://mi.mathnet.ru/pdm169}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm169
  • http://mi.mathnet.ru/rus/pdm/y2010/i2/p104

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
    Цикл статей
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:474
    Полный текст:105
    Литература:18
    Первая стр.:1

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017