Simulating perfect channels with probabilistic lossy channels

We consider the problem of deciding whether an infinite-state system (expressed as a Markov chain) satisfies a correctness property with probability 1. This problem is, of course, undecidable for general infinite-state systems. We focus our attention on the model of probabilistic lossy channel systems consisting of finite-state processes that communicate over unbounded lossy FIFO channels. Abdulla and Jonsson have shown that safety properties are decidable while progress properties are undecidable for non-probabilistic lossy channel systems. Under assumptions of “sufficiently high” probability of loss, Baier and Engelen have shown how to check whether a property holds of probabilistic lossy channel system with probability 1. In this paper, we consider a model of probabilistic lossy channel systems, where messages can be lost only during send transitions. In contrast to the model of Baier and Engelen, once a message is successfully sent to channel, it can only be removed through a transition which receives the message. We show that checking whether safety properties hold with probability 1 is undecidable for this model. Our proof depends upon simulating a perfect channel, with a high degree of confidence, using lossy channels.     

A “mixed” small gain and passivity theorem in the frequency domain

We show that the negative feedback interconnection of two causal, stable, linear time-invariant systems, with a “mixed” small gain and passivity property, is guaranteed to be finite-gain stable. This “mixed” small gain and passivity property refers to the characteristic that, at a particular frequency, systems in the feedback interconnection are either both “input and output strictly passive”; or both have “gain less than one”; or are both “input and output strictly passive” and simultaneously both have “gain less than one”. The “mixed” small gain and passivity property is described mathematically using the notion of dissipativity of systems, and finite-gain stability of the interconnection is proven via a stability result for dissipative interconnected systems.     

Control design for recycled, multi unit processes

An integrated multi-unit chemical plant presents a challenging control design problem due to the existence of recycling streams. In this paper, we develop a framework for analyzing the effects of recycling dynamics on closed-loop performance from which a systematic design of a decentralized control system for a recycled, multi-unit plant is established. In the proposed approach, the recycled streams are treated as unmodelled dynamics of the “unit” model so that their effects on closed-loop stability and performance can be analyzed using the robust control theory. As a result, two measures are produced: (1) the ν-gap metric, which quantifies the strength of recycling effects, and (2) the maximum stability margin of “unit” controller, which represents the ability of the “unit” controller to compensate for such effects. A simple rule for the “unit” control design is then established using the combined two measures in order to guarantee the attainment of good overall closed-loop performances. As illustrated by several design examples, the controllability of a recycled, multi unit process under a decentralized “unit” controller can be determined without requiring any detailed design of the “unit” controller because the simple rule is calculated from the open-loop information only.     

Interval logics and their decision procedures : Part II: a real-time interval logic

In a companion paper, we presented an interval logic, and showed that it is elementarily decidable. In this paper we extend the logic to allow reasoning about real-time properties of concurrent systems; we call this logic real-time future interval logic (RTFIL). We model time by the real numbers, and allow our syntax to state the bounds on the duration of an interval. RTFIL possesses the “real-time interpolation property,” which appears to be the natural quantitative counterpart of invariance under finite stuttering. As the main result of this paper, we show that RTFIL is decidable; the decision algorithm is slightly more expensive than for the untimed logic. Our decidability proof is based on the reduction of the satisfiability problem for the logic to the emptiness problem for timed Büchi automata. The latter problem was shown decidable by Alur and Dill in a landmark paper, in which this real-time extension of ω-automata was introduced. Finally, we consider an extension of the logic that allows intervals to be constructed by means of “real-time offsets”, and show that even this simple extension renders the logic highly undecidable.     

Unprejudiced optimal open loop input design for identification of transfer functions

The problem to estimate transfer functions of linear systems is considered. The quality of the resulting estimate depends, among other things, on the input used during the identification experiment. We measure the quality using a quadratic norm in the frequency domain. The problem to determine optimal inputs, i.e. inputs that minimize the chosen norm, subject to constrained input variance, has long been studied. We point out that such procedures may involve a prejudice (that the system is to be found in a certain model set) that may have some surprising effects. We discuss how such a prejudice can be reduced by allowing the possibility that the true system cannot be exactly described in the chosen model set. We also calculate explicit expressions for the resulting “unprejudiced” optimal inputs. These expressions relate the signal-to-noise ratio (as a function of frequency) to the chosen weighting function in the quadratic norm. We also point out the role of the employed noise model for the design.     

