China
Africa
Explore chapters and articles related to this topic
Scan Testing
Published in Vojin G. Oklobdzija, Digital Design and Fabrication, 2017
Knowing that DUT is modeled by a system graph called S-graph, the partial scan problem consists in finding the minimal feedback vertex set (MFSV). This is known as an NP-complete problem [4]. In an S-graph, the vertices are the DUT registers and the edges represent a combinational path from one register to another.
Achieving a global objective with competing networked agents in the framework of discrete event systems
Published in International Journal of Control, 2020
Seong-Jin Park, Kwang-Hyun Cho
We note that the condition in Theorem 3.1 is a sufficient condition. It means that there might exist other conditions for the existence of fixed points. In this paper, we have established the sufficient condition from the concept of feedback vertex sets in graph theory. In case every cycle in a network has at least one well-informed agent, the set of such well-informed agents corresponds to a feedback vertex set in the network. A feedback vertex set is a subset of vertices (nodes) in a directed graph, such that the removal of the set leaves the graph without directed cycles. It is well known that the nodes of a feedback vertex set determine the convergence of dynamical systems, e.g. network biology (Aracena, 2008; Mochizuki et al., 2013). In particular, Mochizuki et al. (2013) have shown that if the dynamics of the nodes of the feedback vertex set are given, then the dynamics of the whole system are determined uniquely in networks governed by nonlinear dynamics. It means that to drive the state of a network to a desirable steady state (called dynamical attractor), one needs to manipulate a feedback vertex set. The importance of feedback loops in determining the dynamical attractors of the network was recognised early on in the study of the dynamics of biological networks (Glass & Kauffman, 1973; Thomas, 1978). In this paper, we show that in the framework of discrete event systems, the convergence of decisions of agents connected by a network can be also characterised by the feedback vertex set of well-informed agents in each cycle.