Bounded regular path queries in view-based data integration

In this paper we study the problem of deciding boundedness of (recursive) regular path queries over views in data integration systems, that is, whether a query can be re-expressed without recursion. This problem becomes challenging when the views contain recursion, thereby potentially making recursion in the query unnecessary. We define and solve two related problems of boundedness of regular path queries. One of the problems asks for the existence of a bound, and the other, more restricted one, asks if the query is bounded within a given parameter. For the more restricted version we show it PSPACE complete, and obtain a constructive method for optimizing the queries. For the existential version of boundedness, we show it PTIME reducible to the notorious problem of limitedness in distance automata. This problem has received a lot attention in the formal language community, but only exponential time algorithms are currently known.     

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.     

On the computation of invariant sets for constrained nonlinear systems: An interval arithmetic approach

This paper deals with the computation of control invariant sets for constrained nonlinear systems. The proposed approach is based on the computation of an inner approximation of the one step set, that is, the set of states that can be steered to a given target set by an admissible control action. Based on this procedure, control invariant sets can be computed by recursion.We present a method for the computation of the one-step set using interval arithmetic. The proposed specialized branch and bound algorithm provides an inner approximation with a given bound of the error; this makes it possible to achieve a trade off between accuracy of the computed set and computational burden. Furthermore an algorithm to approximate the one step set by an inner bounded polyhedron is also presented; this allows us to relax the complexity of the obtained set, and to make easier the recursion and storage of the sets.     

Bounded quantifications for iteration and concurrency in logic programming

The only means for repetition in most logic programming languages, including Prolog, is recursion. Definite iteration is introduced in logic programming languages through the bounded quantification construct. Firstly, it is claimed that this construct is often, though not always, more natural than recursion for expressing relations that involve repetition. In particular, programs involving arrays and similar data structures are significantly simplified. Secondly, it is argued that bounded quantifications should be efficiently implementable on sequential computers and have a high potential for running in parallel, particularly on computers supporting the SPMD model of computation. Bounded quantifications are compared with related constructs from other languages, including the definite loops of imperative languages and the array comprehensions of recent functional languages.     

Partial Evaluation of the Euclidean Algorithm, Revisited

The usual formulation of the Euclidean Algorithm is not well-suited to be specialized with respect to one of its arguments, at least when using offline partial evaluation. This has led Danvy and Goldberg to reformulate it using bounded recursion. In this article, we show how The Trick can be used to obtain a formulation of the Euclidean Algorithm with good binding-time separation. This formulation of the Euclidean Algorithm specializes effectively using standard offline partial evaluation.     

The unwind property for programs with bounded memory

For programs that can access unbounded memory (e.g., flowchart programs with recursion on simple variable parameters), the ‘unwind property’ is equivalent to the ‘truth-table property’. For programs restricted to bounded memory (e.g., flowchart programs with parameterless recursion), the two properties are not equivalent in general. We recapitulate all known results, give new results, and establish conditions under which the two properties are equivalent for program with bounded memory.     

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     

Simulation of simultaneous safe recursion over an arbitrary structure

In [O. Bournez, F. Cucker, P.J. de Naurois, J.Y. Marion, Computability over an arbitrary structure. Sequential and parallel polynomial time, in: Lecture Notes in Computer Science, vol. 2620, Springer, Berlin, 2003, pp. 185-199] the class of safe recursive functions over an arbitrary structure is defined. A question of simulation of the simultaneous safe recursion by single safe recursion was set. We prove that this simulation is feasible using bounded coding and decoding functions.     

Partial Evaluation of the Euclidian Algorithm

Some programs are easily amenable to partial evaluation because their control flow clearly depends on one of their parameters. Specializing such programs with respect to this parameter eliminates the associated interpretive overhead. Some other programs, however, do not exhibit this interpreter-like behavior. Each of them presents a challenge for partial evaluation. The Euclidian algorithm is one of them, and in this article, we make it amenable to partial evaluation.We observe that the number of iterations in the Euclidian algorithm is bounded by a number that can be computed given either of the two arguments. We thus rephrase this algorithm using bounded recursion. The resulting program is better suited for automatic unfolding and thus for partial evaluation. Its specialization is efficient.     

UnQL: a query language and algebra for semistructured data based on structural recursion

Abstract. This paper presents structural recursion as the basis of the syntax and semantics of query languages for semistructured data and XML. We describe a simple and powerful query language based on pattern matching and show that it can be expressed using structural recursion, which is introduced as a top-down, recursive function, similar to the way XSL is defined on XML trees. On cyclic data, structural recursion can be defined in two equivalent ways: as a recursive function which evaluates the data top-down and remembers all its calls to avoid infinite loops, or as a bulk evaluation which processes the entire data in parallel using only traditional relational algebra operators. The latter makes it possible for optimization techniques in relational queries to be applied to structural recursion. We show that the composition of two structural recursion queries can be expressed as a single such query, and this is used as the basis of an optimization method for mediator systems. Several other formal properties are established: structural recursion can be expressed in first-order logic extended with transitive closure; its data complexity is PTIME; and over relational data it is a conservative extension of the relational calculus. The underlying data model is based on value equality, formally defined with bisimulation. Structural recursion is shown to be invariant with respect to value equality. Received: July 9, 1999 / Accepted: December 24, 1999     

