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.     

Simulation Preorder over Simple Process Algebras

We consider the problem of simulation preorder/equivalence between infinite-state processes and finite-state ones. First, we describe a general method how to utilize the decidability of bisimulation problems to solve (certain instances of) the corresponding simulation problems. For certain process classes, the method allows us to design effective reductions of simulation problems to their bisimulation counterparts and some new decidability results for simulation have already been obtained in this way. Then we establish the decidability border for the problem of simulation preorder/equivalence between infinite-state processes and finite-state ones w.r.t. the hierarchy of process rewrite systems. In particular, we show that simulation preorder (in both directions) and simulation equivalence are decidable in EXPTIME between pushdown processes and finite-state ones. On the other hand, simulation preorder is undecidable between PA and finite-state processes in both directions. These results also hold for those PA and finite-state processes which are deterministic and normed, and thus immediately extend to trace preorder. Regularity (finiteness) w.r.t. simulation and trace equivalence is also shown to be undecidable for PA. Finally, we prove that simulation preorder (in both directions) and simulation equivalence are intractable between all classes of infinite-state systems (in the hierarchy of process rewrite systems) and finite-state ones. This result is obtained by showing that the problem whether a BPA (or BPP) process simulates a finite-state one is PSPACE-hard and the other direction is co -hard; consequently, simulation equivalence between BPA (or BPP) and finite-state processes is also co -hard.     

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.     

Rewrite-Based Decision Procedures

The rewrite-based approach to satisfiability modulo theories consists of using generic theorem-proving strategies for first-order logic with equality. If one can prove that an inference system generates finitely many clauses from the presentation of a theory and a finite set of ground unit clauses, then any fair strategy based on that system can be used as a -satisfiability procedure. In this paper, we introduce a set of sufficient conditions to generalize the entire framework of rewrite-based -satisfiability procedures to rewrite-based -decision procedures. These conditions, collectively termed subterm-inactivity, will allow us to obtain rewrite-based -decision procedures for several theories, namely those of equality with uninterpreted functions, arrays with or without extensionality and two of its extensions, finite sets with extensionality and recursive data structures.     

Lower Bounds for the Weak Pigeonhole Principle and Random Formulas beyond Resolution

We work with an extension of Resolution, called Res(2), that allows clauses with conjunctions of two literals. In this system there are rules to introduce and eliminate such conjunctions. We prove that the weak pigeonhole principle PHP^cn_n and random unsatisfiable CNF formulas require exponential-size proofs in this system. This is the strongest system beyond Resolution for which such lower bounds are known. As a consequence to the result about the weak pigeonhole principle, Res(log) is exponentially more powerful than Res(2). Also we prove that Resolution cannot polynomially simulate Res(2) and that Res(2) does not have feasible monotone interpolation solving an open problem posed by Krají ek.     

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 .     

Reduction Algorithms for Graphs of Small Treewidth

This paper presents a number of new ideas and results on graph reduction applied to graphs of bounded treewidth. S. Arnborg, B. Courcelle, A. Proskurowski, and D. Seese (J. Assoc. Comput. Mach.40, 1134–1164 (1993)) have shown that many decision problems on graphs can be solved in linear time on graphs of bounded treewidth, using a finite set of reduction rules. These algorithms can be used to solve problems on graphs of bounded treewidth without the need to obtain a tree decomposition of the input graph first. We show that the reduction method can be extended to solve the construction variants of many decision problems on graphs of bounded treewidth, including all problems definable in monadic second order logic. We also show that a variant of these reduction algorithms can be used to solve (constructive) optimization problems in O(n) time. For example, optimization and construction variants of I S and H C N can be solved in this way on graphs of small treewidth. Additionally, we show that the results of H. L. Bodlaender and T. Hagerup (SIAM J. Comput.27, 1725–1746 (1998)) can be applied to our reduction algorithms, which results in parallel reduction algorithms that use O(n) operations and O(log n log* n) time on an EREW PRAM, or O(log n) time on a CRCW PRAM.     

Fuzzy Distance Transform: Theory, Algorithms, and Applications

This paper describes the theory and algorithms of distance transform for fuzzy subsets, called fuzzy distance transform (FDT). The notion of fuzzy distance is formulated by first defining the length of a path on a fuzzy subset and then finding the infimum of the lengths of all paths between two points. The length of a path π in a fuzzy subset of the n-dimensional continuous space ⁿ is defined as the integral of fuzzy membership values along π. Generally, there are infinitely many paths between any two points in a fuzzy subset and it is shown that the shortest one may not exist. The fuzzy distance between two points is defined as the infimum of the lengths of all paths between them. It is demonstrated that, unlike in hard convex sets, the shortest path (when it exists) between two points in a fuzzy convex subset is not necessarily a straight line segment. For any positive number θ≤1, the θ-support of a fuzzy subset is the set of all points in ⁿ with membership values greater than or equal to θ. It is shown that, for any fuzzy subset, for any nonzero θ≤1, fuzzy distance is a metric for the interior of its θ-support. It is also shown that, for any smooth fuzzy subset, fuzzy distance is a metric for the interior of its 0-support (referred to as support). FDT is defined as a process on a fuzzy subset that assigns to a point its fuzzy distance from the complement of the support. The theoretical framework of FDT in continuous space is extended to digital cubic spaces and it is shown that for any fuzzy digital object, fuzzy distance is a metric for the support of the object. A dynamic programming-based algorithm is presented for computing FDT of a fuzzy digital object. It is shown that the algorithm terminates in a finite number of steps and when it does so, it correctly computes FDT. Several potential applications of fuzzy distance transform in medical imaging are presented. Among these are the quantification of blood vessels and trabecular bone thickness in the regime of limited special resolution where these objects become fuzzy.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

Full information and full control in a behavioral setting

In this paper, the concepts of Full Information and Full Control which arise in standard and control theory are extended to the behavioral framework. It is shown that the behavioral definitions are more fundamental than those given for the standard input/output case; in particular, the concept of state is not required and no a priori partition of the system variables into inputs and outputs needs to be performed. The interpretation of Full Information is to be able to reconstruct the error and disturbance variables from the control variables. The interpretation of Full Control is to be able to fully affect all the equations involving the error and the disturbance variables.