|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
О сложности задачи генерации строкстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКДата последнего поиска статьи во внешних источниках: 21 мая 2019 г.
- Автор: Охотин Александр Сергеевич
- Журнал: Дискретная математика
- Том: 15
- Номер: 4
- Год издания: 2003
- Издательство: ФГБУ "Издательство "Наука"
- Местоположение издательства: Москва
- Первая страница: 84
- Последняя страница: 99
- DOI: 10.4213/dm217
- Аннотация: В работе рассматривается сложность задачи генерации строк, принадлежащих определенным языкам и удовлетворяющих некоторым дополнительным ограничениям. Языки задаются при помощи формальных грамматик и автоматов. Предлагается следующая формулировка этой задачи в виде задачи распознавания свойств: для заданного языка, представленного формальной грамматикой или автоматом, и для заданной пары строк выяснить, существует ли строка из этого языка, лежащая лексикографически между этими строками. Установлено, что такая задача NLOGSPACE-полна для детерминированных и недетерминированных конечных автоматов, а также для линейных контекстно-свободных грамматик; P-полна для контекстно-свободных грамматик общего вида; NP-полна для альтернирующих конечных автоматов, для конъюнктивных грамматик и для линейных конъюнктивных грамматик; PSPACE-полна для контекстно-зависимых грамматик и линейно ограниченных по памяти машин Тьюринга.
- Добавил в систему: Золин Евгений Евгеньевич