Optimal Deterministic Protocols for Mobile Robots on a Grid

This paper studies a system of m robots operating in a set of n work locations connected by aisles in a × grid, where m≤n. From time to time the robots need to move along the aisles, in order to visit disjoint sets of locations. The movement of the robots must comply with the following constraints: (1) no two robots can collide at a grid node or traverse a grid edge at the same time; (2) a robot's sensory capability is limited to detecting the presence of another robot at a neighboring node. We present a deterministic protocol that, for any small constant ε>0, allows m≤(1-ε)n robots to visit their target locations in O( ) time, where each robot visits no more than d≤n targets and no target is visited by more than one robot. We also prove a lower bound showing that our protocol is optimal. Prior to this paper, no optimal protocols were known for d>1. For d=1, optimal protocols were known only for m≤ , while for general m≤n only a suboptimal randomized protocol was known.     

Extracting models from clause sets saturated under semantic refinements of the resolution rule

We present an algorithm that—given a set of clauses S saturated under some semantic refinements of the resolution calculus—automatically constructs a Herbrand model of S. is represented by a set of atoms with equality and disequality constraints interpreted over the finite tree algebra, hence the problem of evaluating first-order formulae in is decidable.     

Combinatorial sharpness criterion and phase transition classification for random CSPs

We investigate the nature of the phase transition (sharp or coarse) for random constraint satisfaction problems. We first give a sharp threshold criterion specified for CSPs, which is derived from Friedgut–Bourgain’s one. Thus, we get a complete and precise classification of the nature of the threshold for symmetric Boolean CSPs. In particular we show that it is governed by two local properties strongly related to the problems and .     

A Resolution-based Model Building Algorithm for a Fragment of =: (Extended Abstract)

1 [11] is a decidable subclass of first-order clausal logic without equality. [7] shows that 1 becomes undecidable when equational literals are allowed, but remains decidable if equality is restricted to ground terms only.First, we extend this decidability result to some non ground equational literals. By carefully restricting the use of the equality predicate we obtain a new decidable class, called 1 ₌^*. We show that existing paramodulation calculi do not terminate on 1 ₌^* and we define a new simplification rule which allows to ensure termination. Second, we show that the automatic extraction of Herbrand models is possible from saturated sets in 1 ₌^* not containing □. These models are represented by certain finite sets of (possibly equational and non ground) linear atoms. The difficult point here is to show that this formalism is suitable as a model representation mechanism, i.e. that the evaluation of arbitrary non equational first-order formulae in such interpretations is a decidable problem.     

A family of maximal noncontrollable Lie wedges with empty interior

Let S_k be the semigroup of matrices in having nonnegative k-minors. Its Lie wedge generates and is noncontrollable. It is proved here that is a maximal noncontrollable Lie wedge if k=1, n−1 or when k and n are even. The latter is the family of Lie wedges mentioned in the title.     

The Solution Operator of the Korteweg-de Vries Equation is Computable

The initial value problem of the Korteweg-de Vries (KdV) equation posted on the real line R: defines a nonlinear map K from the space H^s( ) to the space C( , H^s( )) for any given real numbers s ≥ = 0. In this paper we prove that the map K_R is computable for any integer s ≥ = 3.     

Robustness analysis via the running time of the interior point methods

Let Σ be the set of stable linear time-invariant autonomous systems, equipped with a stability robustness measure ρ. Let be the measure of the computational efficiency of the algorithm that verifies the stability of the elements of Σ. We demonstrate the existence of a robustness measure ρ, algorithm , and a monotonically increasing function h, such that for all stable ,implications of this relationship are then discussed.     

Fuzzy output feedback control of nonlinear systems under sampled measurements

This paper studies the problem of designing an fuzzy feedback control for a class of nonlinear systems described by a continuous-time fuzzy system model under sampled output measurements. The premise variables of the fuzzy system model are allowed to be unavailable. We develop a technique for designing an fuzzy feedback control that guarantees the gain from an exogenous input to a controlled output is less than or equal to a prescribed value. A design algorithm for constructing the fuzzy feedback controller is given.     

