Splitting Mobility and Communication in Boxed Ambients

Stemming from our previous work on BACI, a boxed ambient calculus with communication in- terfaces, we define a new calculus that further enhances communication mechanisms and mobility control by introducing multiple communication ports, access control lists, and port hiding.The development of the calculus is mainly focused on three objectives: separation of concerns between mobility and communication, fine-grained controls, and locality. Communication primi- tives use ports to establish communication channels between ambients, while ambient names are only used for mobility. In order to achieve a better control over mobility, the calculus includes co-capabilities à la Safe Ambients, but with the addition of access control lists. These lists contain the names of the ambients that are allowed to enter or exit the ambient with that co-capability.The resulting calculus not only provides more flexibility and expressiveness than Boxed Ambients, but also enables simpler implementations using more powerful constructs for communication and mobility. We establish the basic meta-theory of the calculus by providing rules for type safety and showing that typing is preserved during execution.     

A theory of structural stationarity in the <Emphasis Type="Italic">π</Emphasis>-Calculus

Automata-theoretic representations have proven useful in the automatic and exact analysis of computing systems. We propose a new semantical mapping of π-Calculus processes into place/transition Petri nets. Our translation exploits the connections created by restricted names and can yield finite nets even for processes with unbounded name and unbounded process creation. The property of structural stationarity characterises the processes mapped to finite nets. We provide exact conditions for structural stationarity using novel characteristic functions. As application of the theory, we identify a rich syntactic class of structurally stationary processes, called finite handler processes. Our Petri net translation facilitates the automatic verification of a case study modelled in this class.     

Reachability Analysis of Synchronized PA Systems

We present a generic approach for the analysis of concurrent programs with (unbounded) dynamic creation of threads and recursive procedure calls. We define a model for such programs based on a set of term rewrite rules where terms represent control configurations. The reachability problem for this model is undecidable. Therefore, we propose a method for analyzing such models based on computing abstractions of their sets of computation paths. Our approach allows to compute such abstractions as least solutions of a system of (path language) constraints. More precisely, given a program and two regular sets of configurations (process terms) T and T^′, we provide (1) a construction of a system of constraints which characterizes the set of computation paths leading from T to T^′, and (2) a generic framework, based on abstract interpretation, allowing to solve this system in various abstract domains leading to abstract analysis with different precision and cost.     

Improved depth lower bounds for small distance connectivity

We consider the problem of determining, given a graph G with specified nodes s and t, whether or not there is a path of at most k edges in G from s to t. We show that solving this problem on polynomialsize unbounded fan-in circuits requires depth , improving on a depth lower bound of when given by Ajtai (1989), Bellantoni et al. (1992). More generally, we obtain an improved size-depth tradeoff lower bound for the problem for all .?The key to our technique is a new form of “switching lemma” which combines some of the features of iteratively shortening terms due to Furst et al. (1984) and Ajtai (1983) with the features of switching lemma arguments introduced by Yao (1985), H?stad (1987), and Cai (1986) that have been the methods of choice for subsequent results. Received: July 2, 1996.     

Control of an unstable reaction–diffusion PDE with long input delay

A Smith Predictor-like design for compensation of arbitrarily long input delays is available for general, controllable, possibly unstable LTI finite-dimensional systems. Such a design has not been proposed previously for problems where the plant is a PDE. We present a design and stability analysis for a prototype problem, where the plant is a reaction–diffusion (parabolic) PDE, with boundary control. The plant has an arbitrary number of unstable eigenvalues and arbitrarily long delay, with an unbounded input operator. The predictor-based feedback design extends fairly routinely, within the framework of infinite-dimensional backstepping. However, the stability analysis contains interesting features that do not arise in predictor problems when the plant is an ODE. The unbounded character of the input operator requires that the stability be characterized in terms of the H₁ (rather than the usual L₂) norm of the actuator state. The analysis involves an interesting structure of interconnected PDEs, of parabolic and first-order hyperbolic types, where the feedback gain kernel for the undelayed problem becomes an initial condition in a PDE arising in the compensator design for the problem with input delay. Space and time variables swap their roles in an interesting manner throughout the analysis.     

Stochastic nonlinear stabilization - I: A backstepping design

While the current robust nonlinear control toolbox includes a number of methods for systems affine in deterministic bounded disturbances, the problem when the disturbance is unbounded stochastic noise has hardly been considered. We present a control design which achieves global asymptotic (Lyapunov) stability in probability for a class of strict-feedback nonlinear continuous-time systems driven by white noise. In a companion paper, we develop inverse optimal control laws for general stochastic systems affine in the noise input, and for strict-feedback systems. A reader of this paper needs no prior familiarity with techniques of stochastic control.     

A flexible cluster-oriented alternative clustering algorithm for choosing from the Pareto front of solutions

