Конечные автоматы. Теория, алгоритмы, сложность. Учебник для студентов вузов. Сергей Лукьянович Кривой. Букрек

В учебнике рассматриваются основные понятия теории конечных автоматов над словами конечной и бесконечной длины. Приводятся алгоритмы синтеза, анализа, эквивалентных преобразований конечных автоматов, а также примеры решения основных алгоритмических проблем для языков, акцептуемых этими автоматами. Описываются связи теории конечных автоматов с темпоральной линейной логикой и их применение в компьютерной алгебре, трансляции, идентификации, генетике, верификации и т.д. Рассмотрены основные понятия теории конечных временных автоматов и их применение к верификации свойств систем с временными ограничениями и, в частности, к анализу свойств временных сетей Петри. Описаны основные свойства КА над деревьями и свойства магазинных автоматов. Учебник предназначен для научных сотрудников, аспирантов, преподавателей и студентов старших курсов высших учебных заведений.