Аннотация:В статье изучается сложность разных естественных проблем разрешения для автоматов со словарём.Модель вычислений Автомат со словарём представляет собой конечный автомат, к которому в качестве структуры данных добавлено множество, которое мы называем словарём. Детерминированная версия данной модели вычислений была представлена М. Кутрибом, А. Мальхером и М. Ведландтом под названием Deterministic Set Automata на конференциях DLT2014 и DCFS2014. Эта модель вычислений представляет интерес, поскольку её структурные и вычислительные свойства схожи со структурными свойствами КС-языков, что даёт надежду на её практическое применение.
В данной работе мы получаем верхние и нижние оценки на вычислительную сложность языков, распознаваемых детерминированными и недетерминированными автоматами со словарём: эти языки принадлежат классам P и NP соответственно; приводим пример полных языков в данных классах. Также мы устанавливаем важные структурные свойства для данной модели. В частности, доказываем, что языки, распознаваемые автоматами со словарём, образуют рациональный конус.