|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
О проблеме проверки однозначности алфавитного декодирования в классе регулярных языков с полиномиальной функцией ростастатья
- Автор: Дергач П.С.
- Журнал: Интеллектуальные системы. Теория и приложения (ранее: Интеллектуальные системы по 2014, № 2, ISSN 2075-9460)
- Том: 20
- Номер: 2
- Год издания: 2016
- Издательство: [б.и.]
- Местоположение издательства: М.
- Первая страница: 147
- Последняя страница: 202
- Аннотация: Статья состоит из двух частей. В первой части рассматривается проблема проверки однозначности алфавитного декодирования в классе регулярных языков. Приводится ряд из нескольких ограничений на языки, выполнение которых позволяет построить новый решающий алгоритм и значительно улучшить его сложность в сравнении со сложностью аналогичного алгоритма из [4]. Вторая часть статьи посвящена проблеме проверки однозначности алфавитного декодирования для класса регулярных языков с полиномиальной функцией роста. Полученные в первой части статьи результаты ложатся в основу алгоритма, решающего рассматриваемую проблему. Разработана техника, позволяющая реализовать для языков с полиномиальной функцией роста те допущения, которые приведены в первой части статьи.
- Добавил в систему: Дергач Пётр Сергеевич