Search

A nonnegative matrix $A$ is called primitive if $A^k$ is positive for some integer $k>0$. A generalization of this concept to finite sets of matrices is as follows: a set of matrices $\mathcal M = \{A_1, A_2, \ldots, A_m \}$ is primitive if $A_{i_1} A_{i_2} \ldots A_{i_k}$ is positive for some indices $i_1, i_2, ..., i_k$. The concept of primitive sets of matrices comes up in a number of problems within the study of discrete-time switched systems. In this paper, we analyze the computational complexity of deciding if a given set of matrices is primitive and we derive bounds on the length of the shortest positive product. We show that while primitivity is algorithmically decidable, unless $P=NP$ it is not possible to decide primitivity of a matrix set in polynomial time. Moreover, we show that the length of the shortest positive sequence can be superpolynomial in the dimension of the matrices. On the other hand, defining ${\mathcal P}$ to be the set of matrices with no zero rows or columns, we give a simple combinatorial proof of a previously-known characterization of primitivity for matrices in ${\mathcal P}$ which can be tested in polynomial time. This latter observation is related to the well-known 1964 conjecture of Cerny on synchronizing automata; in fact, any bound on the minimal length of a synchronizing word for synchronizing automata immediately translates into a bound on the length of the shortest positive product of a primitive set of matrices in ${\mathcal P}$. In particular, any primitive set of $n \times n$ matrices in ${\mathcal P}$ has a positive product of length $O(n^3)$.

A set of stochastic matrices ${\cal P}$ is a consensus set if for every sequence of matrices $P(1), P(2), \ldots$ whose elements belong to ${\cal P}$ and every initial state $x(0)$, the sequence of states defined by $x(t) = P(t) P(t-1) \cdots P(1) x(0)$ converges to a vector whose entries are all identical. In this paper, we introduce an "avoiding set condition" for compact sets of matrices and prove in our main theorem that this explicit combinatorial condition is both necessary and sufficient for consensus. We show that several of the conditions for consensus proposed in the literature can be directly derived from the avoiding set condition. The avoiding set condition is easy to check with an elementary algorithm, and so our result also establishes that consensus is algorithmically decidable. Direct verification of the avoiding set condition may require more than a polynomial time number of operations. This is however likely to be the case for any consensus checking algorithm since we also prove in this paper that unless $P=NP$, consensus cannot be decided in polynomial time.

International audience; We show that the set of realizations of a given dimension of a max-plus linear sequence is a finite union of polyhedral sets, which can be computed from any realization of the sequence. This yields an (expensive) algorithm to solve the max-plus minimal realization problem. These results are derived from general facts on rational expressions over idempotent commutative semirings: we show more generally that the set of values of the coefficients of a commutative rational expression in one letter that yield a given max-plus linear sequence is a semi-algebraic set in the max-plus sense. In particular, it is a finite union of polyhedral sets.

An edge-colored directed graph is \emph{observable} if an agent that moves along its edges is able to determine his position in the graph after a sufficiently long observation of the edge colors. When the agent is able to determine his position only from time to time, the graph is said to be \emph{partly observable}. Observability in graphs is desirable in situations where autonomous agents are moving on a network and one wants to localize them (or the agent wants to localize himself) with limited information. In this paper, we completely characterize observable and partly observable graphs and show how these concepts relate to observable discrete event systems and to local automata. Based on these characterizations, we provide polynomial time algorithms to decide observability, to decide partial observability, and to compute the minimal number of observations necessary for finding the position of an agent. In particular we prove that in the worst case this minimal number of observations increases quadratically with the number of nodes in the graph. From this it follows that it may be necessary for an agent to pass through the same node several times before he is finally able to determine his position in the graph. We then consider the more difficult question of assigning colors to a graph so as to make it observable and we prove that two different versions of this problem are NP-complete., 15 pages, 8 figures

