A jump inversion theorem for the semilattices of sigma-degrees

We prove an analogue of the jump inversion theorem for the semilattices of Σ-degrees of structures. As a corollary, we get a similar result for the semilattices of degrees of presentability of countable structures.     

Badness and jump inversion in the enumeration degrees

This paper continues the investigation into the relationship between good approximations and jump inversion initiated by Griffith. Firstly it is shown that there is a ${\Pi^{0}_{2}}$ set A whose enumeration degree a is bad—i.e. such that no set ${X \in a}$ is good approximable—and whose complement ${\overline{A}}$ has lowest possible jump, in other words is low₂. This also ensures that the degrees y ≤ a only contain ${\Delta^{0}_{3}}$ sets and thus yields a tight lower bound for the complexity of both a set of bad enumeration degree, and of its complement, in terms of the high/low jump hierarchy. Extending the author’s previous characterisation of the double jump of good approximable sets, the triple jump of a ${\Sigma^{0}_{2}}$ set A is characterised in terms of the index set of coinfinite sets enumeration reducible to A. The paper concludes by using Griffith’s jump interpolation technique to show that there exists a high quasiminimal ${\Delta^{0}_{2}}$ enumeration degree.     

Limit lemmas and jump inversion in the enumeration degrees

We show that there is a limit lemma for enumeration reducibility to 0_e', analogous to the Shoenfield Limit Lemma in the Turing degrees, which relativises for total enumeration degrees. Using this and `good approximations' we prove a jump inversion result: for any set W with a good approximation and any set X<_eW such that W_eX' there is a set A such that X_eA<_eW and A'=W'. (All jumps are enumeration degree jumps.) The degrees of sets with good approximations include the ⁰₂ degrees and the n-CEA degrees. The results in this paper form part of the author's doctoral dissertation written under the supervision of Prof. Steffen Lempp at the University of Wisconsin Madison. The author is grateful to an anonymous referee for helpful comments and suggestions.     

Density of the cototal enumeration degrees

We prove that the cototal enumeration degrees are exactly the enumeration degrees of sets with good approximations, as introduced by Lachlan and Shore [17]. Good approximations have been used as a tool to prove density results in the enumerations degrees, and indeed, we prove that the cototal enumerations degrees are dense.     

A non-splitting theorem in the enumeration degrees

We complete a study of the splitting/non-splitting properties of the enumeration degrees below by proving an analog of Harrington’s non-splitting theorem for the enumeration degrees. We show how non-splitting techniques known from the study of the c.e. Turing degrees can be adapted to the enumeration degrees.     

A splitting theorem for degrees

We prove that, for any , and with _{T}A\oplus U$"> and r.e., in , there are pairs and such that ; ; and, for any and from and any set , if and , then . We then deduce that for any degrees , , and such that and are recursive in , , and is into , can be split over avoiding . This shows that the Main Theorem of Cooper (Bull. Amer. Math. Soc. 23 (1990), 151-158) is false.

     

A non-inversion theorem for the jump operator

R.W. Robinson's [15] interpolation theorem shows that the Sacks [16] jump inversion theorem can be extended to invert the jump and preserve order on any finite linearly ordered set of degrees r.e. in and above (REA in) 0′. We show that although the Friedberg inversion theorem can be extended to partial orders, the Sacks theorem cannot be extended to even the simplest ones even if we allow the inversion to carry us into rather than just the r.e. degrees. This strong non-inversion theorem also decides the problem that Lerman [12] has called the main obstacle to deciding the theory of the degrees with jump. It is a corollary to our main result:

Theorem 1.1. There are a₀ and a₁ REA in 0′ such that a₀ a₁<0” and if u<0′, then not both a₀ and a₁ are r.e. in u.

Other corollaries include a solution to a problem suggested by Jockusch and Soare: not every a REA in 0′ is the jump of a degree which is half of an r.e. minimal pair. The proof introduces a new type of 0 priority argument in which the tree of strategies is ω+1 branching and so simply determining the true path requires a 0 oracle.     

On Nondeterminism,Enumeration Reducibility and Polynomial Bounds

Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e-reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non-deterministic polynomial time reducibility. We define the polynomial time e-degrees as the equivalence classes under this reducibility and investigate their structure on the recursive sets, showing in particular that the pe-degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy.     

A structure theorem for dismantlable lattices and enumeration

