Compiling general linear recursions by variable connection graph analysis

Compilation is a powerful preprocessing technique in the processing of recursions in knowledge-based systems. This paper develops a method of compiling and optimizing complex function-free linear recursions using a variable connection graph, the V-graph. It shows that a function-free recursion consisting of a linear recursive rule and one or more nonrecursive rules can be compiled to (1) a bounded recursion, in which recursion can be eliminated from the program, or (2) an n -chain recursion, whose compiled formula consists of one chain, when n = 1, or n synchronized compiled chains, when n > 1. The study is based on a classification of linear recursions and a study of the compilation results of each class. Using the variable connection graph, linear recursions are classified into six classes: acyclic paths, unit cycles, uniform cycles, nonuniform cycles, connected components, and their disjoint mixtures. Recursions in each class share some common properties in compilation. Our study presents an organized picture for the compilation of general function-free linear recursions. After compilation, the processing of complex linear recursions becomes essentially the processing of primitive n -chain recursions or bounded recursions to which efficient processing methods are available.     

Asynchronous chain recursions

The authors study the compilation and efficient processing of asynchronous chain recursions and show that many complex function-free recursions, which may contain single or multiple linear recursive rules, nonlinear recursive rules, mutually recursive rules, and multiple-level recursions, can be compiled to asynchronous chain recursions. The study on the compilation methods, the simplification of compiled formulas, and the query-processing techniques shows that asynchronous chain recursions can be compiled to relatively simple compiled formulas and processed efficiently using transitive closure query-processing methods     

On the completeness of naive memoing in Prolog

Memoing is often used in logic programming to avoid redundant evaluation of similar goals, often on programs that are inherently recursive in nature. The interaction between memoing and recursion, however, is quite complex. There are several top-down evaluation strategies for logic programs that utilize memoing to achieve completeness in the presence of recursion. This paper’s focus, however, is on the use ofnaive memoing in Prolog. Using memoingnaively in conjunction with recursion in Prolog may not produce expected results. For example, adding naive memoing to Prolog’s evaluation of a right-recursive transitive closure may be incomplete, whereas adding naive memoing to Prolog’s evaluation of a left-recursive transitive closure may be terminating and complete. This paper examines the completeness of naive memoing in linear-recursive, function-free logic programs evaluated with Prolog’s top-down evaluation strategy. In addition, we assume that the program is definite and safe, having finite base relations and exactly one recursive predicate. The goal of the paper is a theoretical study of the completeness of naive memoing and recursion in Prolog, illustrating the limitations imposed even for this simplified class of programs. The naive memoing approach utilized for this study is based on extension tables, which provide a memo mechanism with immediate update view semantics for Prolog programs, through a source transformation known as ET. We introduce the concept ofET-complete, which refers to the completeness of the evaluation of a query over a Prolog program that memos selected predicates through the ET transformation. We show that left-linear recursions defined by a single recursive rule are ET-complete. We generalize the class of left-linear recursions that are ET-complete by introducing pseudo-left-linear recursions, which are also defined by a single linear recursive rule. To add left-linear recursions defined bymultiple linear recursive rules to the class of ET-complete recursions, we present a left-factoring algorithm that converts left-linear recursions defined by multiple recusive rules into pseudo-left-linear recursions defined by a single recursive rule. Based on these results, the paper concludes by identifying research directions for expanding the class of Prolog programs to be examined in future work. This work was partially supported by the National Science Foundation under Grant CCR-9008737. Suzanne Wagner Dietrich, Ph.D.: She is an Associate Professor in the Department of Computer Science and Engineering at Arizona State University. Her research emphasis is on the evaluation of declarative logic programs especially in the context of deductive databases, including materialized view maintenance and condition monitoring in active deductive databases. More recently, her research interests include the integration of active, object-oriented and deductive databases as well as the application of this emerging database technology to various disciplines such as software engineering. She received the B. S. degree in computer science in 1983 from the State University of New York at Stony Brook, and as the recipient of an Office of Naval Research Graduate Fellowship, earned her Ph.D. degree in computer science at Stony Brook in 1987. Changguan Fan, M.S.: He is a Ph.D. candidate in the Department of Computer Science and Engineering at Arizona State University and a software engineer at the Regenisys Corporation in Scottsdale, AZ. His research interests include the evaluation of logic programs, deductive database systems and database management systems. He received his B.S. in Computer Science from the Shanghai Institute of Railway Technology, Shanghai, China in 1982 and his M.S. in the Department of Computer Science and Engineering at Arizona State University in 1989.     