Notes on the definition of behavioural controllability

We take another look at the behavioural definition of controllability for discrete one-dimensional (1D) systems, and its extension to multidimensional (nD) systems defined on or . We suggest that the current definition for nD systems is inappropriate for systems defined on the domain , and that care has to be taken even with the 1D definition. We propose a new definition which applies to all standard classes of discrete nD systems.     

Formative Processes with Applications to the Decision Problem in Set Theory: I. Powerset and Singleton Operators

This paper introduces formative processes, composed by transitive partitions. Given a family of sets, a formative process ending in the Venn partition Σ of is shown to exist. Sufficient criteria are also singled out for a transitive partition to model (via a function from set variables to unions of sets in the partition) all set-literals modeled by Σ. On the basis of such criteria a procedure is designed that mimics a given formative process by another where sets have finite rank bounded by C(|Σ|), with C a specific computable function. As a by-product, one of the core results on decidability in computable set theory is rediscovered, namely the one that regards the satisfiability of unquantified set-theoretic formulae involving Boolean operators, the singleton-former, and the powerset operator. The method described (which is able to exhibit a set-solution when the answer is affirmative) can be extended to solve the satisfiability problem for broader fragments of set theory.     

Design of optimal reduced order filters

This paper shows that the design of a reduced order optimal filter is equivalent to a frequency weighted norm model reduction problem.     

Lower Bounds for Dynamic Algebraic Problems

We consider dynamic evaluation of algebraic functions (matrix multiplication, determinant, convolution, Fourier transform, etc.) in the model of Reif and Tate; i.e., if f(x₁,…, x_n)=(y₁, …, y_m) is an algebraic problem, we consider serving online requests of the form “change input x_i to value v” or “what is the value of output y_i?” We present techniques for showing lower bounds on the worst case time complexity per operation for such problems. The first gives lower bounds in a wide range of rather powerful models (for instance, history dependent algebraic computation trees over any infinite subset of a field, the integer RAM, and the generalized real RAM model of Ben-Amram and Galil). Using this technique, we show optimal Ω(n) bounds for dynamic matrix–vector product, dynamic matrix multiplication, and dynamic discriminant and an Ω( ) lower bound for dynamic polynomial multiplication (convolution), providing a good match with Reif and Tate's O( ) upper bound. We also show linear lower bounds for dynamic determinant, matrix adjoint, and matrix inverse and an Ω( ) lower bound for the elementary symmetric functions. The second technique is the communication complexity technique of Miltersen, Nisan, Safra, and Wigderson which we apply to the setting of dynamic algebraic problems, obtaining similar lower bounds in the word RAM model. The third technique gives lower bounds in the weaker straight line program model. Using this technique, we show an Ω((log n)²/log log n) lower bound for dynamic discrete Fourier transform. Technical ingredients of our techniques are the incompressibility technique of Ben-Amram and Galil and the lower bound for depth-two superconcentrators of Radhakrishnan and Ta-Shma. The incompressibility technique is extended to arithmetic computation in arbitrary fields.     

Implementing Compositional Analysis Using Intersection Types With Expansion Variables

A program analysis is compositional when the analysis result for a particular program fragment is obtained solely from the results for its immediate subfragments via some composition operator. This means the subfragments can be analyzed independently in any order. Many commonly used program analysis techniques (in particular, most abstract interpretations and most uses of the Hindley/Milner type system) are not compositional and require the entire text of a program for sound and complete analysis.System is a recent type system for the pure λ-calculus with intersection types and the new technology of expansion variables. System supports compositional analysis because it has the principal typings property and an algorithm based on the new technology of β-unification has been developed that finds these principal typings. In addition, for each natural number k, typability in the rank-k restriction of System is decidable, so a complete and terminating analysis algorithm exists for the rank-k restriction.This paper presents new understanding that has been gained from working with multiple implementations of System and β-unification-based analysis algorithms. The previous literature on System presented the type system in a way that helped in proving its more important theoretical properties, but was not as easy to follow as it could be. This paper provides a presentation of many aspects of System that should be clearer as well as a discussion of important implementation issues.     