We study decidability and complexity questions related to a continuous analogue of the Skolem-Pisot problem concerning the zeros and nonnegativity of a linear recurrent sequence. In particular, we show that the continuous version of the nonnegativity problem is NP-hard in general and we show that the presence of a zero is decidable for several subcases, including instances of depth two or less, although the decidability in general is left open. The problems may also be stated as reachability problems related to real zeros of exponential polynomials or solutions to initial value problems of linear differential equations, which are interesting problems in their own right.

We consider in this paper formations of autonomous agents moving in a two-dimensional space. Each agent tries to maintain its distances toward a pre-specified group of other agents constant and the problem is to determine if one can guarantee that the distance between every pair of agents (even those not explicitly maintained) remains constant, resulting in the persistence of the formation shape. We provide here a theoretical framework for studying this problem. We describe the constraints on the distance between agents by a directed graph and define persistent graphs. A graph is persistent if the shapes of almost all corresponding agent formations persist. Although persistence is related to the classical notion of rigidity, these are two distinct notions. We derive various properties of persistent graphs, and give a combinatorial criterion to decide persistence. We also define minimal persistence (persistence with the least possible number of edges), and we apply our results to the interesting special case of cycle-free graphs. Copyright (C) 2006 John Wiley & Sons, Ltd.

We introduce a concept of {similarity} between vertices of directed graphs. Let GA and GB be two directed graphs with, respectively, nA and nB vertices. We define an nB \times nA similarity matrix S whose real entry sij expresses how similar vertex j (in GA) is to vertex i (in GB): we say that sij is their similarity score. The similarity matrix can be obtained as the limit of the normalized even iterates of Sk+1 = BSkAT + BTSkA, where A and B are adjacency matrices of the graphs and S0 is a matrix whose entries are all equal to 1. In the special case where GA = GB = G, the matrix S is square and the score sij is the similarity score between the vertices i and j of G. We point out that Kleinberg's "hub and authority" method to identify web-pages relevant to a given query can be viewed as a special case of our definition in the case where one of the graphs has two vertices and a unique directed edge between them. In analogy to Kleinberg, we show that our similarity scores are given by the components of a dominant eigenvector of a nonnegative matrix. Potential applications of our similarity concept are numerous. We illustrate an application for the automatic extraction of synonyms in a monolingual dictionary.

We prove that several problems associated with probabilistic finite automata are undecidable for automata whose number of input letters and number of states are fixed. As a corollary of one of our results we prove that the problem of determining if the set of all products of two 47 x 47 matrices with nonnegative rational entries is bounded is undecidable.

We show that the boundedness of the set of all products of a given pair Sigma of rational matrices is undecidable. Furthermore, we show that the joint (or generalized) spectral radius rho(Sigma) is not computable: because testing whether rho(Sigma)less than or equal to1 is an undecidable problem. As a consequence, the robust stability of linear systems under time-varying perturbations is undecidable, and the same is true for the stability of a simple class of hybrid systems. We also discuss some connections with the so-called "finiteness conjecture". Our results are based on a simple reduction from the emptiness problem for probabilistic finite automata, which is known to be undecidable. (C) 2000 Elsevier Science B.V. All rights reserved.

The lower and average spectral radii measure, respectively, the minimal and average growth rates of long products of matrices taken from a finite set. The logarithm of the average spectral radius is traditionally called the Lyapunov exponent. When one performs these products in the max-algebra, we obtain quantities that measure the performance of discrete event systems. We show that approximating the lower and average max-algebraic spectral radii is NP-hard.

