10449411
Multistage Indexing Algorithms for Speeding Prolog Execution
In a previous article we proposed a new and efficient indexing technique that utilizes all the functors in the clause-heads and the goal. The salient feature of this technique is that the selected clause-head unifies (modulo nonlinearity)with the goal. As a consequence, our technique results in sharper discrimination, fewer choice points and reduced backtracking. A naı̈ve and direct implementation of our indexing algorithms considerably slowed down the execution speeds of a wide range of programs typically seen in practice. This is because it handled deep and shallow terms, terms with few indexable arguments, small and large procedures uniformly. To beneficially extend the applicability of our algorithms we need mechanisms that are ‘sensitive’ to term structures and size and complexity of procedures. We accomplish this in theν-ALS compiler by carefully decomposing our indexing process intomultiple stages . The operations performed by these stages increase in complexity ranging from first argument indexing to unification (modulo nonlinearity). Further the indexing process can be terminated at any stage if it is not beneficial to continue further. We have now completed the design and implementation of ν-ALS. Using it we have enhanced the performance of a broad range of programs typically encountered in practice. Our experience strongly suggests that indexing based on unification (modulo nonlinearity) is a viable idea in practice and that a broad spectrum of useful programs can realize all of its benefits.
5663050
Term Matching on Parallel Computers
Term matching is an important problem that arises very often in term rewriting and in functional and equational programming. We present a new parallel algorithm for the term-matching problem on the EREW (exclusive read, exclusive write) model of parallel computation. Our algorithm assumes a string representation of the two terms as its input. The string representation is first transformed into two labeled ordered trees, and term matching is then performed on these two trees. If n is the length of the input terms, then for any constant ϵ (0 < ϵ ≤ 1) our algorithm uses O(n1-ϵ) processors and takes O(nϵlogn) time. If ϵ = 0, the same algorithm will run in O(log2 n) time. The only other known parallel algorithm for this problem, due to Dwork, Kanellakis, and Stockmeyer, requires O(n2) processors and takes either O(logn) or O(log2n) time. However, their algorithm uses the stronger CREW (concurrent read, exclusive write) model of parallel computation and assumes a DAG (directed acyclic graph) representation of the two terms as its input. On the CRCW (concurrent read, concurrent write) model our algorithm requires n processors and O(log n) time.
10316561
Variable-depth trie index optimization: theory and experimental results
We develop an efficient approach to Trie index optimization. A Trie is a data structure used to index a file having a set of attributes as record identifiers. In the proposed methodology, a file is horizontally partitioned into subsets of records using a Trie index whose depth of indexing is allowed to vary. The retrieval of a record from the file proceeds by “stepping through” the index to identify a subset of records in the file in which a binary search is performed. This paper develops a taxonomy of optimization problems underlying variable-depth Trie index construction. All these problems are solvable in polynomial time, and their characteristics are studied. Exact algorithms and heuristics for their solution are presented. The algorithms are employed in CRES-an expert system for editing written narrative material, developed for the Department of the Navy. CRES uses several large-to-very-large dictionary files for which Trie indexes are constructed using these algorithms. Computational experience with CRES shows that search and retrieval using variable-depth Trie indexes can be as much as six times faster than pure binary search. The space requirements of the Tries are reasonable. The results show that the variable-depth Tries constructed according to the proposed algorithms are viable and efficient for indexing large-to-very-large files by attributes in practical applications.
42876448
Optimal Speedups for Parallel Pattern Matching in Trees
Tree pattern matching is a fundamental operation that is used in a number of programming tasks such as code optimization in compilers, symbolic computation, automatic theorem proving and term rewriting. An important special case of this operation is linear tree pattern matching in which an instance of any variable in the pattern occurs at most once. If n and m are the number of nodes in the subject and pattern tree respectively and if no restriction is placed on the structure of the trees, then the fastest known sequential algorithm for linear tree pattern matching requires O(nm) time in the worst case.
42187803
Incremental Techniques for Efficient Normalization of Nonlinear Rewrite Systems
In [8] we described a nonlinear pattern-matching algorithm with the best known worst-case and optimal average-case time complexity. In this paper we first report on some experiments conducted on our algorithm. Based on these experiments we believe that our algorithm is useful in speeding up normalization of nonlinear rewrite systems even when it has a small number (≥5) of rewrite rules.
16348991
Adaptive Pattern Matching
Pattern matching is an important operation used in many applications such as functional programming, rewriting, and rule-based expert systems. By preprocessing the patterns into a DFA-like automaton, we can rapidly select the matching pattern(s) in a single scan of the relevant portions of the input term. This automaton is typically based on left-to-right traversal of the patterns. By adapting the traversal order to suit the set of input patterns, it is possible to considerably reduce the space and matching time requirements of the automaton. The design of such adaptive automata is the focus of this paper. We first formalize the notion of an adaptive traversal. We then present several strategies for synthesizing adaptive traversal orders aimed at reducing space and matching time complexity. In the worst case, however, the space requirements can be exponential in the size of the patterns. We show this by establishing an exponential lower bounds on space that is independent of the traversal order used. We then discuss an orthogonal approach to space minimization based on direct construction of optimal dag automata. Finally, our work brings forth the impact of typing in pattern matching. In particular, we show that several important problems (e.g., lazy pattern matching in ML) are computationally hard in the presence of type disciplines, whereas they can be solved efficiently in the untyped setting.
5067407
An integrated framework for decision support in corporate planning
Abstract Corporate planning and decision making is a complex but critical management process in multidivisional organizations. This process entails a determination of the objectives and operational constraints at various levels of management. The decision-making function in such large diversified corporations proceeds by assessing the decision alternatives at each level of management with reference to their mutual tradeoffs, and arriving at an equilibrium point. In this paper, we develop a conceptual framework for the design of an integrated DSS in hierarchical organizations. The proposed framework consists of five steps: Analysis of the corporate decision making process, building a model of the decision making process, configuring a DSS for this model, pilot study and implementation. We illustrate the proposed design principles by considering a three-level hierarchical organization and modeling the decision-making process within this organization. A case analysis of the proposed integrated framework is provided. The case study has been conducted with decision makers in a simulated business environment. This research has given rise to several new avenues of exploration and extensions of the proposed design. We present the conclusions from this study and directions for future research in this area. Our experience with this approach in the case analysis has been quite positive, and this suggests that similar results may be obtained in real world organizations as well. We are currently testing the proposed approach with a local organization.
560868
An Optimal Algorithm for the Orienteering Tour Problem
Orienteering is a sport in which a competitor selects a path from a start to a destination, visiting control points along the path. Each control point has an associated score, and the travel between control points involves a certain cost. The problem is to select a set of control points to visit, so that the total score is maximized subject to a budget constraint on total cost. Several versions of this problem exist. In the version considered in this research, the start and the destination are the same, and the problem is to construct a subtour of the set of control points. The orienteering problem is a variant of the traveling salesman problem, and arises in vehicle routing and production scheduling situations. This problem has been shown to be NP-hard in the literature. We develop an optimal algorithm to solve this problem, using Lagrangean relaxation within a branch-and-bound framework. The Lagrangean relaxation is solved by a degree-constrained spanning tree procedure. Characteristics of the Lagrangea...
137267326
Thin Film Ferroelectric Materials and Devices
From the Publisher: 
Thin Film Ferroelectric Materials and Devices is a compilation of current research and development in two very important ferroelectric device technologies, namely ferroelectrics for Dynamic Random Access Memories (DRAM's) and Non-Volatile Ferroelectric Random Access Memories (NV-FRAM's). Given the rapid pace of development and the broad scope of the general topic of ferroelectric materials, readers will benefit from such a focused presentation. Thin Film Ferroelectric Materials and Devices will be of great value to materials and device scientists, device and process engineers, students, and postdoctoral associates. Furthermore, this compilation will serve as a concise introduction for new entrants to this exciting field.
316216
The Distribution Problem with Carrier Service: A Dual Based Penalty Approach
The distribution problem with carrier service is an important optimization problem that often arises in vehicle routing. The problem arises in the distribution of commodities from a central facility to a set of geographically distributed locations. Each location has a certain demand, the distribution vehicle has a load capacity, and the entire operation should be completed within a certain time. An outside carrier is available for direct service of locations from the central facility. The problem is to determine a feasible tour for the company vehicle and the locations to be served by the outside carrier such that the total cost of the operations is minimized. We model this problem and develop a solution technique using valid inequalities. A key feature of the solution approach is that it can easily be extended to solve similar problems with any type and number of side constraints as encountered in the current model. The algorithm has been extensively tested and computational results for problems having u...
13648716
EARS: An online bibliographic search and retrieval system based on ordered explosion
Abstract Ergonomics Abstracts Retrieval System (EARS) is an online bibliographic information search and retrieval system using the hierarchical subject classification of the Ergonomics Abstracts . EARS is designed using an inverted file organization and is implemented on CDC-Cyber. The data base of abstracts is organized using a fixed-length record format, where each logical record corresponds to a variable number of fixed-length physical records. Accordingly, an index for the identification of physical records from the logical records is used. The data base is inverted on a three-level hierarchical classification scheme and postings files are used for data base inversion. The data base is accessed after selectively traversing a 4-layer structure of indexes and postings files. EARS provides facilities to perform combinations of searches, limited searches, and certain editing functions. The system is currently used extensively by the Western New York Human Factors research community. The logical and physical designs of EARS, its interactive operational features, and its current expansions are described in this paper.