Supervised alternative clustering is the problem of finding a set of clusterings which are of high quality and different from a given negative clustering. The task is therefore a clear multi-objective optimization problem. Optimizing two conflicting objectives at the same time requires dealing with trade-offs. Most approaches in the literature optimize these objectives sequentially (one objective after another one) or indirectly (by some heuristic combination of the objectives). Solving a multi-objective optimization problem in these ways can result in solutions which are dominated, and not Pareto-optimal. We develop a direct algorithm, called COGNAC, which fully acknowledges the multiple objectives, optimizes them directly and simultaneously, and produces solutions approximating the Pareto front. COGNAC performs the recombination operator at the cluster level instead of at the object level, as in the traditional genetic algorithms. It can accept arbitrary clustering quality and dissimilarity objectives and provides solutions dominating those obtained by other state-of-the-art algorithms. Based on COGNAC, we propose another algorithm called SGAC for the sequential generation of alternative clusterings where each newly found alternative clustering is guaranteed to be different from all previous ones. The experimental results on widely used benchmarks demonstrate the advantages of our approach.

     

Structured coalgebras and minimal HD-automata for the -calculus

The coalgebraic framework developed for the classical process algebras, and in particular its advantages concerning minimal realizations, does not fully apply to the π-calculus, due to the constraints on the freshly generated names that appear in the bisimulation.In this paper we propose to model the transition system of the π-calculus as a coalgebra on a category of name permutation algebras and to define its abstract semantics as the final coalgebra of such a category. We show that permutations are sufficient to represent in an explicit way fresh name generation, thus allowing for the definition of minimal realizations.We also link the coalgebraic semantics with a slightly improved version of history dependent (HD) automata, a model developed for verification purposes, where states have local names and transitions are decorated with names and name relations. HD-automata associated with agents with a bounded number of threads in their derivatives are finite and can be actually minimized. We show that the bisimulation relation in the coalgebraic context corresponds to the minimal HD-automaton.     

Renaming in synchronous message passing systems with Byzantine failures

We study the renaming problem in a fully connected synchronous network with Byzantine failures. We show that when the original namespace of the processors is unbounded, this problem cannot be solved in an a priori bounded number of rounds for , where n is the size of the network and t is the number of failures. On the other hand, for n > 3t, we present a Byzantine renaming algorithm that runs in O(lg n) rounds. In addition, we present a fast, efficient strong renaming algorithm for n > t, which runs in rounds, where N ₀ is the value of the highest identifier among all the correct processors.     

New results on stability and L∞‐gain analysis for positive linear differential‐algebraic equations with unbounded time‐varying delays

This article addresses the problems of stability and L_∞‐gain analysis for positive linear differential‐algebraic equations with unbounded time‐varying delays for the first time. First, we consider the stability problem of a class of positive linear differential‐algebraic equations with unbounded time‐varying delays. A new method, which is based on the upper bounding of the state vector by a decreasing function, is presented to analyze the stability of the system. Then, by investigating the monotonicity of state trajectory, the L_∞‐gain for differential‐algebraic systems with unbounded time‐varying delay is characterized. It is shown that the L_∞‐gain for differential‐algebraic systems with unbounded time‐varying delay is also independent of the delays and fully determined by the system matrices. Two numerical examples are given to illustrate the obtained results.     

Optimal control of systems with a unitary semigroup and with colocated control and observation

We solve the quadratic optimal control problem on an infinite time interval for a class of linear systems whose state space is a Hilbert space and whose operator semigroup is unitary. The difficulty is that the systems in this class, having unbounded control and observation operators, may be ill-posed. We show that there is a surprisingly simple solution to the problem (the optimal feedback turns out to be output feedback). Our approach is to use a change of variables which transforms the system into a one which, according to recent research, is known to be conservative. We show that, under a mild assumption, the transfer function of this conservative system is inner, and then it follows that the optimal control of this conservative system is trivial. We give an example with the wave equation on an n-dimensional domain, with Neumann control and Dirichlet observation of the velocity.     

Optimal regulators for linear systems with no control cost

This article is concerned with the theory of optimal feedback regulator for the linear system =Ax +Bu with the cost functional given byJ(u) = 1/2(Mx(T),x(T)). Due to absence of the usual positive definite quadratic cost for controls, this is a nonstandard problem.Two sets of results are presented: one for bounded and one for unbounded controls. For bounded controls, the control law is given by solving a system of coupled nonlinear differential equations of the Riccati type; and for unbounded controls, the optimal control law is determined by solving a parameterized family of matrix Riccati differential equations.     

Robust control and differential games on a finite time horizon

It is well known that theH control problem has a state space formulation in terms of differential games. For a finite time horizon control problem, the analogous differential game is considered. The disturbance is the control for the maximizing player. In order to allow forL ² disturbances, the controls for at least one player must be allowed to be unbounded. It is shown that the value of the game is the viscosity solution of the corresponding Isaacs equation under rather general conditions.     