Spectral properties of infinite-dimensional closed-loop systems

We consider feedback systems obtained from infinite-dimensional well-posed linear systems by output feedback. Thus, our framework allows for unbounded control and observation operators. Our aim is to investigate the relationship between the open-loop system, the feedback operator K and the spectrum (in particular, the eigenvalues and eigenvectors) of the closed-loop generator A^K. We give a useful characterization of that part of the spectrum σ(A^K) which lies in the resolvent set of A, the open-loop generator, via the “characteristic equation” involving the open-loop transfer function. We show that certain points of σ(A) cannot be eigenvalues of A^K if the input and output are scalar (so that K is a number) and K≠0. We devote special attention to the case when the output feedback operator K is compact. It is relatively easy to prove that in this case, σ_e(A), the essential spectrum of A, is invariant, that is, it is equal to σ_e(A^K). A related but much harder problem is to determine the largest subset of σ(A) which remains invariant under compact output feedback. This set, which we call the immovable spectrum of A, strictly contains σ_e(A). We give an explicit characterization of the immovable spectrum and we investigate the consequences of our results for a certain class of well-posed systems obtained by interconnecting an infinite chain of identical systems.     

Universal stabilization of a class of nonlinear systems with homogeneous vector fields

Under relative-degree-one and minimum-phase assumptions, it is well known that the class of finite-dimensional, linear, single-input (u), single-output (y) systems (A,b,c) is universally stabilized by the feedback strategy u = Λ(λ)y, λ = y², where Λ is a function of Nussbaum type (the terminology “universal stabilization” being used in the sense of rendering /s(0/s) a global attractor for each member of the underlying class whilst assuring boundedness of the function λ(·)). A natural generalization of this result to a class ^k of nonlinear control systems (a,b,c), with positively homogeneous (of degree k 1) drift vector field a, is described. Specifically, under the relative-degree-one (cb ≠ 0) and minimum-phase hypotheses (the latter being interpreted as that of asymptotic stability of the equilibrium of the “zero dynamics”), it is shown that the strategy u = Λ(λ)/vby/vb^k−1y, assures ^k-universal stabilization. More generally, the strategy u = Λ(λ)exp(/vby/vb)y, assures -universal stabilization, where = _{k 1} ^k.     

An Integrated Approach for the Specification and Analysis of Stochastic Real-Time Systems

The usage of process algebras for the performance modeling and evaluation of concurrent systems turned out to be convenient due to their feature of compositionality. A particularly simple and elegant solution in this field is the calculus of Interactive Markov Chains (IMCs), where the behavior of processes is just represented by Continuous Time Markov Chains extended with action transitions representing process interaction. The main advantage of IMCs with respect to other existing approaches is that a notion of bisimulation which abstracts from τ-transitions (“complete” interactions) can be defined which is a congruence. However in the original definition of the calculus of IMCs the high potentiality of compositionally minimizing the system state space given by the usage of a “weak” notion of equivalence and the elegance of the approach is somehow limited by the fact that the equivalence adopted over action transitions is a finer variant of Milner's observational congruence that distinguishes τ-divergent “Zeno” processes from non-divergent ones. In this paper we show that it is possible to reformulate the calculus of IMCs in such a way that we can just rely on simple standard observational congruence. Moreover we show that the new calculus is the first Markovian process algebra allowing for a new notion of Markovian bisimulation equivalence which is coarser than the standard one.     

Deforestation, program transformation, and cut-elimination

