On observability subspaces

The paper presents an in depth study of topics in geometric control pertaining to observer theory from a functional point of view. We give characterizations of several classes of subspaces, including observability, almost observability and reconstructibility subspaces. We solve completely the problem of spectral assignability for observer dynamics by generalizing Rosenbrock's pole placement theorem. These results are then applied to observer theory.     

On a multiserver markovian queueing system with balking and reneging

In this paper a multi-server queueing model with balking and reneging is considered. Steady-state distribution of the number of customers in the system is obtained. An expression for the average loss of customers during a fixed duration of time is also advanced.     

Maximal and minimal representations of gapped and non-gapped motifs of a string

The problems of finding maximal and minimal equivalent representations for gapped and non-gapped motifs as well as finding motifs that characterize a fixed set of occurrence locations for a given string are studied. We apply two equivalence relations on representations. The first one is the well-known occurrence-equivalence of motifs. The second equivalence is introduced for patterns of occurrence locations, to characterize such patterns by motifs. For both equivalences, quadratic-time algorithms are given for finding a maximal representative of an equivalence class. Finding a minimal representative is shown to be NP-complete in both cases. For non-gapped motifs suffix-tree-based linear-time algorithms are given for finding maximal and minimal representatives. Maximal (minimal) gapped motifs are composed of blocks that are maximal (minimal) non-gapped motifs, maximal and minimal non-gapped motifs thus making up a small basis for all motifs. The implied bound on the number of gapped motifs that have a fixed number of non-gapped blocks is also given.     

On the computation of controllability subspaces

A procedure to determine parametric expressions for the basis matrices of all possible controllability subspaces (c.s.)  of a pair (A, B) is presented. Based on this procedure the paramotrization of the basis matrices corresponding to the family of c.s. of (A, B) that are contained in the kernel of the output map c becomes possible. This result leads to an alternative method of computing the maximal c.s.  of )A, B) contained in the kernel of c, which avoids the intermediate computation of the maximal (A, B)-invarianfc subspaco contained in ker C.     

On minimal graphs

Graphs, regarded as grammar forms as well as coloring specifications, induce graph-families, so-called color-families. It can be shown that for each color-family a unique (vertex) minimal graph exists. In this paper an operation on such minimal graphs is presented. As a main result it is shown that in a minimal graph G with m vertices, none of them adjacent to all other vertices, cliques have less than $\text{1}\text{2}$m vertices and this bound cannot be improved.     

On Markov chains generated by markovian controlled Markov systems: Structural stability

From the viewpoint of applying the framework of structural stability theory for dynamical systems defined on manifolds to the analysis of structural stability problems for discrete stochastic systems, this paper deals with the structural stability problem that arises when one considers the effects of small perturbations of transition matrices of an underlying Markov system M upon the ergodic properties and the other behaviour of a non-homogeneous Markov chain generated by a markovian controlled Markov system M^B (proposed by Komota el al. previously) and of a Markov system M, respectively. The concepts of three kinds of stability, namely, ergodic stability, ultimate stability and strong stability, are introduced and the necessary and sufficient conditions for a given Markov chain and for a given Markov system to be stable in the sense of these three kinds of stability are presented. As a consequence of these results, it is made clear that the three kinds of stability are equivalent in both cases. Finally, it is proved that the class of structurally stable Markov systems is open and dense in the metric space of all Markov systems defined on fixed state set and input set. This open—dense theorem is analogous in some sense to Peixoto's open-dense theorem for the class of structurally stable dynamical systems defined on a compact differentiate manifold.     

On minimal energy trajectories

Among all trajectories in the plane that have a given location and direction of endpoints, the one that minimizes the integral of the squared curvature is defined as the minimal energy trajectory. Plane trajectories minimizing a length-normalized and thus scale-invariant energy measure are discussed along with algorithms for obtaining them. It is shown that a scale-invariant measure is more natural for the design of interpolation and shape completion curves, and with this measure, circular arcs are optimal in a large number of situations. A simple numerical procedure is proposed for computing piecewise linear approximations of optimal trajectories as a solution of discrete two-point boundary value problems. Such trajectories are useful in computer graphics, geometric design, and motion planning of robots.     