One of the open problems in the max-plus-algebraic system theory for discrete event systems is the minimal realization problem. In this paper we present some results in connection with the minimal realization problem in the max-plus algebra. First we characterize the minimal system order of a max-linear discrete event system. We also introduce a canonical representation of the impulse response of a max-linear discrete event system. Next we consider a simplified version of the general minimal realization problem: the boolean minimal realization problem, i.e., we consider models in which the entries of the system matrices are either equal to the max-plus-algebraic zero element or to the max-plus-algebraic identity element. We give a lower bound for the minimal system order of a max-plus-algebraic boolean discrete event system. We show that the decision problem that corresponds to the boolean realization problem (i.e., deciding whether or not a boolean realization of a given order exists) is decidable, and that the boolean minimal realization problem can be solved in a number of elementary operations that is bounded from above by an exponential of the square of (any upper bound of) the minimal system order. We also point out some open problems, the most important of which is whether or not the boolean minimal realization problem can be solved in polynomial time.

A set of matrices over the integers is said to be k-mortal (with k positive integer) if the zero matrix can be expressed as a product of length k of matrices in the set. The set is said to be mortal if it is k-mortal for some finite k. We show that the problem of deciding whether a pair of 48 × 48 integer matrices is mortal is undecidable, and that the problem of deciding, for a given k, whether a pair of matrices is k-mortal is NP-complete.

We study the computational complexity of a general consensus problem for switched systems. A set of n × n stochastic matrices {P 1 , …, P k } is a consensus set if for every switching map τ : ℕ → {1, …, k} and for every initial state x(0), the sequence of states defined by x(t + 1) = P τ(t) x(t) converges to a state whose entries are all identical. We show in this paper that, unless P = NP, the problem of determining if a set of matrices is a consensus set cannot be decided in polynomial-time. As a consequence, unless P = NP, it is not possible to give efficiently checkable necessary and sufficient conditions for consensus. This provides a possible explanation for the absence of such conditions in the current literature on consensus. On the positive side, we provide a simple algorithm which checks whether {P 1 , …, P k } is a consensus set in a number of operations which scales as a doubly exponential in n.

Given a family of real or complex monic polynomials of fixed degree with one affine constraint on their coefficients, consider the problem of minimizing the root radius (largest modulus of the roots) or root abscissa (largest real part of the roots). We give constructive methods for efficiently computing the globally optimal value as well as an optimal polynomial when the optimal value is attained and an approximation when it is not. An optimal polynomial can always be chosen to have at most two distinct roots in the real case and just one distinct root in the complex case. Examples are presented illustrating the results, including several fixed-order controller optimal design problems.

In this paper, we present several descent methods that can be applied to nonnegative matrix factorization and we analyze a recently developed fast block coordinate method called Rank-one Residue Iteration (RRI). We also give a comparison of these different methods and show that the new block coordinate method has better properties in terms of approximation error and complexity. By interpreting this method as a rank-one approximation of the residue matrix, we prove that it \(converges\) and also extend it to the nonnegative tensor factorization and introduce some variants of the method by imposing some additional controllable constraints such as: sparsity, discreteness and smoothness.

We show that the simultaneous stabilizability of three linear systems, that is the question of knowing whether three linear systems are simultaneously stabilizable, is rationally undecidable. By this we mean that it is not possible to find necessary and sufficient conditions for simultaneous stabilization of the three systems in terms of expressions involving the coefficients of the three systems and combinations of arithmetical operations (additions, subtractions, multiplications, and divisions), logical operations (''and'' and ''or''), and sign test operations (equal to, greater than, greater than or equal to,...).

Given a family of real or complex monic polynomials of fixed degree with one fixed affine constraint on their coefficients, consider the problem of minimizing the root radius (largest modulus of the roots) or abscissa (largest real part of the roots). We give constructive methods for finding globally optimal solutions to these problems. In the real case, our methods are based on theorems that extend results in Raymond Chen's 1979 PhD thesis. In the complex case, our methods are based on theorems that are new, easier to state but harder to prove than in the real case. Examples are presented illustrating the results, including several fixed-order controller optimal design problems.