Recursion Schemata for Slowly Growing Depth Circuit Classes

We characterize iterated log depth circuit classes between AC⁰ and AC¹ by Cobham-like bounded recursion schemata. We also give alternative characterizations which utilize the safe recursion method developed by Bellantoni and Cook.     

Time-Varying Asymmetrical BLFs Based Adaptive Finite-Time Neural Control of Nonlinear Systems With Full State Constraints

This paper concentrates on asymmetric barrier Lyapunov functions (ABLFs) based on finite-time adaptive neural network (NN) control methods for a class of nonlinear strict feedback systems with time-varying full state constraints. During the process of backstepping recursion, the approximation properties of NNs are exploited to address the problem of unknown internal dynamics. The ABLFs are constructed to make sure that the time-varying asymmetrical full state constraints are always satisfied. According to the Lyapunov stability and finite-time stability theory, it is proven that all the signals in the closed-loop systems are uniformly ultimately bounded (UUB) and the system output is driven to track the desired signal as quickly as possible near the origin. In the meantime, in the scope of finite-time, all states are guaranteed to stay in the pre-given range. Finally, a simulation example is proposed to verify the feasibility of the developed finite time control algorithm.      

Hierarchies of recursive computations†

A recursive version of the Turing machine model is used to analyze the time and storage complexity of recursive algorithms. Hierarchy theorems are proven for time and for width of recursion (the amount of storage used at a level). A particular language is shown to be the “hardest” language to recognize without recursion. Previous results relating recursive and non-recursive time bounded computations are sharpened.     

Prespecifiable fixed‐time control for a class of uncertain nonlinear systems in strict‐feedback form

In this paper, we investigate the prespecifiable fixed‐time control problem for a class of uncertain nonlinear systems in strict‐feedback form, where the settling (convergence) time is not only bounded but also user‐assignable in advance. One of the salient features of the proposed method lies in the fact that it makes it possible to achieve any practically allowable settling time by using a simple and effective control parameter selection recipe. Both fixed‐time stabilization and fixed‐time tracking are considered for uncertain strict‐feedback systems. Firstly, by adding exponential state feedback and using fractional power integration as Lyapunov function candidate, a global stabilizing control strategy is developed. It is proved that all the system states converge to zero within prespecified fixed‐time with continuous and bounded control action. Secondly, under more general uncertain nonlinearities and external disturbances, an adaptive fixed‐time controller is derived such that the tracking error converges to a small neighborhood of zero within preassigned time. Theoretical results are also illustrated and supported by simulation studies.     

Event-triggered adaptive fuzzy control for nonstrict-feedback nonlinear systems with output hysteresis

This paper concentrates upon the issue of adaptive fuzzy tracing control for a class of nonstrict-feedback nonlinear systems output with hysteresis via an event-triggered strategy. To handle the difficulty caused by the nonstrict nonlinear systems, the variable separation technique is introduced. The design difficulty of output hysteresis is addressed by employing a hysteresis inverse function and Nussbaum function to compensate unmeasurable state signal. Meanwhile, the fuzzy logic system (FLS) is used to estimate the unknown function at each step of recursion. Moreover, by devising the relative threshold event-triggered mechanism (ETM), the frequency of actuators and controllers can be largely decreased. Thus, the adaptive fuzzy event-triggered tracing control strategy is proposed by combining the barrier Lyapunov function and backstepping technique. With the proposed scheme, it is theoretically demonstrated that all signals in the closed-loop system are bounded, and the tracing errors are driven to a small neighborhood of the origin under the output constraint. Eventually, two examples demonstrate the efficacy of the proposed control strategy.     

A heuristic Kalman filter for a class of nonlinear systems

One of the basic assumptions involved in the "optimality" of the Kalman filter theory is that the system under consideration must be linear. If the model is nonlinear, a linearization procedure is usually performed in deriving the filtering equations. This approach requires the nonlinear system dynamics to be differentiable. This note is an attempt to develop a heuristic Kalman filter for a class of nonlinear systems, with bounded first-order growth, that does not require the system dynamics to be differentiable. The proposed filter approximates the nonlinear state function by its state argument multiplied by a particular gain matrix only in the recursion of the estimation error covariance matrix. Under certain conditions, the error covariance remains bounded by bounds which can be precomputed from noise and system models, and the upper bound tends to zero when the state noise covariance tends to zero. A numerical example, with backlash nonlinearity, is also added.     

Reduced-order performance of adaptive control systems

Performance and stability behavior of discrete adaptive systems in the presence of fast parasitics are examined. When the parasitics are locally bounded, it is shown that sufficiently general input sequences yield a bounded response within a closed region. In the general case, it is established that a region of attraction exists from which all sequences converge to a target set which contains the equilibrium for exact adaptive tracking.     

递归与循环算法分析

程序设计中没有用到循环或递归算法,很难解决一些实际问题。本文以斐波那契(Fibonacci)数列为例对递归与循环算法的时间复杂度作了比较、分析。     

递归与循环算法分析

程序设计中没有用到循环或递归算法，很难解决一些实际问题。本文以斐波那契（Fibonacci）数列为例对递归与循环算法的时间复杂度作了比较、分析。