The complexity of recursive constraint satisfaction problems

We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through finitely branching recursive trees or recursive binary trees. There are a large number of results in the literature on the complexity of the problem of finding an infinite path through a recursive tree. Our main result allows us to automatically transfer such results to give equivalent results about the complexity of the problem of finding a solution to a recursive constraint satisfaction problem.     

Building graph separators with the recursive rotation algorithm for the nested dissection method

A recursive rotation algorithm is built and investigated. The algorithm is a possible version of the nested dissection algorithm. The Liu algorithm builds a matrix graph separator by means of rotation of an elimination tree, which reduces the height of the latter. In this case, the nodes of the matrix graph are previously reordered by one of the well-known Cuthill-McKee algorithms, the reverse Cuthill-McKee algorithm, and the King algorithm. Then this procedure is recursively repeated. The recursive rotation algorithm is compared with the multilevel and spectral methods of graph separation for 2D finite-element grids.     

Models of Arithmetic and recursive functions

We investigate homomorphic images of the semiring of recursive functions as models of the Π₂ fragment of Arithmetic, and some relations between this fragment, its models and recursion theory.     

Canonical recursive functions and operations

A series of properties of canonical recursive functions and operations are established, allowing the possibility of extrapolating to these functions and operations the method proposed by R. L. Goodstein for constructing equational calculi.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 88, pp. 218–235, 1979.     

Discrete families of recursive functions and index sets

A number of discrete families of recursive functions are studied; exact upper bounds of index sets appearing in the construction are obtained.Translated fromAlgebra i Logika, Vol. 33, No. 2, pp. 147-165, March-April, 1994.     

A graph aided strategy to produce good recursive towers over finite fields

We propose a systematic method to produce potentially good recursive towers over finite fields. The graph point of view, so as some magma and sage computations are used in this process. We also establish some theoretical functional criterion ensuring the existence of many rational points on a recursive tower. Both points are illustrated by an example, from the production process, to the theoretical study.     

A stochastic framework for recursive computation of spline functions: Part II,smoothing splines

Many of the optimal curve-fitting problems arising in approximation theory have the same structure as certain estimation problems involving random processes. We develop this structural correspondence for the problem of smoothing inaccurate data with splines and show that the smoothing spline is a sample function of a certain linear least-squares estimate. Estimation techniques are then used to derive a recursive algorithm for spline smoothing.     

Real recursive functions and their hierarchy

In the last years, recursive functions over the reals (Theoret. Comput. Sci. 162 (1996) 23) have been considered, first as a model of analog computation, and second to obtain analog characterizations of classical computational complexity classes (Unconventional Models of Computation, UMC 2002, Lecture Notes in Computer Science, Vol. 2509, Springer, Berlin, pp. 1–14). However, one of the operators introduced in the seminal paper by Moore (1996), the minimalization operator, has not been considered: (a) although differential recursion (the analog counterpart of classical recurrence) is, in some extent, directly implementable in the General Purpose Analog Computer of Claude Shannon, analog minimalization is far from physical realizability, and (b) analog minimalization was borrowed from classical recursion theory and does not fit well the analytic realm of analog computation. In this paper, we show that a most natural operator captured from analysis—the operator of taking a limit—can be used properly to enhance the theory of recursion over the reals, providing good solutions to puzzling problems raised by the original model.     

Feasible Graphs and Colorings

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring.     

A recursive scheme for frequency estimation using the modulating functions method

In this paper, an application of modulating functions method for estimation of the frequency of noisy sinusoids, is proposed. The unknown frequency is updated by introducing a recursive algorithm which is independent by the choice of the modulating functions type. The proposed recursive estimation formula is able to take into account possible abrupt changes or sweep in the frequency of the sinusoidal signal. The goodness of the proposed method is verified through numerical simulations.     

Class of algebras of primitive recursive functions

In this paper Robinson's algebra is embedded in a countable class of algebras of primitive recursive functions. Each algebra of this class contains the operations of addition and composition of functions and also one of the operations i_a which are defined as follows: g(x)= i _a f(x) (a=0, 1, 2, ...) if g(x) satisfies the equations g(0)=a and g(x+1)=f[g(x)]. In this paper we study the properties possessed by all or almost all the algebras of this class.Translated from Matematicheskie Zametki, Vol. 14, No. 1, pp. 143–156, July, 1973.     

