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.
8380823
Term Matching on Parallel Computers
Term matching is an important problem that arises very often in term rewriting and in functional and equational programming. In this paper, 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<#x2208;≤1) our algorithm uses O(n1−∈) processors and takes O(nelog n) time. If e=0 the same algorithm will run in O(log2n) time. The only other known parallel algorithm for this problem is due to Dwork, Kanellakis and Stockmeyer that requires O(n2) processors and takes either O(log n) 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. The techniques used in our algorithm are novel and have wide applicability.
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.
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.
120676923
Preference Structure Representation Using Convex Cones in Multicriteria Integer Programming
A new efficient system of representing the decision-maker's preference structure in solving multicriteria integer programming problems is developed. The problem is solved by an interactive branch-and-bound method that employs the procedure of Zionts and Wallenius Zionts, S., J. Wallenius. 1983. An interactive multiple objective linear programming method for a class of underlying nonlinear utility functions. Management Sci.295. for multicriteria linear programming. The decision-maker's underlying utility function is assumed to be pseudoconcave, and his pairwise comparisons of decision alternatives are used to determine his preference structure in terms of certain convex cones in the objective function space and constraints on the weights on the objectives in the weight space. The two forms of preference structure representation are interrelated, and their underlying theory is developed. The primary objective of a representation scheme is exactness, and, in this respect, it is shown that the constraints on the weights are not adequate for representing nonlinear utility functions. On the other hand, the convex cones exactly represent any quasiconcave utility function and clearly avoid the approximations and inaccuracies in other utility assessment systems. Accordingly, an efficient ordered representation using convex cones is developed. An algorithmic framework for multicriteria integer programming that integrates the representation using convex cones with the branch-and-bound solution procedure is developed. Computational experience with bicriteria problems having up to 80 variables and 40 constraints is presented.
96844617
Template approaches to growth of oriented oxide heterostructures on SiO2/Si
A template approach to growing highly oriented ferroelectric oxide heterostructures on SiO2/Si substrates is presented. In this method, a thin “template” of a layered perovskite is used to induce the growth of the subsequent layers in the desired orientation. The efficacy of this “template” approach is illustrated through the example of growth of ferroelectric La-Sr-Co-0/Pb-Zr-Ti-O/La-Sr-Co-O heterostructures on SiO2Si. Discrete test capacitors fabricated from these heterostructures grown using the template approach exhibit remnant polarization values in the range of 10–15 μ C/cm2 and show very little degradation after 1011 bipolar fatigue cycles. In contrast, test capacitors fabricated without the template layer showed very little crystallographic texture and poor ferroelectric properties.
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.
62235624
An efficient approach to stochastic jobshop scheduling: algorithms and empirical investigations
Abstract Jobshop scheduling is one of the important classes of problems planning. The jobshop represents a common manufacturing environment, in which a set of machines is used to process a stream of jobs arriving randomly. The stochastic arrival pattern of the jobs, their processing sequences, and processing times render the scheduling of jobs a complex and difficult task. Furthermore, the scheduling task involves multiple conflicting objectives such as the minimization of the flow time, lateness and the number of late jobs among others. In this research,we develop a framework for the efficient scheduling of jobs considering these multiple objectives. The motivation for this research arises from the good performance of the interactive man-machine scheduling systems in achieving significant levels of attainment in the set of objectives, simultaneously. We develop scheduling strategies to the man-machine approach in this research. The algorithms developed in this research have been extensively tested and evaluated against the traditional scheduling methods using simulation studies. The results show that the proposed approach is efficient and viable for solving practical scheduling problems in the presence of multiple objectives.
5458806
Microcomputer based multiple criteria decision support system for strategic planning
Abstract There are two major approaches currently used for developing Decision support Systems (DSS) for strategic planning, especially in the objective formulation stage. Several mathematical models have been developed to abstract the decision situation. However, they do not take into account either behavioral aspects of decision making or the presence of multiple and conflicting objectives. A second approach is to consider the several qualitative factors that go into decision making; such considerations are normally situation-dependent and hence it is difficult to provide a system for general managerial situations. The Multiple Criteria Decision Making (MCDM) approach combines the advantages of both the approaches and, therefore, is an excellent alternative for designing DSS. This paper develops an MCDM approach to strategic planning. The model is applied to such a problem in a simulated environment and the problem is solved interactively. Our experience shows that the proposed methodology is a viable approach for solving practical decision problems in strategic planning.