Studying synchronization issues for extended automata

Overview & Synopsis

The paper presents a study of synchronization issues for one of non-classical state models, i.e., a state identification problem widely used in the area of Model based Testing (MBT) and run-time verification / monitoring. We consider Finite Automata (FA) augmented with the context variables and their related updates when the transitions are executed. For such Extended Automata (EA) we define the notions of merging and synchronizing sequences that serve as reset words in MBT, and show that under certain conditions and when every context variable is defined over a ring, it is possible for the extended automata of the studied class to 'repeat' the necessary and sufficient conditions established for the classical automata. Otherwise, in a general case, the problem can be reduced to deriving reset words for classical FA that represent corresponding EA slices.