On computing minimal models

This paper addresses the problem of computing the minimal models of a given CNF propositional theory. We present two groups of algorithms. Algorithms in the first group are efficient when the theory is almost Horn, that is, when there are few non-Horn clauses and/or when the set of all literals that appear positive in any non-Horn clause is small. Algorithms in the other group are efficient when the theory can be represented as an acyclic network of low-arity relations. Our algorithms suggest several characterizations of tractable subsets for the problem of finding minimal models.This work was partially supported by an IBM graduate fellowship to the first author, by NSF grants IRI-9157636 and IRI-9200918, by Air Force Office of Scientific Research grant AFOSR 900136, by a grant from Xerox Palo Alto research center, and by Toshiba of America. Part of this work was done while the first author was a graduate student at the Cognitive Systems Laboratory, Computer Science Department, University of California, Los Angeles, California, USA.     

On correction equations and domain decomposition for computing invariant subspaces

By considering the eigenvalue problem as a system of nonlinear equations, it is possible to develop a number of solution schemes which are related to the Newton iteration. For example, to compute eigenvalues and eigenvectors of an n × n matrix A, the Davidson and the Jacobi-Davidson techniques, construct ‘good’ basis vectors by approximately solving a “correction equation” which provides a correction to be added to the current approximation of the sought eigenvector. That equation is a linear system with the residual r of the approximated eigenvector as right-hand side.One of the goals of this paper is to extend this general technique to the “block” situation, i.e., the case where a set of p approximate eigenpairs is available, in which case the residual r becomes an n × p matrix. As will be seen, solving the correction equation in block form requires solving a Sylvester system of equations. The paper will define two algorithms based on this approach. For symmetric real matrices, the first algorithm converges quadratically and the second cubically. A second goal of the paper is to consider the class of substructuring methods such as the component mode synthesis (CMS) and the automatic multi-level substructuring (AMLS) methods, and to view them from the angle of the block correction equation. In particular this viewpoint allows us to define an iterative version of well-known one-level substructuring algorithms (CMS or one-level AMLS). Experiments are reported to illustrate the convergence behavior of these methods.     

On controllability,near-controllability,controllable subspaces,and nearly-controllable subspaces of a class of discrete-time multi-input bilinear systems

This paper considers a class of discrete-time multi-input inhomogeneous bilinear systems. The structure of such systems is most close to linear time-invariant systems’ but they own a strong property. That is, if the systems are uncontrollable, they can still be nearly controllable. Necessary and sufficient conditions for controllability and near-controllability of the systems are established by using a classical decomposition. Furthermore, a geometric characterization is given for the systems such that controllable subspaces and nearly-controllable subspaces are derived and characterized. Similar results on controllability are also obtained for the continuous-time counterparts of the systems. Finally, examples are provided to demonstrate the conceptions and results of this paper.     

On almost invariant subspaces of structural systems anddecentralized control

Graph-theoretic conditions are obtained for a structured system to have the property that the supremal L_p-almost invariant (controllability) subspace is generically the entire state space and that the infimal ^L_p-almost conditional invariant (complementary observability) subspace is generically the zero subspace. The conditions are used to determine stabilizability of structured interconnected systems by means of decentralized feedback control. Although the obtained graph-theoretic conditions are conservative, they are considered satisfactory to the extent that the benefits of easy testability involving only binary calculations outweigh the conservativeness in the results     

On almost invariant subspaces for implicit linear discrete-time systems

The concept of almost invariant subspace for an implicit linear discrete-time system is introduced and studied in detail. It is shown also that for regular homogeneous implicit systems the so-called deflating subspaces can be identified with almost invariant subspaces.