The concept of `adjunct' operation of two lattices with respect to a pair of elements is introduced. A structure theorem namely, `A finite lattice is dismantlable if and only if it is an adjunct of chains' is obtained. Further it is established that for any adjunct representation of a dismantlable lattice the number of chains as well as the number of times a pair of elements occurs remains the same. If a dismantlable lattice L has n elements and n+k edges then it is proved that the number of irreducible elements of L lies between n-2k-2 and n-2. These results are used to enumerate the class of lattices with exactly two reducible elements, the class of lattices with n elements and upto n+1 edges, and their subclasses of distributive lattices and modular lattices. This revised version was published online in June 2006 with corrections to the Cover Date.     

An improved partial enumeration algorithm for integer programming problems

In this paper, we present an improved Partial Enumeration Algorithm for Integer Programming Problems by developing a special algorithm, named PE_SPEEDUP (partial enumeration speedup), to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many integer programming problems, including knapsack problems, reliability optimization, and spare allocation problems. The algorithm is based on monotonicity properties of the problem functions, and uses function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed PE_SPEEDUP algorithm has been demonstrated on some integer optimization problems taken from the literature.     

ECO:a methodology for the enumeration of combinatorial objects

In this Paper, we illustrate a method (called the ECO method) for enumerating some classes of combinatorial objects. The basic idea of this method is the following: by means of an operator that performs a "local expansion" on the objects, we give some recursive constructions of these classes. We use these constructions to deduce some new funtional equations verified by classes' generating functions. By solving the functional equations, we enumerate the combinatorial objects according to various parameters. We show some applications of the method referring to some classical combinatorial objects, such as: trees, paths, polyminoes and permutations     

A partial enumeration algorithm for pure nonlinear integer programming

In this paper, a partial enumeration algorithm is developed for a class of pure IP problems. Then, a computational algorithm, named PE_SPEEDUP (partial enumeration speedup), has been developed to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many pure IP problems, including knapsack problems, reliability optimization, and spare allocation problems. The algorithm is based on monotonicity properties of the problem functions, and uses function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed algorithm and the PE_SPEEDUP algorithm has been demonstrated on some integer optimization problems taken from the literature.     

A join theorem for the computably enumerable degrees

It is shown that for any computably enumerable (c.e.) degree , if , then there is a c.e. degree such that (so is lowand is high). It follows from this and previous work of P. Cholak, M. Groszek and T. Slaman that the low and low c.e. degrees are not elementarily equivalent as partial orderings.

     

A differential game with jump process observations

We introduce a stochastic differential game with jump process observations. Both players obtain common, noisy information of the state of the system only at random time instants. The solutions to this game and its continuous observations in noise counterpart are obtained. Some earlier results dealing with the effect of changes in system parameters on the optimal cost for the continuous observations case are extended to the game with jump process observations.This work was supported by a 1978 Summer Faculty Fellowship from the University of Maryland, Baltimore County.     

Dynamic compensator design and H∞ admissibilization for delayed singular jump systems via Moore–Penrose generalized inversion technique

This paper is intended to study output feedback-based $H_{\infty }$ admissibilization for singular Markovian jump time-varying delays systems via Moore–Penrose generalized inversion technique. The main aim is to design singular dynamic compensator based on output feedback control idea and Moore–Penrose generalized inversion technique, such that the time-varying delays singular Markovian jump system realizes not only stochastic stability, but also regularity, impulse-freeness (which are collectively known as stochastic admissibility) and achieves $H_{\infty }$ interference level. Time delay-dependent and mode-dependent L–K candidate functional is constructed, Moore–Penrose generalized inversion technique is utilized, then the improved $H_{\infty }$ admissibilization conditions for singular Markovian jump time-varying delays systems are provided by virtue of linear matrix inequalities. Simulation examples including a direct current motor-controlled inverted pendulum system are employed to confirm the effectiveness and practicability of the addressed singular dynamic compensation technique.     

A converse to Dye's theorem

Every non-amenable countable group induces orbit inequivalent ergodic equivalence relations on standard Borel probability spaces. Not every free, ergodic, measure preserving action of on a standard Borel probability space is orbit equivalent to an action of a countable group on an inverse limit of finite spaces. There is a treeable non-hyperfinite Borel equivalence relation which is not universal for treeable in the ordering.

     

A generalization of the Fujisawa-Kuh global inversion theorem

We discuss the problem of global invertibility of nonlinear maps defined on the finite dimensional Euclidean space via differential tests. We provide a generalization of the Fujisawa-Kuh global inversion theorem and introduce a generalized ratio condition which detects when the pre-image of a certain class of linear manifolds is non-empty and connected. In particular, we provide conditions that also detect global injectivity.     

Asymptotic enumeration theorems for the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs

The asymptotic properties of the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs are studied. Let be a directed circulant graph. Let and be the numbers of spanning trees and of Eulerian trails, respectively. Then