Chain-split evaluation in deductive databases

Many popularly studied recursions in deductive databases can be compiled into one or a set of highly regular chain generating paths, each of which consists of one or a set of connected predicates. Previous studies on chain-based query evaluation in deductive databases take a chain generating path as an inseparable unit in the evaluation. However, some recursions, especially many functional recursions whose compiled chain consists of infinitely evaluable function(s), should be evaluated by chain-split evaluation, which splits a chain generating path into two portions in the evaluation: an immediately evaluable portion and a delayed-evaluation portion. The necessity of chain-split evaluation is examined from the points of view of both efficiency and finite evaluation, and three chain-split evaluation techniques: magic sets, buffered evaluation, and partial evaluation are developed. Our study shows that chain-split evaluation is a primitive recursive query evaluation technique for different kinds of recursions, and it can be implemented efficiently in deductive databases by extensions to the existing recursive query evaluation methods     

A simple characterization of uniform boundedness for a class of recursions

Detecting bounded recursions is a powerful optimization technique for recursive database query languages, as bounded recursions can be replaced by equivalent nonrecursive definitions. The problem is also of theoretical interest in that varying the class of recursions considered generates problem instances that vary from linearly decidable to NP-hard to undecidable. In this paper we review and clarify the existing definitions of boundedness. We then specify a class of recursions C such that membership in C guarantees that a certain simple condition is necessary and sufficient for boundedness. We use the notion of membership in C to unify and extend previous work on determining decidable classes of bounded recursions.     

Partial and Nested Recursive Function Definitions in Higher-order Logic

Based on inductive definitions, we develop a tool that automates the definition of partial recursive functions in higher-order logic (HOL) and provides appropriate proof rules for reasoning about them. Termination is modeled by an inductive domain predicate which follows the structure of the recursion. Since a partial induction rule is available immediately, partial correctness properties can be proved before termination is established. It turns out that this modularity also facilitates termination arguments for total functions, in particular for nested recursions. Our tool is implemented as a definitional package extending Isabelle/HOL. Various extensions provide convenience to the user: pattern matching, default values, tail recursion, mutual recursion and currying.     

Group recursive discriminant subspace learning with image set decomposition

Discriminant subspace learning is a widely used feature extraction technique for image recognition, since it can extract effective discriminant features by employing the class information and Fisher criterion. A crucial research topic on this technique is how to rapidly extract sufficient and effective features. Recently, recursive discriminant subspace learning technique has attracted lots of research interest because it can acquire sufficient discriminant features. Generally, it recursively decomposes image samples and extracts features from a number of decomposed sample sets. The major drawback of most recursive discriminant subspace learning methods is that they calculate the projective vectors one by one, such that they suffer from big computational costs. The recursive modified linear discriminant method and the incremental recursive Fisher linear discriminant method employ a simple solution for this problem, which calculates the class number minus one projective vectors in each recursion. However, this solution produces the unfavorable projective vectors with poor discriminant capabilities, and it cannot provide the terminating criterion for recursive computation and make the projective vectors orthogonal. In this paper, we propose a novel recursive learning approach that is group recursive discriminant subspace learning, which can rapidly learn multiple orthogonal subspaces with each spanned by a group of projective vectors. And we present a rule to select favorable projective vectors per recursion and provide a matrix-form-based terminating criterion to determine the number of recursions. Experiments on three widely used databases demonstrate the effectiveness and efficiency of the proposed approach.     

Mathematica在横向程序变换中的应用

本文讨论用Ｍａｔｈｅｍａｔｉｃａ的两大核心工作机制即模式匹配和规则来实现横向程序变换,以两类不同的递归程序变换的抽象模式为例,本文设计了相应的Ｍａｔｈｅｍａｔｉｃａ程序包将非尾递归的程序变换成为相应的尾递归形式,然后利用Ｍａｔｈｅｍａｔｉｃａ３．０提供的ＭａｔｈＬｉｎｋ机制,在ＶＢ５．０的环境下实现它们的应用。     