I — an interactive program for calibrating activated sludge systems

I — an interactive program for calibrating activated sludge systems is formulated and demonstrated. The model involves a heuristic screening algorithm for exploring the system equations structure, analytical computations of the sensitivities of the variables to the model coefficients, analytical computations of the gradients of the objective functions selected for the calibration process, and a gradient interactive steepest descent minimization scheme. The methodology was implemented in an end-user PC program: I , that uses the TK S ® and M ® as computational engines, and as the shell. Applications to the activated sludge system models of (Argaman Water Research 29(1) and Argaman et al. (Journal of Environmental Engineering ASCE 125(7) (1999), 608-617) are presented.     

On identification secret sharing schemes

Let be a set of participants sharing a secret from a set of secrets. A secret sharing scheme is a protocol such that any qualified subset of can determine the secret by pooling their shares, the messages which they receive, without error, whereas non-qualified subsets of cannot obtain any knowledge about the secret when they pool what they receive. In (optimal) schemes, the sizes of shared secrets depend on the sizes of shares given to the participants. Namely the former grow up exponentially as the latter increase exponentially. In this paper, instead of determining the secret, we require the qualified subsets of participants to identify the secret. This change would certainly make no difference from determining secret if no error for identification were allowed. So here we relax the requirement to identification such that an error may occur with a vanishing probability as the sizes of the secrets grow up. Under relaxed condition this changing allows us to share a set of secrets with double exponential size as the sizes of shares received by the participants exponentially grow. Thus much longer secret can be shared. On the other hand, by the continuity of Shannon entropy we have that the relaxation makes no difference for (ordinary) secret sharing schemes. We obtain the characterizations of relations of sizes of secrets and sizes of the shares for identification secret sharing schemes without and with public message. Our idea originates from Ahlswede–Dueck’s awarded work in 1989, where the identification codes via channels were introduced.     

Matrix-theoretic conditions for the realizability of sliding manifolds

Systems of the type , , where sgn(·) is the vector sign function, usually determine the realizability of sliding modes in control systems with high-frequency gain K. A new condition on K is established for the global stability of this system using a nonsmooth Liapunov function. This condition is used to establish necessary and sufficient stability conditions for second-order systems.     

Controllability of discrete-time control system on the symplectic group

Let x_n+1=exp(A+uB)x_n be a discrete-time control system on with A and B matrices in the symplectic Lie algebra . This paper gives sufficient conditions for the global controllability of the system. These conditions are similar to those of Martin (Math. Control Signal Systems 8 (1995) 279).     

Automatic verification of a manufacturing system

Due to increasing complexity and costs involved, powerful techniques are needed to analyse manufacturing systems. In order to improve these techniques, which are often based on simulation, our research focuses on application of formal methods to manufacturing systems. We translate a simulation model into a format suitable for model checking. The advantage of model checking, as opposed to simulation, is that we can prove liveness, eventually something good will happen, and safety, something bad will never happen, properties of manufacturing systems. We applied our approach to a model of a manufacturing system consisting of a turntable, a drill, and a testing device. The model was written in the χ language, which has been used extensively to simulate large manufacturing systems. We translated the model into , the input language of the popular model checker . After that, we used to verify that the model does not have deadlock and that it makes progress under all circumstances.     

Formulas relating stability estimates of discrete-time and sampled-data nonlinear systems

We provide an explicit stability or input-to-state stability (ISS) estimate for a sampled-data nonlinear system in terms of the estimate for the corresponding discrete-time system and a function describing inter-sample growth. It is quite obvious that a uniform inter-sample growth condition, plus an ISS property for the exact discrete-time model of a closed-loop system, implies uniform ISS of the sampled-data nonlinear system. Our results serve to quantify these facts by means of comparison functions. Our results can be used as an alternative to prove and extend results in [[Reference to 1]] or extend some results in [[Reference to 4]] to a class of nonlinear systems. Finally, the formulas we establish can be used as a tool for some other problems which we indicate.