Аннотация:
Детерминированные и недетерминированные конечные автоматы распознают одно и то же семейство языков. Хорошо известно, что детерминизация может приводить к экспоненциальному росту числа состояний. (Естественно напрашиваются аналогии с проблемой перебора.) Можно выделить некоторые промежуточные классы конечных автоматов, например, однозначные конечные автоматы, а также различные другие модификации конечных автоматов. Операции над языками при разных представлениях будут по-разному влиять на количество состояний.
В докладе будет дан обзор результатов о сложности в терминах количества состояний для разных видов автоматов и приведены некоторые новые результаты.