Making prolog more expressive

This paper introduces extended programs and extended goals for logic programming. A clause in an extended program can have an arbitrary first-order formula as its body. Similarly, an extended goal can have an arbitrary first-order formula as its body. The main results of the paper are the soundness of the negation as failure rule and SLDNF-resolution for extended programs and goals. We show how the increased expressibility of extended programs and goals can be easily implemented in any PROLOG system which has a sound implementation of the negation as failure rule. We also show how these ideas can be used to implement first-order logic as a query language in a deductive database system. An application to integrity constraints in deductive database systems is also given.     

Command algebras,recursion and program transformation

Dijkstra's language of guarded commands is extended with recursion and transformed into algebra. The semantics is expressed in terms of weakest preconditions and weakest liberal preconditions. Extreme fixed points are used to deal with recursion. Unbounded nondeterminacy is allowed. The algebraic setting enables us to develop efficient transformation rules for recursive procedures. The main result is an algebraic version of the rule of computational induction. In this version, certain parts of the programs are restricted to finite nondeterminacy. It is shown that without this restriction the rule would not be valid. Some applications of the rule are presented. In particular, we prove the correctness of an iterative stack implementation of a class of simple recursive procedures.     

Extension of cellular automata via the introduction of an algorithm for the recursive estimation of neighbors

This study focuses on an extended model of standard cellular automaton (CA), which includes an extra index, comprising a radius that defines a perception area for each cell in addition to the radius defined by the CA rule. Such an extension can be realized by introducing a recursive algorithm called the “Recursive Estimation of Neighbors.” The extended CA rules form a sequence ordered by this index, which includes the CA rule as its first term. This extension aims to construct a model that can be used within the CA framework to study the relation between information processing and pattern formation in collective systems. Even though the extension presented here is merely an extrapolation to a CA having a larger rule neighborhood identical to the perception area, the extra radius can be interpreted as an individual attribute of each cell. The novel perspective to CA provided here makes it possible to build heterogeneous CAs, which contain cells having different extra radii. Several pattern formations in the extension of one-dimensional elementary CAs and two-dimensional Life-like CAs are presented. It is expected that the extended model can be applied to various simulations of complex systems and in other fields.     

A study on the structure of linear recursion

We study a general class of single linear recursions and the properties of their expansions by analyzing the structures of the recursions. We show that the expansions of a linear recursion of this class are very regular in that the variable connections are heavily shared and change periodically with respect to the expansions. The variable connections can be precisely characterized as static bindings and chain connections. We conclude that a single linear recursion under our assumptions either is bounded or can be expressed as chain recursions. This study contributes to query processing, because it provides the basis for rule compilation as a general and powerful technique for query processing. Combined with query information, the expansion properties of the recursion provide optimized query-processing plans     

Evolving Recursive Programs by Using Adaptive Grammar Based Genetic Programming

Genetic programming (GP) extends traditional genetic algorithms to automatically induce computer programs. GP has been applied in a wide range of applications such as software re-engineering, electrical circuits synthesis, knowledge engineering, and data mining. One of the most important and challenging research areas in GP is the investigation of ways to successfully evolve recursive programs. A recursive program is one that calls itself either directly or indirectly through other programs. Because recursions lead to compact and general programs and provide a mechanism for reusing program code, they facilitate GP to solve larger and more complicated problems. Nevertheless, it is commonly agreed that the recursive program learning problem is very difficult for GP. In this paper, we propose techniques to tackle the difficulties in learning recursive programs. The techniques are incorporated into an adaptive Grammar Based Genetic Programming system (adaptive GBGP). A number of experiments have been performed to demonstrate that the system improves the effectiveness and efficiency in evolving recursive programs. Communicated by: William B. Langdon An erratum to this article is available at .     

Data mining in deductive databases using query flocks