On Markovian decision programming with recursive reward functions

In this paper, the infinite horizon Markovian decision programming with recursive reward functions is discussed. We show that Bellman's optimal principle is applicable for our model. Then, a sufficient and necessary condition for a policy to be optimal is given. For the stationary case, an iteration algorithm for finding a stationary optimal policy is designed. The algorithm is a generalization of Howard's [7] and Iwamoto's [3] algorithms.This research was supported by the National Natural Science Foundation of China.     

Random recursive forests

A random recursive forest is defined as a union of random recursive trees. We find the expected number of trees in the uniform random recursive forest as well as the number of vertices of given degree, the maximum degree, the height of vertices, the order of branches, the root of the component containing a given vertex, and the last root of such forests. © 1994 John Wiley & Sons, Inc.     

K-moment problem for recursive sequences of order ∞: Application to the zeros of analytic functions

In this paper we solve the K-moment problem for a family of sequences defined by linear recursive relations of order ∞ indexed by Z. Extension of some known properties are studied and others results are established. Moreover, we paraphrase a fundamental application on the existence of zeros of an analytic function, in terms of the support of the representing measure of the former sequences.     

Efficient indexing methods for recursive decompositions of Bayesian networks

We consider efficient indexing methods for conditioning graphs, which are a form of recursive decomposition for Bayesian networks. We compare two well-known methods for indexing, a top-down method and a bottom-up method, and discuss the redundancy that each of these suffer from. We present a new method for indexing that combines the advantages of each model in order to reduce this redundancy. We also introduce the concept of an update manager, which is a node in the conditioning graph that controls when other nodes update their current index. Empirical evaluations over a suite of standard test networks show a considerable reduction both in the amount of indexing computation that takes place, and the overall runtime required by the query algorithm.     

Nonconvex variational problem with recursive integral functionals in Sobolev spaces: Existence and representation

The purpose of this paper is twofold. First, we present the existence theorem of an optimal trajectory in a nonconvex variational problem with recursive integral functionals by employing the norm-topology of a weighted Sobolev space. We show the continuity of the integral functional and the compactness of the set of admissible trajectories. Second, we show that a recursive integrand is represented by a normal integrand under the conditions guaranteeing the existence of optimal trajectories. We also demonstrate that if the recursive integrand satisfies the convexity conditions, then the normal integrand is a convex function. These results are achieved by the application of the representation theorem in Lp-spaces.     

Dynamical recursive algorithms for Lg-spline interpolation of EHB data

Lg-splines find application in many areas of mathematics, physics, and engineering. Especially in the last, there is need for recursive algorithms suitable for real-time application. In this paper we investigate a dynamical structure of the Hilbert space underlying the spline interpolation problem. We use these insights to develop a recursive algorithm for computing Lg-splines interpolating extended Hermite- Birkhoff data. We also investigate the relationship of our algorithm to a basic theorem due to Jerome and Schumaker regarding the smoothness properties of such splines and to algorithms based on their theorem.     

Endomorphisms of the group of all recursive permutations

We describe all endomorphisms of the group Aut_T ɛ of all recursive permutations. It is proved that the family of these endomorphisms is countable, and that they all are continuous and may be defined by some natural recursive operators. Orbits relative to the image of Aut_Tω prove to be recursive, and there exists a recursive model M such that this image is exactly its recursive automorphism group. There exists a universal endomorphism which contains, in a sense, all endomorphisms of that group. The universal endomorphism is unique with respect to some natural recursive equivalence. Supported by RFFR grant No. 093-01-01525. Translated fromAlgebra i Logika, Vol. 36, No. 1, pp. 54–76, January–February, 1997.     

A recursive quadratic programming algorithm that uses differentiable exact penalty functions

In this paper, a recursive quadratic programming algorithm for solving equality constrained optimization problems is proposed and studied. The line search functions used are approximations to Fletcher's differentiable exact penalty function. Global convergence and local superlinear convergence results are proved, and some numerical results are given.