A theory of recursive dimension for ordered sets

The classical theorem of R. P. Dilworth asserts that a partially ordered set of width n can be partitioned into n chains. Dilworth's theorem plays a central role in the dimension theory of partially ordered sets since chain partitions can be used to provide embeddings of partially ordered sets in the Cartesian product of chains. In particular, the dimension of a partially-ordered set never exceeds its width. In this paper, we consider analogous problems in the setting of recursive combinatorics where it is required that the partially ordered set and any associated partition or embedding be described by recursive functions. We establish several theorems providing upper bounds on the recursive dimension of a partially ordered set in terms of its width. The proofs are highly combinatorial in nature and involve a detailed analysis of a 2-person game in which one person builds a partially ordered set one point at a time and the other builds the partition or embedding.This paper was prepared while the authors were supported, in part, by NSF grant ISP-80-11451. In addition, the second author received support under NSF grant MCS-80-01778 and the third author received support under NSF grant MCS-82-02172.     

A class of primitive substitutions and scrambled sets

Consider the subshifts induced by constant-length primitive substitutions on two symbols. By investigating the equivalent version for the existence of Li-Yorke scrambled sets and by proving the non-existence of Schweizer-Smítal scrambled sets, we completely reveal for this class of subshifts the chaotic behaviors possibly occurring in the sense of Li-Yorke and Schweizer-Smítal.     

A restricted computation model on Scott domains and its partial primitive recursive functionals

The paper builds on both a simply typed term system and a computation model on Scott domains via so-called parallel typed while programs (PTWP). The former provides a notion of partial primitive recursive functional on Scott domains supporting a suitable concept of parallelism. Computability on Scott domains seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (scvr) is not reducible to partial primitive recursion. So extensions and PTWP are studied that are closed under scvr. The twist are certain type 1 G?del recursors for simultaneous partial primitive recursion. Formally, denotes a function , however, is modelled such that is finite, or in other words, a partial sequence. As for PTWP, the concept of type writable variables is introduced, providing the possibility of creating and manipulating partial sequences. It is shown that the PTWP-computable functionals coincide with those definable in plus a constant for sequential minimisation. In particular, the functionals definable in denoted can be characterised by a subclass of PTWP-computable functionals denoted . Moreover, hierarchies of strictly increasing classes in the style of Heinermann and complexity classes are introduced such that . These results extend those for and PTWP [Nig94]. Finally, scvr is employed to define for each type the enumeration functional of all finite elements of . Received January 30, 1996     

Q 1-degrees of c.e. sets

We show that the Q-degree of a hyperhypersimple set includes an infinite collection of Q ₁-degrees linearly ordered under ${\leq_{Q_1}}$ with order type of the integers and consisting entirely of hyperhypersimple sets. Also, we prove that the c.e. Q ₁-degrees are not an upper semilattice. The main result of this paper is that the Q ₁-degree of a hemimaximal set contains only one c.e. 1-degree. Analogous results are valid for ${\Pi_1^0}$ s ₁-degrees.     

Relativized projecta and \beta-r.e. sets

I consider the projectum of a -r.e. set. It is shown that there are tame r.e. sets with small projecta and that there are tame r.e. sets with large projecta. Received: August 1, 1994     

Sharp thresholds for the phase transition between primitive recursive and Ackermannian Ramsey numbers

We compute the sharp thresholds on g at which g-large and g-regressive Ramsey numbers cease to be primitive recursive and become Ackermannian.We also identify the threshold below which g-regressive colorings have usual Ramsey numbers, that is, admit homogeneous, rather than just min-homogeneous sets.     

A probably fast,provably optimal algorithm for rectilinear Steiner trees

We use the technique of divide-and-conquer to construct a rectilinear Steiner minimal tree on a set of sites in the plane. A well-known optimal algorithm for this problem by Dreyfus and Wagner [10] is used to solve the problem in the base case. The run time of our optimal algorithm is probabilistic in nature: for all ? > 0, there exists b > 0 such that Prob[T(n) > 2^{b√n log n]>1–?, for n log n} > 1 – ?, for n sites uniformly distributed on a rectangle. The key fact in the run-time argument is the existence of probable bounds on the number of edges of an optimal tree crossing our subdivision lines. We can test these bounds in low-degree polynomial time for any given set of sites. © 1994 John Wiley & Sons, Inc.     

A recursive construction for Room designs

