Описание:В спецкурсе изложены результаты исследования оценок сложности построения элементарного базиса для линейных автоматов. Доказываются условия A-полноты и K-полноты систем линейных автоматов над конечными полями. Выводятся оценки сложности получения элементарных базисов для A-полноты над произвольными полями. Для K-полноты оценки сложности доказываются для линейных автоматов над полем. Курс предполагает уверенное владение основным курсом дискретной математики и теории автоматов.
