14530470
Conformance testing in the presence of multiple faults
Conformance testing is the problem of determining if a black-box implementation I is equivalent to a specification S, where both are modeled as finite state Mealy machines. The problem involves constructing a checking sequence based on the specification, which is a sequence of inputs that detects all faulty machines. Traditionally conformance testing algorithms have assumed that the number of states in the implementation does not exceed that in the specification. This is because it is known that, in the absence of this assumption, the length of the checking sequence needs to be at least exponential in the number of extra states in the implementation [41]. However, this has limited the applicability of these techniques in practice where the implementation typically has many more states than the specification.In this paper we relax the constraints on the size of the implementation and investigate the existence of polynomial length checking sequences for implementations with extra states, under the promise that they either have multiple faults or no faults at all. We present randomized algorithms to construct checking sequences that catch faulty implementations with at most Δ extra states, having at least r faults (where Δ and r are parameters to the algorithm), and pass all correct implementations. We demonstrate the near optimality of our algorithms by presenting lower bounds for this problem. One of the main technical lemmas used in our proof is an estimate of the probability that a random walk on directed graphs will reach a large target set. We believe that this lemma will be of independent interest in the context of verifying safety properties.
16578484
On the Complexity of Error Explanation
When a system fails to satisfy its specification, the model checker produces an error trace (or counter-example) that demonstrates an undesirable behavior, which is then used in debugging the system. Error explanation is the task of discovering errors in the system or the reasons why the system exhibits the error trace. While there has been considerable recent interest in automating this task and developing tools based on different heuristics, there has been very little effort in characterizing the computational complexity of the problem of error explanation. 
 
