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.     

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.     

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 .     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

Towards Proof Planning for ω

This paper describes the proof planning system _ω⁺ for the meta theorem prover for LF implemented in Twelf. The main contributions include a formal system that approximates the flow of information between assumptions and goals within a meta proof, a set of inference rules to reason about those approximations, and a soundness proof that guarantees that the proof planner does not reject promising proof states. Proof planning in _ω⁺ is decidable.     

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.