This paper presents an overview of Pragma, an adaptive runtime infrastructure capable of reactively and proactively managing and optimizing application execution using current system and application state, predictive ...
Propositional satisfiability (SAT) is a fundamental problem of immense practical importance. While SAT is NP-complete when clauses can contain 3 literals or more, the problem can be solved in linear time when the give...
详细信息
ISBN:
(纸本)0909925828
Propositional satisfiability (SAT) is a fundamental problem of immense practical importance. While SAT is NP-complete when clauses can contain 3 literals or more, the problem can be solved in linear time when the given formula contains only binary clauses (2SAT). Many complete search algorithms for SAT solving have taken advantage of 2SAT information that occurs in the statement of the problem in order to simplify the solving process, only one that we are aware of uses 2SAT information that arises in the process of the search, as clauses are simplified. There are a number of possibilities for making use of 2SAT information to improve the SAT solving process: maintaining 2SAT satisfiability during search, detecting unit consequences of the 2SAT clauses, and Krom subsumption using 2SAT clauses. In this paper we investigate the tradeoffs of increasing complex 2SAT handling versus the search space reduction and execution time. We give experimental results illustrating that the SAT solver resulting from the best tradeoff is competitive with state of the art Davis-Putnam methods, on hard problems involving a substantial 2SAT component.
Applications of the Hough Transform (HT) have been limited to small-size images for a long time. For large-size images, peak detection and line verification become much more time-consuming. Many HT-based line detectio...
详细信息
Recognizing graphic objects from binary images is an important task in many real-life applications. Generally, there are two ways to do the graphics recognition: onestep methods and two-step methods. The former recogn...
详细信息
Recognizing graphic objects from binary images is an important task in many real-life applications. Generally, there are two ways to do the graphics recognition: one-step methods and two-step methods. The former recog...
详细信息
A previously unknown form of compromising emanations has been discovered. LED status indicators on data communication equipment, under certain conditions, are shown to carry a modulated optical signal that is signific...
详细信息
Modern enterprises are irreversibly dependent on large-scale, adaptive, component-based information systems whose complexity frequently exceeds current engineering capabilities for intellectual control, resulting in p...
详细信息
Process improvement studies have tended to focus on software process improvement (SPI) framework such as the generic „best practices" models (e.g., CMM and SPICE), SPI Models (e.g., PDCA and IDEAL), and Quality I...
详细信息
It is common in client/server architectures for components to have SQL statements embedded in their source code. Components submit queries to relational databases using such standards as Universal Data Access (UDA) an...
详细信息
It is common in client/server architectures for components to have SQL statements embedded in their source code. Components submit queries to relational databases using such standards as Universal Data Access (UDA) and Open Database Connectivity (ODBC). The API that implements these standards is complex and requires the embedding of SQL statements in the language that is used to write the components. Such programming practices are widespread and result in increased complexity in maintaining systems. We propose an approach that eliminates the embedding of SQL in programming languages, thereby enabling the automation of important software maintenance tasks.
Formal methods, especially model checking, are an indispensable part of the softwareengineering process. With large software systems currently beyond the range of fully automatic verification, however, a combination ...
详细信息
Formal methods, especially model checking, are an indispensable part of the softwareengineering process. With large software systems currently beyond the range of fully automatic verification, however, a combination of decomposition and abstraction techniques is needed. To model check components of a system, a standard approach is to close the component with an abstraction of its environment. To make it useful in practice, the closing of the component should be automatic, both for data and for control abstraction. Specifically for model checking asynchronous open systems, external input queues should be removed, as they are a potential source of a combinatorial state explosion. In this paper we close a component synchronously by embedding the external environment directly into the system to avoid the external queues, while for the data, we use a two-valued abstraction, namely data influenced from the outside or not. This gives a more precise analysis than that investigated by Ioustinova et al. (2002). To further combat the state explosion problem, we combine this data abstraction with a static analysis to remove superfluous code fragments. The static analysis we use is reminiscent of that presented by Ioustinova et al., but we use a combination of a may and a must-analysis instead of a may-analysis.
暂无评论