Шаблон:Current Seminars — различия между версиями

В докладе рассматривается задача расшифровки функций алгебры логики, зависящих от n переменных, которые можно представить в виде элементарной дизъюнкции с ровно одной переменной с отрицанием. При расшифровке можно задавать вопросы о значении расшифровываемой функции на произвольном наборе значений ее переменных и получать правильные ответы. Функция считается расшифрованной, если восстановлены ее значения на всех возможных наборах значений ее переменных. Находятся верхняя и нижняя оценки наименьшего числа вопросов, которые требуется задать, чтобы расшифровать любую функцию от n переменных из рассматриваемого множества.

Доклад посвящен задачам анализа и синтеза временных автоматов. Временной автомат используется для описания поведения системы, которая переходит из состояния в состояние под действием входных воздействий, производя при этом выходные сигналы. Временная переменная позволяет учесть временные аспекты в поведении системы посредством введения временных ограничений по подаче входных символов, а также описания входных и выходных таймаутов. Для конечных автоматов с одной временной переменной рассматриваются классические задачи анализа и синтеза, такие как минимизация и композиция временных автоматов. Показывается, что для построения единственной приведенной (минимальной) формы детерминированного полностью определенного временного автомата недостаточно приведенной формы по состояниям, необходимо также минимизировать временные аспекты, и предлагается метод минимизации временного автомата. Во второй части доклада отмечается, что в отличие от классических автоматов, «медленная» внешняя среда и отсутствие осцилляций не являются достаточными условиями для описания параллельной композиции детерминированным временным автоматом, и формулируются достаточные условия, при которых операция параллельной композиции является замкнутой в множестве детерминированных временных автоматов. В последней части доклада отмечается, что автором получен ряд интересных результатов по синтезу проверяющих тестов с гарантированной полнотой для временных автоматов.