The problem of proving that two programs, in any reasonable programming language, are equivalent is well-known to be undecidable. In a formal programming system, in which the rules for equivalence are finitely presented, the problem of provable equivalence is semi-decidable. Despite this improved situation there is a significant lack of generally accepted automated techniques for systematically searching for a proof (or disproof) of program equivalence. Techniques for searching for proofs of equivalence often stumble on the formulation of induction and, of course, coinduction (when it is present) which are often formulated in such a manner as to require inspired guesses.There are, however, well-known program transformation techniques which do address these issues. Of particular interest to this paper are the deforestation techniques introduced by Phil Wadler and the fold/unfold program transformation techniques introduced by Burstall and Darlington. These techniques are shadows of an underlying cut-elimination procedure and, as such, should be more generally recognized as proof techniques.In this paper we show that these techniques apply to languages which have both inductive and coinductive datatypes. The relationship between these program transformation techniques and cut-elimination requires a transformation from initial and final “algebra” proof rules into “circular” proof rules as introduced by Santocanale (and used implicitly in the model checking community). This transformation is only possible in certain proof systems. Here we show that it can be applied to cartesian closed categories with datatypes: closedness is an essential requirement. The cut-elimination theorems and attendant program transformation techniques presented here rely heavily on this alternate presentation of induction and coinduction.     

On the extension of solutions of linear constant-coefficient PDE

We solve the following over-determined boundary value problem (the “extension problem”): Let R(∂) be a matrix whose entries are linear partial differential operators, with constant coefficients. Let Ω be a non-empty, open, bounded, convex set. We consider the homogeneous system R(∂)f=0 in a neighborhood of , subject to the boundary condition f=g in a neighborhood of ∂Ω. For a given g, we give a criterion for the (unique) existence of a smooth solution f to this problem. There are two obvious necessary conditions: g is smooth and R(∂)g=0 in a neighborhood of ∂Ω. We characterize the class of differential operators R(∂) for which the problem is solvable for any g satisfying the necessary conditions. Finally, in the case where the solution is non-unique, we consider the possibility of obtaining uniqueness by fixing several components of the desired solution.     

Stability Radius of a Lexicographic Optimum of a Vector Problem of Boolean Programming

A Boolean problem of vector lexicographic optimization is considered. Its partial criteria are projections of linear functions on the nonnegative orthant. A formula is obtained for calculation of the limit level of perturbations of the parameter space of the problem with a metric l₁ that preserve the lexicographic optimality of a given solution.This work is performed within the framework of the State Program of Fundamental Investigations of the Republic of Belarus “Mathematical Structures 29.”__________Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 71–81, March–April 2005.     

Unfair Problems and Randomized Algorithms for Metrical Task Systems

Borodin, Linial, and Saks introduced a general model for online systems calledmetrical task systems(1992,J. Assoc. Comput. Mach.39(4), 745–763). In this paper, the unfair two state problem, a natural generalization of the two state metrical task system problem, is studied. A randomized algorithm for this problem is presented, and it is shown that this algorithm is optimal. Using the analysis of the unfair two state problem, a proof of a decomposition theorem similar to that of Blum, Karloff, Rabani, and Saks (1992, “Proc. 33rd Symposium on Foundations of Computer Science,” pp. 197–207) is presented. This theorem allows one to design divide and conquer algorithms for specific metrical task systems. Our theorem gives the same bounds asymptotically, but it has less restrictive boundary conditions.     

On global uniform asymptotic stability of nonlinear time-varying systems in cascade

In this short paper we deal with the stability analysis problem of nonautonomous nonlinear systems in cascade. In particular, we give sufficient conditions to guarantee that (i) a globally uniformly stable (GUS) nonlinear time-varying (NLTV) system remains GUS when it is perturbed by the output of a globally uniformly asymptotically stable (GUAS) NLTV system, under the assumption that the perturbing signal is absolutely integrable; (ii) if in addition the perturbed system is GUAS, it remains GUAS under the cascaded interconnection; (iii) two GUAS systems yield a GUAS cascaded system, under some growth restrictions over the Lyapunov function. Our proofs rely on the second method of Lyapunov, roughly speaking on a “δ- stability analysis”.     

On the decidability of fragments of the asynchronous π-calculus

We study the decidability of a reachability problem for various fragments of the asynchronous π-calculus. We consider the combination of three main features: name generation, name mobility, and unbounded control. We show that the combination of name generation with either name mobility or unbounded control leads to an undecidable fragment. On the other hand, we prove that name generation without name mobility and with bounded control is decidable by reduction to the coverability problem for Petri Nets.     

Averaging with disturbances and closeness of solutions

