Дескрипція автоматів їхньою поведінкою

Abstract

Розглянуто деякі питання дескрипції автоматів, у першу чергу, фрагментами поведінки. Наведено умови існування контрольних експериментів та ідентифікаторів станів автомата. Для систем визначальних співвідношень, якими може бути заданий автомат, вказано метричні характеристики, вказано зв'язок між визначальними співвідношеннями і контрольними експериментами. Для експериментів з груповими автоматами наведено точні оцінки складності таких експериментів.

Certain problems of automata description are considered, first and foremost with behavior fragments. Existence conditions for checking experiments and automaton's stare identifiers are given. Metric characterisation of the systems of automaton's defining relations is given, a link between checking experiments and defining relations is established. The exact complexity estimations for experiments with group automate are given.