О сложности задачи генерации строк

В работе рассматривается сложность задачи генерации строк, принадлежащих определенным языкам и удовлетворяющих некоторым дополнительным ограничениям. Языки задаются при помощи формальных грамматик и автоматов. Предлагается следующая формулировка этой задачи в виде задачи распознавания свойств: для заданного языка, представленного формальной грамматикой или автоматом, и для заданной пары строк выяснить, существует ли строка из этого языка, лежащая лексикографически между этими строками. Установлено, что такая задача NLOGSPACE-полна для детерминированных и недетерминированных конечных автоматов, а также для линейных контекстно-свободных грамматик; P-полна для контекстно-свободных грамматик общего вида; NP-полна для альтернирующих конечных автоматов, для конъюнктивных грамматик и для линейных конъюнктивных грамматик; PSPACE-полна для контекстно-зависимых грамматик и линейно ограниченных по памяти машин Тьюринга.