A note on the controllability of nonlinear systems

In this paper a question of the controllability of nonlinear systems is considered. On the basis of theorems due to Graves, a new sufficient condition for local controllability is established.     

A note on dead-beat controllability of generalised Hammerstein systems

Necessary and sufficient conditions for dead-beat and complete controllability for a class of generalised Hammerstein systems are presented. Since the system's structure is very close to linear, only linear algebra is used for the controllability test. The test is very simple and easy to use. A closed-loop minimum-time dead-beat controller can be designed for a subclass of generalised Hammerstein systems using the Gröbner basis method.     

A note on single input controllability for normal systems

It is known that ifA is a normal reductive linear operator on a Hilbert space and the linear system {A, B} is controllable, then there exists a vectorb in the range ofB such that {A, B} is controllable. It is shown that this result does not hold for an arbitrary normal operatorA. Research partiablly supported by the National Science Foundation.     

A note on controllability of deterministic context-free systems

In this paper, we prove that the most important concept of supervisory control of discrete-event systems, the controllability property, is undecidable for two deterministic context-free languages $K$ and $L$, where $L$ is prefix closed, even though $K$ is a subset of $L$. If $K$ is not a subset of $L$, the undecidability follows from the work by Sreenivas. However, the case where $K$ is a subset of $L$ does not follow from that work because it is decidable whether $K$ and $L$ are equivalent as shown by Sénizergues. Thus, our result completes this study. The problem is also mentioned as open in the Ph.D. thesis by Griffin, who extended the supervisory control framework so that the specification language is modeled as a deterministic context-free language (compared to the classical approach where the specification is regular) and the plant language is regular. This approach is of interest because it brings an opportunity for more concise representations of the specification (as discussed, e.g., in the work by Geffert et al.) and, therefore, in some sense it treats the most interesting problem of current supervisory control theory, the state-space explosion problem.     

A note on non-singular deterministic pushdown automata

The non-singular deterministic pushdown automata were first defined by Valiant as an example of a class of machines with a decidable equivalence problem [3]. No algorithm currently exist for deciding whether or not a deterministic pushdown automation is non-singular, so the applicability of Valiant's equivalence decision procedure cannot be readily (if ever) determined. In this paper, it is shown that the equivalence problem for non-singular automata is reducible to the problem of deciding whether or not a deterministic pushdown automaton is non-singular.     

Budget-bounded model-checking pushdown systems

