Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Testing Systems with Behavior Parallelism Based on a Reduced Reachability Graph
Authors
	Cheremisinova L.D.
Date of publication
	2022
DOI
	10.31114/2078-7707-2022-4-71-78
Abstract
	The paper deals with the problem of verification of the functional correctness of reactive control systems with respect to their design specification. When solving the problem of implementing control devices, one has to deal with the parallelism present in control objects, which is displayed in the specification for control system designing. It is assumed that the description of the device operation is given in the language of parallel automata [4] and it is correct. The subject is to analyze the implementation of the control system for input-output conformance, which is performed by simulation of its behavior on the area of its desired operation. The test sequence generation is based on traversing the graph of reachable states of the parallel automaton. But the size of the reachability graph grows exponentially with the number of states and transitions. In addition, for systems with behavioral parallelism the degree of parallelism of the automaton has a very negative impact on the graph size and performance of testing because of necessity to enumerate all possible orders of transitions firing. A method of reduction of the reachability graph for a parallel automaton is proposed, which is based on the assumption that the parallel automaton transitions are independent and may be executed in different order. The reduction of the reachability graph is achieved by extending the partial order on the set of transitions, which makes it possible to significantly reduce the number of considered states of the control system and, accordingly, the number of graph vertices and arcs. The obtained reduction of reachability graphs of parallel automata allows us to solve problem of constructing tests for more complex control systems with parallelism of behavior
Keywords
	parallel automaton, verification, reachability graph, design specification.
Library reference
	Cheremisinova L.D. Testing Systems with Behavior Parallelism Based on a Reduced Reachability Graph // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2022. Issue 4. P. 71-78. doi:10.31114/2078-7707-2022-4-71-78
URL of paper
	http://www.mes-conference.ru/data/year2022/pdf/D059.pdf