We establish that, under appropriate conditions, the solutions of a time-varying system with disturbances converge uniformly on compact time intervals to the solutions of the system's average as the rate of change of time increases to infinity. The notions of “average” used for systems with disturbances are the “strong” and “weak” averages introduced in Ne i and Teel (D. Ne i , A.R. Teel, Input-to-state stability for time-varying nonlinear systems via averaging, 1999, submitted for publication. See also: On averaging and the ISS property, Proceedings of the 38th Conference on Decision and Control, Phoenix, AZ, December 1999, pp. 3346–3351.)     

Computability in planar dynamical systems

In this paper we explore the problem of computing attractors and their respective basins of attraction for continuous-time planar dynamical systems. We consider C ¹ systems and show that stability is in general necessary (but may not be sufficient) to attain computability. In particular, we show that (a) the problem of determining the number of attractors in a given compact set is in general undecidable, even for analytic systems and (b) the attractors are semi-computable for stable systems. We also show that the basins of attraction are semi-computable if and only if the system is stable.     

Efficient constrained local model fitting for non-rigid face alignment

Active appearance models (AAMs) have demonstrated great utility when being employed for non-rigid face alignment/tracking. The “simultaneous” algorithm for fitting an AAM achieves good non-rigid face registration performance, but has poor real time performance (2–3 fps). The “project-out” algorithm for fitting an AAM achieves faster than real time performance (>200 fps) but suffers from poor generic alignment performance. In this paper we introduce an extension to a discriminative method for non-rigid face registration/tracking referred to as a constrained local model (CLM). Our proposed method is able to achieve superior performance to the “simultaneous” AAM algorithm along with real time fitting speeds (35 fps). We improve upon the canonical CLM formulation, to gain this performance, in a number of ways by employing: (i) linear SVMs as patch-experts, (ii) a simplified optimization criteria, and (iii) a composite rather than additive warp update step. Most notably, our simplified optimization criteria for fitting the CLM divides the problem of finding a single complex registration/warp displacement into that of finding N simple warp displacements. From these N simple warp displacements, a single complex warp displacement is estimated using a weighted least-squares constraint. Another major advantage of this simplified optimization lends from its ability to be parallelized, a step which we also theoretically explore in this paper. We refer to our approach for fitting the CLM as the “exhaustive local search” (ELS) algorithm. Experiments were conducted on the CMU MultiPIE database.     

A unique methodology for the stability robustness of multiple time delay systems

The stability robustness is considered for linear time invariant (LTI) systems with rationally independent multiple time delays against delay uncertainties. The problem is known to be notoriously complex, primarily because the systems are infinite dimensional due to delays. Multiplicity of the delays in this study complicates the analysis even further. And “rationally independent” feature of the delays makes the problem prohibitively challenging as opposed to the TDS with commensurate time delays (where time delays are rationally related). A unique framework is described for this broadly studied problem and the enabling propositions are proven. We show that this procedure analytically reveals all possible stability regions exclusively in the space of the delays. As an added strength, it does not require the delay-free system under consideration to be stable. Our methodology offers a resolution to this question, which has been studied from variety of directions in the past four decades. None of these respectable investigations can, however, deliver an exact and exhaustive robustness declaration. From this stand point the new method has a unique contribution.     

Spines of random constraint satisfaction problems: definition and connection with computational complexity

We study the connection between the order of phase transitions in combinatorial problems and the complexity of decision algorithms for such problems. We rigorously show that, for a class of random constraint satisfaction problems, a limited connection between the two phenomena indeed exists. Specifically, we extend the definition of the spine order parameter of Bollobás et al. [10] to random constraint satisfaction problems, rigorously showing that for such problems a discontinuity of the spine is associated with a 2^Ω(n) resolution complexity (and thus a 2^Ω(n) complexity of DPLL algorithms) on random instances. The two phenomena have a common underlying cause: the emergence of “large” (linear size) minimally unsatisfiable subformulas of a random formula at the satisfiability phase transition.We present several further results that add weight to the intuition that random constraint satisfaction problems with a sharp threshold and a continuous spine are “qualitatively similar to random 2-SAT”. Finally, we argue that it is the spine rather than the backbone parameter whose continuity has implications for the decision complexity of combinatorial problems, and we provide experimental evidence that the two parameters can behave in a different manner.AMS subject classification 68Q25, 82B27