We study the propagation of information in social networks. To do so, we focus on a cascade model where nodes are infected with {probability $p_1$ after their first contact with the information and with probability $p_2$ at all subsequent contacts.} The diffusion starts from one random node and leads to a cascade of infection. It is shown that first and {subsequent} trials play different roles in the propagation and that the size of the cascade depends in a non-trivial way on $p_1$, $p_2$ and on the network structure. Second trials are shown to amplify the propagation in dense parts of the network while first trials are {dominant for the exploration of} new parts of the network and launching new seeds of infection., 7 pages, 6 figures

Overlap-free words are words over the alphabet A = {a, b} that do not contain factors of the form xvxvx, where x ∈ A and v ∈ A*. We analyze the asymptotic growth of the number un of overlapfree words of length n. We obtain explicit formulas for the minimal and maximal rates of growth of un in terms of spectral characteristics (the lower spectral radius and the joint spectral radius) of one set of matrices of dimension 20. Using these descriptions we provide estimates of the rates of growth that are within 0.4% and 0.03% of their exact value. The best previously known bounds were within 11% and 3% respectively. We prove that un actually has the same growth for "almost all" n. This "average" growth is distinct from the maximal and minimal rates and can also be expressed in terms of a spectral quantity (the Lyapunov exponent). We use this expression to estimate it.

We consider the problem of determining the proportion of edges that are discovered in an Erdos-Renyi 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 new 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., 12 pages, 8 figures (18 .eps files)

For a given finite set $\Sigma$ of matrices with nonnegative integer entries we study the growth of $$ \max_t(\Sigma) = \max\{\|A_{1}... A_{t}\|: A_i \in \Sigma\}.$$ We show how to determine in polynomial time whether the growth with $t$ is bounded, polynomial, or exponential, and we characterize precisely all possible behaviors., Comment: 20 pages, 4 figures, submitted to LAA

We consider questions related to the computation of the capacity of codes that avoid forbidden difference patterns. The maximal number of $n$-bit sequences whose pairwise differences do not contain some given forbidden difference patterns increases exponentially with $n$. The exponent is the capacity of the forbidden patterns, which is given by the logarithm of the joint spectral radius of a set of matrices constructed from the forbidden difference patterns. We provide a new family of bounds that allows for the approximation, in exponential time, of the capacity with arbitrary high degree of accuracy. We also provide a polynomial time algorithm for the problem of determining if the capacity of a set is positive, but we prove that the same problem becomes NP-hard when the sets of forbidden patterns are defined over an extended set of symbols. Finally, we prove the existence of extremal norms for the sets of matrices arising in the capacity computation. This result makes it possible to apply a specific (even though non polynomial) approximation algorithm. We illustrate this fact by computing exactly the capacity of codes that were only known approximately., Comment: 7 pages. Submitted to IEEE Trans. on Information Theory

We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or non-strict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and non-strict thresholds both lead to undecidable problems., 10 pages

In this paper, we introduce a procedure for approximating the joint spectral radius of a finite set of matrices with arbitrary precision. Our approximation procedure is based on semidefinite liftings and can be implemented in a recursive way. For two matrices even the first step of the procedure gives an approximation, whose relative quality is at least 1/sq.2, that is, more than 70%. The subsequent steps improve the quality but also increase the dimension of the auxiliary problem from which this approximation can be found. In an improved version of our approximation procedure we show how a relative quality of (1/sq.2exp.1/k) can be obtained by evaluating the spectral radius of a single matrix of dimension nexp.k(nexp.k+1)/2 where n is the dimension of the initial matrices. This result is computationally optimal in the sense that it provides an approximation of relative quality 1-E in time polynomial in nexp.1/E and it is known that, unless P=NP, no such algorithm is possible that runs in time polynomial in n and 1/E. For the special case of matrices with non-negative entries we prove that (1/2)exp.1/k pexp.1/k (A1exp.k + A2exp.k)