We address the verification problem for concurrent programs modeled as multi-pushdown systems (MPDS). In general, MPDS are Turing powerful and hence come along with undecidability of all basic decision problems. Because of this, several subclasses of MPDS have been proposed and studied in the literature (Atig et al. in LNCS, Springer, Berlin, 2005; La Torre et al. in LICS, IEEE, 2007; Lange and Lei in Inf Didact 8, 2009; Qadeer and Rehof in TACAS, LNCS, Springer, Berlin, 2005). In this paper, we propose the class of bounded-budget MPDS, which are restricted in the sense that each stack can perform an unbounded number of context switches only if its depth is below a given bound, and a bounded number of context switches otherwise. We show that the reachability problem for this subclass is Pspace-complete and that LTL-model-checking is Exptime-complete. Furthermore, we propose a code-to-code translation that inputs a concurrent program \(P\) and produces a sequential program \(P'\) such that running \(P\) under the budget-bounded restriction yields the same set of reachable states as running \(P'\) . Moreover, detecting (fair) non-terminating executions in \(P\) can be reduced to LTL-Model-Checking of \(P'\) . By leveraging standard sequential analysis tools, we have implemented a prototype tool and applied it on a set of benchmarks, showing the feasibility of our translation.     

A note ‘ On the controllability of distributed parameter systems ’†

The aim of this note is to give a simple proof of an improved anil equivalent result to the one derived in the article under consideration, Herget (1970).     

Discrete-time linear periodic systems: A note on the reachability and controllability interval length

Discrete-time linear systems with periodic coefficients of period T are considered in this paper. The reachability and controllability indices at time t for periodic systems, μ_rt and μ_ct, are defined. It is shown that the reachability [controllability] subspace at time t does coincide with the reachability [controllability] subspace over the interval (t − μ_rt,T, t) [(t, t + μ_ct.,T)] and properly includes the reachability [controllability] subspace over the interval (t −(μ_rt−1) T, t) [(t, t +(μ_cr−1)T)].     

A controllability theory for nonlinear systems

A Lyapunov-like approach to the controllability of nonlinear dynamic systems is presented. A theory is developed which yields sufficient conditions for complete controllability for some classes of nonlinear systems; feedback controllers which drive the systems to desired terminal conditions, at a specified final time, are also obtained. Well-known controllability conditions for linear dynamic systems are derived using this general controllability theory. Elliptical regions are found which contain (bound) the trajectories of a class of systems controlled according to these methods. These regions are used in synthesizing controllers for nonlinear systems and for a class of state-variable inequality constrained problems. An uncontrollability theorem, based also upon Lyapunov-like notions, is presented; this yields sufficiency conditions for uncontrollability for some types of nonlinear systems. Relationships of the theories to other nonlinear controllability approaches are indicated.     

A note on the controllability for the wave equation in nonsmooth plane domains

We study exact boundary controllability for a two-dimensional wave equation in a region which is an angular sector of a circle or an angular sector of an annular region. The control, of Neumann type, acts on the curved part of the boundary, while in the straight part we impose homogeneous Dirichlet boundary condition. The initial state has finite energy and the control is square integrable.     

A note on transition systems

This paper introduces a mathematical structure called transition systems. The notion of transition systems has been developed as a result of the study of Petri nets and vector addition systems. The intended use of transition systems is to model concurrent and asynchronous events. The concept of information flow in a complex system and communication between parts of a complex system can be formulated in this formal structure. This paper is concerned with the mathematical properties rather than the applications of transition systems. Patterns of activities in complex systems are defined in terms of termination and finiteness properties of transition systems. Concepts of conservation and repetitivity have been introduced. Structural properties of restricted classes of transition systems have been studied.     

A note on transition systems

This paper introduces a mathematical structure called transition systems. The notion of transition systems has been developed as a result of the study of Petri nets and vector addition systems. The intended use of transition systems is to model concurrent and asynchronous events. The concept of information flow in a complex system and communication between parts of a complex system can be formulated in this formal structure. This paper is concerned with the mathematical properties rather than the applications of transition systems. Patterns of activities in complex systems are defined in terms of termination and finiteness properties of transition systems. Concepts of conservation and repetitivity have been introduced. Structural properties of restricted classes of transition systems have been studied.     

Model checking probabilistic systems against pushdown specifications

Model checking is a fully automatic verification technique traditionally used to verify finite-state systems against regular specifications. Although regular specifications have been proven to be feasible in practice, many desirable specifications are non-regular. For instance, requirements which involve counting cannot be formalized by regular specifications but using pushdown specifications, i.e., context-free properties represented by pushdown automata. Research on model-checking techniques for pushdown specifications is, however, rare and limited to the verification of non-probabilistic systems.In this paper, we address the probabilistic model-checking problem for systems modeled by discrete-time Markov chains and specifications that are provided by deterministic pushdown automata over infinite words. We first consider finite-state Markov chains and show that the quantitative and qualitative model-checking problem is solvable via a product construction and techniques that are known for the verification of probabilistic pushdown automata. Then, we consider recursive systems modeled by probabilistic pushdown automata with an infinite-state Markov chain semantics. We first show that imposing appropriate compatibility (visibility) restrictions on the synchronizations between the pushdown automaton for the system and the specification, decidability of the probabilistic model-checking problem can be established. Finally we prove that slightly departing from this compatibility assumption leads to the undecidability of the probabilistic model-checking problem, even for qualitative properties specified by deterministic context-free specifications.     

通信下推系统的一种有界可达算法

Qadeer首次针对并发下推系统提出一种有界可达算法,通过限定上下文切换的次数使得算法可终止,可有效地分析过程间并发程序。但是并发下推系统以全局变量模拟同步,不适应于当前广泛使用的基于事件驱动的并发程序。针对通信下推系统,提出一种基于双重调度的有界可达算法,通过限定同步调度的次数,结合线程间的同步调度和线程内的路径调度解决通信下推系统的可达性问题,从而为事件驱动的过程间并发程序分析提供了算法基础。     

Structural controllability in non-linear systems

Changes with respect to controllability or uncontrollability behaviour of perturbed linear and non-linear systems are examined. The perturbations are considered to be either arbitrary or the result of the action of a transformation group. Certain conclusions concerning the transformation of electrical networks are drawn.