In this paper, we study the complexity of two popular heuristics used in error explanation. The first approach tries to compute the smallest number of system changes that need to be made in order to ensure that the given counter-example is no longer exhibited, with the intuition being that these changes are the errors that need fixing. The second approach relies on the observation that differences between correct and faulty runs of a system shed considerable light on the sources of errors. In this approach, one tries to compute the correct trace of the system that is closest to the counter-example. We consider three commonly used abstractions to model programs and systems, namely, finite state Mealy machines, extended finite state machines and pushdown automata. We show that the first approach of trying to find the fewest program changes is NP-complete no matter which of the three formal models is used to represent the system. Moreover we show that no polynomial factor approximation algorithm for computing the smallest set of changes is possible, unless P = NP. For the second approach, we present a polynomial time algorithm that finds the closest correct trace, when the program is represented by a Mealy machine or a pushdown automata. When the program is represented by an extended finite state machine, the problem is once again NP-complete, and no polynomial factor approximation algorithm is likely.
7638167
Congruences for Visibly Pushdown Languages
We study congruences on words in order to characterize the class of visibly pushdown languages (Vpl), a subclass of context-free languages. For any language L, we define a natural congruence on words that resembles the syntactic congruence for regular languages, such that this congruence is of finite index if, and only if, L is a Vpl. We then study the problem of finding canonical minimal deterministic automata for Vpls. Though Vpls in general do not have unique minimal automata, we consider a subclass of VPAs called k-module single-entry VPAs that correspond to programs with recursive procedures without input parameters, and show that the class of well-matched Vpls do indeed have unique minimal k-module single-entry automata. We also give a polynomial time algorithm that minimizes such k-module single-entry VPAs.
18650185
Minimization, Learning, and Conformance Testing of Boolean Programs
Boolean programs with recursion are convenient abstractions of sequential imperative programs, and can be represented as recursive state machines (RSMs) or pushdown automata. Motivated by the special structure of RSMs, we define a notion of modular visibly pushdown automata (modular VPA) and show that for the class of languages accepted by such automata, unique minimal modular VPA exist. This yields an efficient approximate minimization theorem that minimizes RSMs to within a factor of k of the minimal RSM, where k is the maximum number of parameters in any module. Using the congruence defined for minimization, we show an active learning algorithm (with a minimally adequate teacher) for context free languages in terms of modular VPAs. We also present an algorithm that constructs complete test suites for Boolean program specifications. Finally, we apply our results on learning and test generation to perform model checking of black-box Boolean programs.
3094409
A method for modifying closed-loop motion plans to satisfy unpredictable dynamic constraints at runtime
The problem of motion planning in environments with both known static obstacles and unpredictable dynamic constraints is considered. A methodology is introduced in which the motion plan for the static environment is modified on-line to accommodate the unpredictable constraints in such a way that the completeness properties of the original motion plan are preserved. At the heart of the approach is the idea that navigation functions are indeed Lyapunov functions; and that the traditional method of forcing the robot to track the negative gradient of field is not the only input which stabilizes the system. This extra freedom in selecting the input is used to accommodate the dynamic constraints. A computational method for selecting the appropriate inputs is given. The method is used to solve two sample problems. The constraints in these cases are used to model collisions with other robots and, in the second example, a team of robots traveling information. Finally, some preliminary work on extending the approach to nonholonomic systems is presented.
42239647
Velocity control of mobile manipulators
When a serial-chain manipulator is mounted on a mobile base, the end-effector motion must be decomposed into the motion of the base and the motion of the manipulator. The determination of actuator rates for a given end-effector motion is typically underconstrained. By associating with each joint, a compliance function, local as well as global solutions for the inverse kinematics of kinematically redundant systems can be obtained. The rate decomposition problem is formulated using screw theory. Analytical expressions are obtained for the local solution for perfectly general systems, including those with nonholonomic constraints. Global integral solutions are also obtained using this framework. Nonholonomic systems require that additional constraints be imposed to remove the nonholonomy in the system. The basic goal of allocating the end-effector motion between the manipulator and its mobile base according to user-prescribed preferences is demonstrated using computer simulations and experiments.<<ETX>>
5480787
Parallel Formulations of Decision-Tree Classification Algorithms
Classification decision tree algorithms are used extensively for data mining in many domains such as retail target marketing, fraud detection, etc. Highly parallel algorithms for constructing classification decision trees are desirable for dealing with large data sets in reasonable amount of time. Algorithms for building classification decision trees have a natural concurrency, but are difficult to parallelize due to the inherent dynamic nature of the computation. In this paper, we present parallel formulations of classification decision tree learning algorithm based on induction. We describe two basic parallel formulations. One is based on Synchronous Tree Construction Approach and the other is based on Partitioned Tree Construction Approach. We discuss the advantages and disadvantages of using these methods and propose a hybrid method that employs the good features of these methods. We also provide the analysis of the cost of computation and communication of the proposed hybrid method. Moreover, experimental results on an IBM SP-2 demonstrate excellent speedups and scalability.
30844152
Multiple cooperating mobile manipulators
The main goal of the paper is to present a framework and basic control algorithms for coordinating a small team of robots in tasks that involve grasping large objects and transporting them in a two-dimensional environment with obstacles. Each robot consists of a mobile platform and an arm. Some arms are passive while others are active. Our previous work (1998) addressed the manipulator design, the architecture, and the communication between robots. In this paper we address the control of the manipulators, the coordination between the platforms for a team of two or three cooperating robots, and the handling of flexible large objects.
38254367
Parallel formulations of decision-tree classification algorithms
Classification decision tree algorithms are used extensively for data mining in many domains such as retail target marketing, fraud detection, etc. Highly parallel algorithms for constructing classification decision trees are desirable for dealing with large data sets in reasonable amount of time. Algorithms for building classification decision trees have a natural concurrency, but are difficult to parallelize due to the inherent dynamic nature of the computation. We present parallel formulations of classification decision tree learning algorithm based on induction. We describe two basic parallel formulations. One is based on Synchronous Tree Construction Approach and the other is based on Partitioned Tree Construction Approach. We discuss the advantages and disadvantages of using these methods and propose a hybrid method that employs the good features of these methods. Experimental results on an IBM SP-2 demonstrate excellent speedups and scalability.