Pattern-based abstraction for verifying secrecy in protocols

We present a method based on abstract interpretation for verifying secrecy properties of cryptographic protocols. Our method allows one to verify secrecy properties in a general model allowing an unbounded number of sessions, an unbounded number of principals, and an unbounded size of messages. As abstract domain we use sets of so-called super terms. Super terms are obtained by allowing an interpreted constructor, which we denote by Sup , where the meaning of a term Sup (t) is the set of terms that contain t as subterm. For these terms, we solve a generalized form of the unification problem and introduce a widening operator. We implemented a prototype and were able to verify well-known protocols such as, for instance, Needham–Schroeder–Lowe (0.03 s), Yahalom (12.67 s), Otway–Rees (0.01 s), and Kao–Chow (0.78 s).     

On the PID tracking control of robot manipulators

We consider the problem of PID tracking control of robotics manipulators. Our objective is to prove that under classical PID control, semiglobal stability can be assured with arbitrary small output tracking error. This means that, for any given set of initial conditions W_x, there exist PID control gains such that all trajectories starting in W_x converge to a residual set of arbitrary size. A novel PID control configuration is developed in terms of a parameter that is directly related with the size of the region of attraction and the size of the residual set. Tuning guidelines are extracted from the stability analysis.     

Capacitated Domination Problem

We consider a generalization of the well-known domination problem on graphs. The (soft) capacitated domination problem with demand constraints is to find a dominating set D of minimum cardinality satisfying both the capacity and demand constraints. The capacity constraint specifies that each vertex has a capacity that it can use to meet the demands of dominated vertices in its closed neighborhood, and the number of copies of each vertex allowed in D is unbounded. The demand constraint specifies the demand of each vertex in V to be met by the capacities of vertices in D dominating it. In this paper, we study the capacitated domination problem on trees from an algorithmic point of view. We present a linear time algorithm for the unsplittable demand model, and a pseudo-polynomial time algorithm for the splittable demand model. In addition, we show that the capacitated domination problem on trees with splittable demand constraints is NP-complete (even for its integer version) and provide a polynomial time approximation scheme (PTAS). We also give a primal-dual approximation algorithm for the weighted capacitated domination problem with splittable demand constraints on general graphs.     

A generalization of Nemhauser and Trotter?s local optimization theorem

The Nemhauser–Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We generalize Nemhauser and Trotter?s result to vertex deletion problems, introducing a novel algorithmic strategy based on purely combinatorial arguments (not referring to linear programming as the Nemhauser–Trotter result originally did). The essence of our strategy can be understood as a doubly iterative process of cutting away “easy parts” of the input instance, finally leaving a “hard core” whose size is (almost) linearly related to the cardinality of the solution set. We exhibit our approach using a generalization of Vertex Cover, called Bounded-Degree Vertex Deletion. For some fixed d?0, Bounded-Degree Vertex Deletion asks to delete at most k vertices from a graph in order to transform it into a graph with maximum vertex degree at most d. Vertex Cover is the special case of d=0. Our generalization of the Nemhauser–Trotter-Theorem implies that Bounded-Degree Vertex Deletion, parameterized by k, admits an O(k)-vertex problem kernel for d?1 and, for any ?>0, an O(k1+?)-vertex problem kernel for d?2. Finally, we provide a W[2]-completeness result for Bounded-Degree Vertex Deletion in case of unbounded d-values.     

Coding Mobile Synchronizing Petri Nets into Rewriting Logic

Mobile Synchronizing Petri Nets (MSPN's) are a model for mobility and coordination based on coloured Petri Nets, in which systems are composed of a collection of (possibly mobile) hardware devices and mobile agents, both modelled homogenously. In this paper we approach their verification, for which we have chosen to code MSPN's into rewriting logic. In order to obtain a representation of MSPN systems by means of a rewrite theory, we develop a class of them, that we call ν-Abstract Petri nets (ν-APN's), which are easily representable in that framework. Moreover, the obtained representation provides a local mechanism for fresh name generation. Then we prove that, even if ν-APN's are a particular class of MSPN systems, they are strong enough to capture the behaviour of any MSPN system. We have chosen Maude to implement ν-APN's, as well as the translation from MSPN's to ν-APN's, for which we make intensive use of its reflective features.     

A Universal Online Caching Algorithm Based on Pattern Matching

We present a universal algorithm for the classical online problem of caching or demand paging. We consider the caching problem when the page request sequence is drawn from an unknown probability distribution and the goal is to devise an efficient algorithm whose performance is close to the optimal online algorithm which has full knowledge of the underlying distribution. Most previous works have devised such algorithms for specific classes of distributions with the assumption that the algorithm has full knowledge of the source. In this paper, we present a universal and simple algorithm based on pattern matching for mixing sources (includes Markov sources). The expected performance of our algorithm is within 4+o(1) times the optimal online algorithm (which has full knowledge of the input model and can use unbounded resources).