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.
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.
41350587
Automata-Driven Indexing of Prolog Clauses
Abstract Indexing Prolog clauses is an important optimization step that reduces the number of clauses on which unification will be performed and can avoid the pushing of a choice point. It is quite desirable to increase the number of functors used in indexing as this can considerably reduce the size of the filtered set. However, doing so can cause an enormous increase in code size and running time if indexing is done naively. This paper describes new and efficient indexing techniques that utilize all the functors in the clause heads and the goal. The salient feature of these techniques is that the selected clause head unifies (modulo nonlinearity) with the goal. In unification (modulo nonlinearity) all the variables in the terms being unified are assumed to be unique, so the only operation performed is of matching their constant portions. So use of our indexing techniques can result in sharper discrimination, fewer choice points, and reduced backtracking. These techniques have been incorporated into a Prolog compiler and using this compiler the run-time performance of a broad spectrum of Prolog programs has been improved.
100663548
La 0.5 Sr 0.5 CoO 3 electrode technology for Pb(Zr,Ti)O 3 thin film nonvolatile memories
Abstract Oxide electrode technology is investigated for optimization of Pb(Zr,Ti)O 3 (PZT) thin film capacitor properties for high density nonvolatile memory applications. PZT thin film capacitors with RF sputter deposited La 0.5 Sr 0.5 CoO 3 (LSCO) electrodes have been characterized with respect to the following parameters: initial dielectric hysteresis loop characteristics, fatigue performance, microstructure and imprint behavior. Our studies have determined that the fatigue of PZT capacitors with LSCO electrodes is less sensitive to B site cation ratio and underlying electrode stack technology than with RuO 2 electrodes. Doping PZT thin films with Nb (PNZT) improves imprint behavior of LSCO//PZT//LSCO capacitors considerably. We have demonstrated that PNZT 4/30/70 // LSCO capacitors thermally processed at either 550°C or 675°C have almost identical initial hysteresis properties and exhibit essentially no fatigue out to approximately 10 10 cycles.
6173091
Automata-driven indexing of Prolog clauses
Indexing Prolog clauses is an important optimization step that reduces the number of clauses on which unification will be performed and can avoid the pushing of a choice point. It is quite desirable to increase the number of functors used in indexing as this can considerably reduce the size of the filtered set. However this can cause an enormous increase in running time if indexing is done naively. This paper describes a new technique for indexing that utilizes all the functors in a clause-head. More importantly, in spite of using all the functors, this technique is still able to quickly select relevant clause-heads at run time. This is made possible primarily by a finite-state automaton that guides the indexing process. The automaton is constructed at compile time by preprocessing all the clause-heads.
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.
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.
35337405
A dynamic learning model for on-line quality control using the TAGUCHI approach
Abstract An important philosophy of quality control due to Taguchi rests on the belief that, once quality is designed into the product and the process, very little inspection is necessary. Taguchi evaluates quality in terms of costs incurred, including inspection and adjustment costs apart from quality loss. Using these costs, he determines an optimal interval for periodic inspection of products. At each inspection, the first item on the process line is checked for defects. If no defects are found, the process is assumed to be under control. On the other hand, if the first item turns out to be defective, the process is immediately stopped and adjusted. The underlying assumption here is that, once a defect is observed, it is construed that the process has drifted and all subsequent items are defective. This article challenges the underlying assumption by recognizing that the observation of one defective item does not necessarily imply that the process is out of control. Noisy signals may occur as a result ...
61774575
A simple method to test the stability of 2-D recursive digital filters of second order
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.
28568598
Cascade Graphs: Design, Analysis and Algorithms for Relational Joins
The focus of this work is on join optimization in relational database systems. The importance of join optimization is critically underscored by the high cost of relational joins and their frequent needs in traditional as well as emerging database applications. We demonstrate that the sequence in which the pages of the relations are accessed to process a join is a critical determinant of the join execution cost and an optimization of this sequence can lead to a significant improvement in performance over the traditional approaches. We initially develop three network structures to represent a join on two relations:page connectivity graph, cascade andblock tree cascade. A page connectivity graph is a bipartite representation of the set of connected pages in the two relations according to the join predicate. To reveal the structural properties of the join, the nodes of the bipartite graph are ordered into a set of levels, and the resulting isomorphic structure is termed acascade. From the cascade, a tree structure termed ablock tree cascade is derived by selectively grouping nodes at each level of the cascade intoblocks. We formulate the join as a tree traversal process, and accordingly develop efficient tree traversal algorithms. We develop a compact data structure to store the resulting access path, and provide a comprehensive analysis of the algorithms with detailed assessments of their performance. The performance evaluation demonstrates that the proposed approach can result in significant cost savings over the current join processing methods, for low to modest values of the join selectivity factor.