It is shown that if there is a Room design of sidev ₁ and a Room design of sidev ₂ containing a subdesign of sidev ₃, then there exists a design of side v₁ (v₂ — v₃)+v₃, provided thats = v ₂ — v₃ 6. Further, ifs 0, each of the 3 initial designs is isomorphic to a subdesign of the resultant design. It is also shown that there exist Room designs of sidev for all Fermat primesv > 65537.     

A programming technique for recursive procedures

A programming technique is described for ALGOL-like recursive procedures in which parameters and local variables are replaced by variables global to the recursive procedure and declared in a surrounding non-recursive procedure. The stack and time required for execution of a variety of recursive procedures has been determined in the languages ALGOL 60, CORAL 66 and ALGOL 68 both when programmed using this technique and when using parameters. Detailed results are presented for the Ackermann function and for tree manipulation.The global technique gives considerable savings in stack for all recursions investigated. For call-dominated recursions the technique speeds up the execution time in ALGOL 60 and CORAL 66 by about 25%. In ALGOL 68 the parameterless recursive procedure must be declared in the closed-clause which forms the particular-program rather than in a surrounding procedure in order to achieve a similar improvement in execution time.     

A recursive method for computing interpolants

In this paper, we describe a recursive method for computing interpolants defined in a space spanned by a finite number of continuous functions in R^d${\mathbb{R}}^d$. We apply this method to construct several interpolants such as spline interpolants, tensor product interpolants and multivariate polynomial interpolants. We also give a simple algorithm for solving a multivariate polynomial interpolation problem and constructing the minimal interpolation space for a given finite set of interpolation points.     

A foundation for real recursive function theory

The class of recursive functions over the reals, denoted by , was introduced by Cristopher Moore in his seminal paper written in 1995. Since then many subsequent investigations brought new results: the class was put in relation with the class of functions generated by the General Purpose Analogue Computer of Claude Shannon; classical digital computation was embedded in several ways into the new model of computation; restrictions of were proved to represent different classes of recursive functions, e.g., recursive, primitive recursive and elementary functions, and structures such as the Ritchie and the Grzergorczyk hierarchies.The class of real recursive functions was then stratified in a natural way, and and the analytic hierarchy were recently recognised as two faces of the same mathematical concept.In this new article, we bring a strong foundational support to the Real Recursive Function Theory, rooted in Mathematical Analysis, in a way that the reader can easily recognise both its intrinsic mathematical beauty and its extreme simplicity. The new paradigm is now robust and smooth enough to be taught. To achieve such a result some concepts had to change and some new results were added.     

Randomized rounding: A technique for provably good algorithms and algorithmic proofs

We study the relation between a class of 0–1 integer linear programs and their rational relaxations. We give a randomized algorithm for transforming an optimal solution of a relaxed problem into a provably good solution for the 0–1 problem. Our technique can be a of extended to provide bounds on the disparity between the rational and 0–1 optima for a given problem instance. This work was supported by Semiconductor Research Corporation grant SRC 82-11-008 and an IBM Doctoral Fellowship.     

A recursive algorithm for nonlinear least-squares problems

The solution of nonlinear least-squares problems is investigated. The asymptotic behavior is studied and conditions for convergence are derived. To deal with such problems in a recursive and efficient way, it is proposed an algorithm that is based on a modified extended Kalman filter (MEKF). The error of the MEKF algorithm is proved to be exponentially bounded. Batch and iterated versions of the algorithm are given, too. As an application, the algorithm is used to optimize the parameters in certain nonlinear input–output mappings. Simulation results on interpolation of real data and prediction of chaotic time series are shown. A. Alessandri and M. Cuneo were partially supported by the EU and the Regione Liguria through the Regional Programmes of Innovative Action (PRAI) of the European Regional Development Fund (ERDF). M. Sanguineti was partially supported by a grant from the PRIN project ‘New Techniques for the Identification and Adaptive Control of Industrial Systems’ of the Italian Ministry of University and Research.     

A recursive partitioning tool for interval prediction

The traditional approach to regression trees involves partitioning the space of predictor variables into subsets that optimise a function of the response variable(s), and then predicting future response values by a single-valued summary statistic in each subset. Our belief is that a prediction interval is of greater practical use than a predictive value, and that the criterion for the partitioning should be based on such intervals rather than on single values. We define four potential criteria in the case of a single response variable, discuss computational aspects of producing the partition, evaluate the criteria on both real and simulated data, and draw some tentative conclusions about their relative efficacies. The methodology is extended to the case of multiple response variables, and its viability is demonstrated by application to some further real data. The possibility of fitting distributions to within-subsets data is discussed, and some potential extensions are briefly outlined.