We analyse the computability and the complexity of various definitions of spectral radii for sets of matrices. We show that the joint and generalised spectral radii of two integer matrices are not approximable in polynomial time, and that, two related quantities-the lower spectral radius and the largest Lyapunov exponent-are not algorithmically approximable. As a corollary of these results we show that: 1) the problem of deciding if all possible products of two given matrices are stable is NP-hard, 2) the problem of deciding if at, least one product of two given matrices is stable is undecidable.

We show that the simultaneous stabilization question: When are three linear systems stabilizable by the same controller? cannot be solved by a semialgebraic set description nor be answered by computational machines.

In this paper we study problems such as: given a discrete time dynamical system of the form x(t + 1)= f(x(t)) where f: R-n --> R-n is a piecewise affine function, decide whether all trajectories converge to 0. We show in our main theorem that this Attractivity Problem is undecidable as soon as n greater than or equal to2. The same is true of two related problems: Stability (is the dynamical system globally asymptotically stable?) and Mortality (do all trajectories go through 0?). We then show that AM-activity and Stability become decidable in dimension 1 for continuous functions. (C) 2001 Elsevier Science B.V. All rights reserved.

A configuration of a Turing machine is given by a tape content together with a particular state of the machine. Petr Kůrka has conjectured that every Turing machine - when seen as a dynamical system on the space of its configurations - has at least one periodic orbit. In this paper, we provide an explicit counter-example to this conjecture. We also consider counter machines and prove that, in this case, the problem of determining if a given machine has a periodic orbit in configuration space is undecidable.

Colloque avec actes et comité de lecture. internationale.; International audience; We prove that several global properties (global convergence, global asymptotic stability, mortality, and nilpotence) of particular classes of discrete time dynamical systems are undecidable. Such results had been known only for point-to-point properties. We prove these properties undecidable for saturated linear dynamical systems, and for continuous piecewise affine dynamical systems in dimension three. We also describe some consequences of our results on the possible dynamics of such systems.

We consider the iterates of bilinear functions over the semiring (max, +). Equivalently, our object of study can be viewed as recognizable tree series over the semiring (max, +). In this semiring, a fundamental result associates the asymptotic behaviour of the iterates of a linear function with the maximal average weight of the circuits in a graph naturally associated with the function. Here we provide an analog for the 'iterates' of bilinear functions. We also give a triple recognizing the formal power series of the worst case behaviour. Remark. Due to space limitations, the proofs have been omitted. A full version can be obtained from the authors on request.

In this paper, we consider simple classes of nonlinear systems and prove that basic questions related to their stability and controllability are either undecidable or computationally intractable (NP-hard). As a special case, we consider a class of "hybrid" systems in which the state space is partitioned into two halfspaces. and the dynamics in each halfspace correspond to a different linear system.

A configuration of a Turing machine is given by a tape content together with a particular state of the machine. Petr Kůrka has conjectured that every Turing machine—when seen as a dynamical system on the space of its configurations—has at least one periodic orbit. In this paper, we provide an explicit counterexample to this conjecture. We also consider counter machines and prove that, in this case, the problem of determining if a given machine has a periodic orbit in configuration space is undecidable.

We describe Turing machines, tilings and infinite words as dynamical systems and analyze some of their dynamical properties. It is known that some of these systems do not always have periodic configurations; we prove that they always have quasi-periodic configurations and we quantify quasi-periodicity. We then study the decidability of dynamical properties for these systems. In analogy to Rice's theorem for computable functions, we derive a theorem that characterizes dynamical system properties that are undecidable. As an illustration of this result, we prove that topological entropy is undecidable for Turing machines and for tilings.

We show that the problem of determining if a given integer linear recurrent sequence has a zero-a problem that is known as "Pisot's problem"-is NP-hard. With a similar argument we show that the problem of finding the minimal realization dimension of a one-letter max-plus rational series is NP-hard. This last result answers a folklore question raised in the control literature on the max-plus approach to discrete event systems. Our results are simple consequences of a construction due to Stockmeyer and Meyer. (C) 2002 Elsevier Science Inc. All rights reserved.