Self-recovery micro-rollback synthesis (SMS) has currently become an important issue in high level synthesis. The problem of SMS combines the problem of functional unit scheduling and assignment with the problem of ch...
详细信息
Self-recovery micro-rollback synthesis (SMS) has currently become an important issue in high level synthesis. The problem of SMS combines the problem of functional unit scheduling and assignment with the problem of checkpoint insertion and microprogram optimization. It has been shown that these problems are NP-complete. The most studied problem is functional unit scheduling and assignment. Several heuristic techniques, including as soon as possible (ASAP), as last as possible (ALAP), integer programming, spring elasticity model, graph based mobility model, and genetic algorithm, are proposed. However, there are few studies on self-recovery micro-rollback synthesis and the technique of solution space searching by genetic algorithm has not been attempted. We study the feasibility of the genetic algorithm for the problem of SMS constrained on: the number of functional units, control steps, number of checkpoints, and the functional unit areas.
The paper presents a new approach for shape recovery based on integrating geometric and photometric information. We consider 3D objects which are symmetric with respect to a plane (e.g., faces) and their reconstructio...
详细信息
The paper presents a new approach for shape recovery based on integrating geometric and photometric information. We consider 3D objects which are symmetric with respect to a plane (e.g., faces) and their reconstruction from a single image. Both the viewpoint and the illumination are not necessarily frontal. In principle, no correspondence between symmetric points is required, but knowledge about a few corresponding pairs accelerates the process. The basic idea is that an image taken from a general, non-frontal viewpoint, under non-frontal illumination can be regarded as a pair of images of half of the object, taken from two different viewing positions and two different lighting directions. We show that integrating the photometric and geometric information yields the unknown lighting and viewing parameters, as well as dense correspondence between pairs of symmetric points. As a result, a dense shape recovery of the object is computed. The method has been implemented and tested experimentally on simulated and real data.
We provide rigorous time/space trade-offs for inverting any function. Given a function f, we give a time/space trade-off of TS2 = N3q(f), where q(f) is the probability that two random elements (taken with replacement)...
详细信息
We provide rigorous time/space trade-offs for inverting any function. Given a function f, we give a time/space trade-off of TS2 = N3q(f), where q(f) is the probability that two random elements (taken with replacement) are mapped to the same image under f. We also give a more general trade-off, T S3 = N3, that can invert any function at any point.
In a previous paper (1998) we presented a method for image-based navigation by which a robot can navigate to desired positions and orientations in 3D space specified by single images taken from these positions. In thi...
详细信息
In a previous paper (1998) we presented a method for image-based navigation by which a robot can navigate to desired positions and orientations in 3D space specified by single images taken from these positions. In this paper we further investigate the method and develop robust algorithms for navigation assuming the perspective projection model. In particular, we develop a tracking algorithm that exploits our knowledge of the motion performed by the robot at every step. This algorithm allows us to maintain correspondences between frames and eliminate false correspondences. We combine this tracking algorithm with an iterative optimization procedure to accurately recover the displacement of the robot from the target. Our method for navigation is attractive since it does not require a 3D model of the environment. We demonstrate the robustness of our method by applying it to a six degree of freedom robot arm.
We present a framework integrating specification and scheduler generation for real time systems. In a first step, the system, which can include arbitrarily designed tasks (cyclic or sporadic, with or without precedenc...
详细信息
We present a framework integrating specification and scheduler generation for real time systems. In a first step, the system, which can include arbitrarily designed tasks (cyclic or sporadic, with or without precedence constraints, any number of resources and CPUs) is specified as a timed Petri net. In a second step, our tool generates the most general non preemptive online scheduler for the specification, using a controller synthesis technique.
The complexity of testing nonemptiness of finite state automata on infinite trees is investigated. It is shown that for tree automata with the pairs (or complemented pairs) acceptance condition having m states and n p...
详细信息
The complexity of testing nonemptiness of finite state automata on infinite trees is investigated. It is shown that for tree automata with the pairs (or complemented pairs) acceptance condition having m states and n pairs, nonemptiness can be tested in deterministic time (mn)O(n);however, it is shown that the problem is in general NP-complete (or co-NP-complete, respectively). The new nonemptiness algorithm yields exponentially improved, essentially tight upper bounds for numerous important modal logics of programs, interpreted with the usual semantics over structures generated by binary relations. For example, it follows that satisfiability for the full branching time logic CTL* can be tested in deterministic double exponential time. Another consequence is that satisfiability for propositional dynamic logic (PDL) with a repetition construct (PDL-delta) and for the propositional Mu-calculus (Lμ) can be tested in deterministic single exponential time.
For certain fundamental problems in fault detection and identification, the necessary and sufficient conditions for their solvability are derived. These conditions are weaker than the ones found in the literature sinc...
详细信息
For certain fundamental problems in fault detection and identification, the necessary and sufficient conditions for their solvability are derived. These conditions are weaker than the ones found in the literature since we do not assume any particular structure for the residual generator.
Considers the problem of fault detection and isolation while using zero or almost zero threshold. A number of different fault detection and isolation problems using exact or almost exact disturbance decoupling are for...
详细信息
Considers the problem of fault detection and isolation while using zero or almost zero threshold. A number of different fault detection and isolation problems using exact or almost exact disturbance decoupling are formulated. Solvability conditions are given for the formulated design problems. The l-step delayed fault detection problem is also considered for discrete-time systems.
Motivated by applications in robotics, we formulate the problem of minimizing the total angle cost of a TSP tour for a set of points in Euclidean space, where the angle cost of a tour is the sum of the direction chang...
详细信息
Motivated by applications in robotics, we formulate the problem of minimizing the total angle cost of a TSP tour for a set of points in Euclidean space, where the angle cost of a tour is the sum of the direction changes at the points. We establish the NP-hardness of both this problem and its relaxation to the cycle cover problem. We then consider the issue of designing approximation algorithms for these problems and show that both problems can be approximated to within a ratio of O(log n) in polynomial time. We also consider the problem of simultaneously approximating both the angle and the length measure for a TSP tour. In studying the resulting tradeoff, we choose to focus on the sum of the two performance ratios and provide tight bounds on the sum. Finally, we consider the external value of the angle measure and obtain essentially tight bounds for it. In this paper we restrict our attention to the planar setting, but all our results are easily extended to higher dimensions.
Methods for the correct and efficient handling of annotations in a full-text retrieval system were investigated. The problem with annotations is that they cannot be treated as regular text, since this would disrupt pr...
Methods for the correct and efficient handling of annotations in a full-text retrieval system were investigated. The problem with annotations is that they cannot be treated as regular text, since this would disrupt proximity searches, but on the other hand, they cannot be ignored, as they may carry important information. Moreover, in some cases, a user may wish to restrict a search to prespecified subsets of annotations. We suggest a new way of processing the database to overcome the above dilemma.
暂无评论