5 December 2007 in Physical Review E
We consider the problem of determining the proportion of edges that are discovered in an Erdős-Rényi graph when one constructs all shortest paths from a given source node to all other nodes. This problem is equivalent to the one of determining the proportion of edges connecting nodes that are at identical distance from the source node. The evolution of this quantity with the probability of existence of the edges exhibits intriguing oscillatory behavior. In order to perform our analysis, we introduce a different way of computing the distribution of distances between nodes. Our method outperforms previous similar analyses and leads to estimates that coincide remarkably well with numerical simulations. It allows us to characterize the phase transitions appearing when the connectivity probability varies.
1 May 2014 in Discrete Applied Mathematics
8 December 2017 in IEEE Transactions on Automatic Control
We provide algorithmically verifiable necessary and sufficient conditions for fundamental system theoretic properties of discrete-time linear systems subject to data losses. More precisely, the systems in our modeling framework are subject to disruptions (data losses) in the feedback loop, where the set of possible data loss sequences is captured by an automaton. As such, the results are applicable in the context of shared (wireless) communication networks and/or embedded architectures where some information on the data loss behaviour is available a priori. We propose an algorithm for deciding observability (or the absence of it) for such systems, and show how this algorithm can be used also to decide other properties including constructibility, controllability, reachability, null-controllability, detectability and stabilizability by means of relations that we establish among these properties. The main apparatus for our analysis is the celebrated Skolem's Theorem from Linear Algebra. Moreover, we study the relation between the model adopted in this paper and a previously introduced model where, instead of allowing dropouts in the feedback loop, one allows for ti
12 June 2017 in IEEE Control Systems Letters
We study discrete time linear constrained switching systems with additive disturbances, in the general setting where the switching acts on the system matrices, the disturbance sets, and the state constraint sets. Our primary goal is to extend the existing invariant set constructions when the switching signal is constrained by a given automation. We achieve it by working with a relaxation of invariance, namely the multi-set invariance. By exploiting recent results on computing the stability metrics for these systems, we establish explicit bounds on the number of iterations required for each construction. Last, as an application, we develop new maximal invariant set constructions for the case of linear systems in far fewer iterations compared to the state-of-the-art.
6 August 2018 in IEEE Transactions on Automatic Control
We study optimization-based criteria for the stability of switching systems, known as Path-Complete Lyapunov Functions, and ask the question “can we decide algorithmically when a criterion is less conservative than another'”. Our contribution is twofold. First, we show that a Path-Complete Lyapunov Function, which is a multiple Lyapunov function by nature, can always be expressed as a common Lyapunov function taking the form of a combination of minima and maxima of the elementary functions that compose it. Geometrically, our results provide for each Path-Complete criterion an implied invariant set. Second, we provide a linear programming criterion allowing to compare the conservativeness of two arbitrary given Path-Complete Lyapunov functions.