Data mining can be defined as a process for finding trends and patterns in large data. An important technique for extracting useful information, such as regularities, from usually historical data, is called as association rule mining. Most research on data mining is concentrated on traditional relational data model. On the other hand, the query flocks technique, which extends the concept of association rule mining with a ‘generate-and-test’ model for different kind of patterns, can also be applied to deductive databases. In this paper, query flocks technique is extended with view definitions including recursive views. Although in our system query flock technique can be applied to a data base schema including both the intensional data base (IDB) or rules and the extensible data base (EDB) or tabled relations, we have designed an architecture to compile query flocks from datalog into SQL in order to be able to use commercially available data base management systems (DBMS) as an underlying engine of our system. However, since recursive datalog views (IDB's) cannot be converted directly into SQL statements, they are materialized before the final compilation operation. On this architecture, optimizations suitable for the extended query flocks are also introduced. Using the prototype system, which is developed on a commercial database environment, advantages of the new architecture together with the optimizations, are also presented.     

Recursive prediction error algorithms without a stability test

In this paper, recursive prediction error identification schemes are studied which incorporate Kalman gain calculations to ensure exponential stability of the predictor and related recursions. Thus there is an alternative to the trial and error projection techniques and stability test calculations of earlier schemes with no compromise on convergence rate or computational effort. The resulting algorithms are then attractive for a wide range of applications.     

Dynamic Programming via Static Incrementalization

Dynamic programming is an important algorithm design technique. It is used for problems whose solutions involve recursively solving subproblems that share subsubproblems. While a straightforward recursive program solves common subsubproblems repeatedly, a dynamic programming algorithm solves every subsubproblem just once, saves the result, and reuses it when the subsubproblem is encountered again. This can reduce the time complexity from exponential to polynomial. This paper describes a systematic method for transforming programs written as straightforward recursions into programs that use dynamic programming. The method extends the original program to cache all possibly computed values, incrementalizes the extended program with respect to an input increment to use and maintain all cached results, prunes out cached results that are not used in the incremental computation, and uses the resulting incremental program to form an optimized new program. Incrementalization statically exploits semantics of both control structures and data structures and maintains as invariants equalities characterizing cached results. It provides the basis of a general method for achieving drastic program speedups. Compared with previous methods that perform memoization or tabulation, the method based on incrementalization is more powerful and systematic. It has been implemented in a prototype system CACHET and applied to numerous problems and succeeded on all of them.     

Robust state estimation for uncertain discrete-time stochastic systems with missing measurements

In this paper, results of robust estimation of Zhou (2010a) are extended to state estimation with missing measurements. A new procedure is derived which inherits the main properties of that of Zhou (2010a). In this extension, a covariance matrix used in the recursions is replaced by its estimate which makes its asymptotic property investigation mathematically difficult. Though introducing a monotonic function and using the so-called squeeze rule, this new robust estimator is proved to converge to a stable system. Numerical simulation results indicate that the proposed estimator may have an estimation accuracy better than the estimator of Wang, Yang, Daniel, and Liu (2005).     

Deep auto-encoder observer multiple-model fast aircraft actuator fault diagnosis algorithm

In the extended multiple model adaptive estimation fault diagnosis algorithm, the extended Kalman filter has theoretical limitations, and the establishment of accurate aircraft mathematical model is almost impossible. Meanwhile, there is no automatic method to optimally select the node number of deep neural network hidden layer. In this paper, a deep auto-encoder observer multiple-model fault diagnosis algorithm for aircraft actuator fault is proposed. Based on the empirical formula of the basic auto-encoder hidden layer node number selection (three layered neural network), the recursive formula for deep auto-encoder hidden layer node number selection are proposed. The deep auto-encoder observers for no-fault and different actuator faults are trained to observe the system state. Combined with multiple model adaptive estimation, the deep auto-encoder observer overcomes the theoretical limitation of extended Kalman filter, and avoided the calculation of the nonlinear system Jacobian matrix. The simulation results show that hidden layer node number selection recursive formula is useful. The fault diagnosis algorithm is more efficient and has better performance compared to the standard methods.     

Functional combination

The algebraic functional operation of combination is introduced as a programming tool. It has a practical semantic interpretation in building functions which return several results, especially when such functions are directly recursive. Example functions are given whose invocations build multiple results from single recursions, including a new algorithm for batch-probing binary search trees from an unordered list of keys which returns an ordered list of hits.