Анализ структуры атрибутных транзиционных систем без скрытых переходов

Abstract

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

Проведено теоретико-множинний аналіз структури атрибутних транзиційних систем без прихованих переходів. Запропоновано часткові операції композиції історій і трас. Показано можливість їхнього застосування для розпаралелювання побудови покриттів множин історій та трас. Визначено відношення еквівалентності на множині станів. У термінах систем із заданими початковими і фінальними станами, а також систем з заданими початковими станами і множинами фінальних граничних множин станів визначено класи безпечних і коректних систем. Побудовано алгебру таких систем.

The paper carries out set-theoretic analysis of the structure of attributed transition systems without hidden transitions. Partial operations of composition of histories and traces are proposed. It is shown that they can be used to parallelize the design of coverings of sets of histories and traces. Equivalence relations on the set of states are extracted. In terms of systems with distinguished initial and final states, as well as systems with distinguished initial states and sets of final limit sets of states, classes of safe and correct systems are defined. The algebra of such systems is proposed.