Post’s Problem for ordinal register machines: An explicit approach

We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.     

A Branch-and-Price Algorithm for the Capacitated Arc Routing Problem with Stochastic Demands

We address the Capacitated Arc Routing Problem with Stochastic Demands (CARPSD), which we formulate as a Set Partitioning Problem. The CARPSD is solved by a Branch-and-Price algorithm, which we apply without graph transformation. The demand’s stochastic nature is incorporated into the pricing problem. Computational results are reported.     

Speed’s Orbit Problem: Variations on Themes of Burnside

The paper offers a solution to T. P. Speed’s Orbit Problem, describing the orbit decomposition of direct powers of a transitive finite group action. The solution is given in terms of the Burnside algebra of the group and the right action of an incidence algebra of the subgroup lattice on a module of finitary functions. As a corollary, it is shown that almost all orbits in powers of a faithful action are regular. This gives one possible ‘GF(1)’ version of Burnside’s original theorem that each irreducible complex representation of a finite group appears in a tensor power of a fixed faithful representation.     

Limit cycles of quadratic systems

In this paper, the global qualitative analysis of planar quadratic dynamical systems is established and a new geometric approach to solving Hilbert’s Sixteenth Problem in this special case of polynomial systems is suggested. Using geometric properties of four field rotation parameters of a new canonical system which is constructed in this paper, we present a proof of our earlier conjecture that the maximum number of limit cycles in a quadratic system is equal to four and their only possible distribution is (3:1) [V.A. Gaiko, Global Bifurcation Theory and Hilbert’s Sixteenth Problem, Kluwer, Boston, 2003]. Besides, applying the Wintner–Perko termination principle for multiple limit cycles to our canonical system, we prove in a different way that a quadratic system has at most three limit cycles around a singular point (focus) and give another proof of the same conjecture.     

Extracting Herbrand disjunctions by functional interpretation

Carrying out a suggestion by Kreisel, we adapt Gödel’s functional interpretation to ordinary first-order predicate logic(PL) and thus devise an algorithm to extract Herbrand terms from PL-proofs. The extraction is carried out in an extension of PL to higher types. The algorithm consists of two main steps: first we extract a functional realizer, next we compute the β-normal-form of the realizer from which the Herbrand terms can be read off. Even though the extraction is carried out in the extended language, the terms are ordinary PL-terms. In contrast to approaches to Herbrand’s theorem based on cut elimination orɛ-elimination this extraction technique is, except for the normalization step, of low polynomial complexity, fully modular and furthermore allows an analysis of the structure of the Herbrand terms, in the spirit of Kreisel ([13]), already prior to the normalization step. It is expected that the implementation of functional interpretation in Schwichtenberg’s MINLOG system can be adapted to yield an efficient Herbrand-term extraction tool.BRICS, Basic Research in Computer Science, funded by the Danish National Research FoundationUlrich Kohlenbach’s research was partially supported by the Danish National Research Council, Grant no. 21-02-0474.     

Computation of an infinite integral using series acceleration

A numerical computation in crystallography involves an infinite integral depending on one parameter. In a recent article in this journal this computational problem is addressed using Romberg’s method and tools for error control. One observe numerical difficulties with the reported approach both near the parameter’s endpoints and near the parameter interval’s midpoint. In this short note we will present an alternative approach making use of a known infinite series formulation of the problem at hand and a simple and efficient series acceleration technique. If some care is taken to avoid cancellations the numerical results are excellent for all values of the parameter. AMS subject classification 65B05, 65B10, 65D30     

Isomorphism of a Ring to the Endomorphism Ring of an Abelian Group

This paper presents necessary and sufficient conditions under which isomorphism of endomorphism rings of additive groups of arbitrary associative rings with 1 implies isomorphism of these rings. For a certain class of Abelian groups, we present a criterion which shows when isomorphism of their endomorphism rings implies isomorphism of these groups. We demonstrate necessary and sufficient conditions under which an arbitrary ring is the endomorphism ring of an Abelian group. This solves Problem 84 in L. Fuchs’ “Infinite Abelian Groups.”__________Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 9, No. 1, pp. 231–234, 2003.     

The effect of management discretion on hedging and fair valuation of participating policies with maturity guarantees

In this paper we consider how an insurer should invest in order to hedge the maturity guarantees inherent in participating policies. Many papers have considered the case where the guarantee is increased each year according to the performance of an exogenously given reference portfolio subject to some guaranteed rate. However, in this paper we will consider the more realistic case whereby the reference portfolio is replaced by the insurer’s own investments which are controlled completely at the discretion of the insurer’s management. Hence in our case any change in the insurer’s investment strategy leads to a change in the underlying value process of the participating contract. We use a binomial tree model to show how this risk can be hedged, and hence calculate the fair value of the contract at the outset.     

Leaving the Moon by means of invariant manifolds of libration point orbits

The aim of this work is to look for rescue trajectories that leave the surface of the Moon, belonging to the hyperbolic manifolds associated with the central manifold of the Lagrangian points L₁ and L₂ of the Earth–Moon system. The model used for the Earth–Moon system is the Circular Restricted Three-Body Problem. We consider as nominal arrival orbits halo orbits and square Lissajous orbits around L₁ and L₂ and we show, for a given Δv, the regions of the Moon’s surface from which we can reach them. The key point of this work is the geometry of the hyperbolic manifolds associated with libration point orbits. Both periodic/quasi-periodic orbits and their corresponding stable invariant manifold are approximated by means of the Lindstedt–Poincaré semi-analytical approach.     

The <Emphasis Type="Italic">q</Emphasis>-Variations of Sylvester’s Bijection Between Odd and Strict Partitions

The q-identities corresponding to Sylvester’s bijection between odd and strict partitions are investigated. In particular, we show that Sylvester’s bijection implies the Rogers-Fine identity and give a simple proof of a partition theorem of Fine, which does not follow directly from Sylvester’s bijection. Finally, the so-called (m, c)-analogues of Sylvester’s bijection are also discussed.2000 Mathematics Subject Classification: Primary—05A17, 05A15, 33D15, 11P83     

Induced effects and technological innovation with strategic environmental policy

This paper investigates an environmental policy designed to reduce the emission of pollutants under uncertainty, where the agents’ problem is formulated as an optimal stopping problem. We first analyze the single-agent’s case according to Pindyck [Pindyck, R.S., 2002. Optimal timing problems in environmental economics. Journal of Economic Dynamics and Control 26, 1677–1697]. We then extend the model to the case in which there are two competing agents. Therefore, we consider the external economic effects that are peculiar to an agent’s environmental policy decision. Finally, we consider the effect of technological innovation. The results of the analysis suggest that if there are two competing agents, they implement environmental policy simultaneously. Furthermore, the threshold for implementing environmental policy is higher when there are two agents, and how long these two agents take to implement environmental policy depends on the magnitude of the external economic effect. Furthermore, when we consider the effect of technological innovation, we show that the incentive to be the leader occurs if an additional condition is satisfied.     

The design of multiactivity multifacility systems

We consider a service/distribution system in which each of N activities is to be carried out at one or several facility locations. Each activity is to be assigned to one out of a specified set of configurations; each configuration is a specific subset of the set of L facilities being considered, along with a specific strategy for their use. We call such a system a multiactivity multifacility system and present a mathematical formulation for its optimal design that includes capacity restrictions at the facilities and the treatment of multiple criteria. The design problem is simply to choose an appropriate configuration for each of the N activities. We discuss various criteria, and we show that the multiactivity multifacility design problem includes many familiar discrete location problems as special cases. We introduce a 0–1 linear optimization model called the Team Generalized Assignment Problem (T-GAP) and show that parametric solution of a T-GAP will yield all efficient solutions of the multiactivity multifacility design problem with multiple criteria. Rather than attempting to find all efficient solutions, however, we advocate an interactive approach and describe an interactive branch-and-bound algorithm that solves the design problem as a finite sequence of T-GAP's.     

Characterizing properties of approximate solutions for optimization problems

Approximate solutions for optimization problems become of interest if the ‘true’ optimum cannot be found: this may happen for the simple reason that an optimum does not exist or because of the ‘bounded rationality’ (or bounded accuracy) of the optimizer. This paper characterizes several approximate solutions by means of consistency and additional requirements. In particular we consider invariance properties. We prove that, where the domain contains optimization problems without maximum, there is no non-trivial consistent solution satisfying non-emptiness, translation and multiplication invariance. Moreover, we show that the class of ‘satisficing’ solutions is obtained, if the invariance axioms are replaced with Chernoff’s Choice Axiom.     

Total domination in planar graphs of diameter two

MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213–229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. Henning, Domination in planar graphs with small diameter, J. Graph Theory 40 (2002) 1–25] showed that there is a unique planar graph of diameter two with domination number three. It follows that the total domination number of a planar graph of diameter two is at most three. In this paper, we consider the problem of characterizing planar graphs with diameter two and total domination number three. We say that a graph satisfies the domination-cycle property if there is some minimum dominating set of the graph not contained in any induced 5-cycle. We characterize the planar graphs with diameter two and total domination number three that satisfy the domination-cycle property and show that there are exactly thirty-four such planar graphs.     

Iterative patching and the asymmetric traveling salesman problem

Although Branch-and-Bound (BnB) methods are among the most widely used techniques for solving hard problems, it is still a challenge to make these methods smarter. In this paper, we investigate iterative patching, a technique in which a fixed patching procedure is applied at each node of the BnB search tree for the Asymmetric Traveling Salesman Problem. Computational experiments show that iterative patching results in general in search trees that are smaller than the classical BnB trees, and that solution times are lower for usual random and sparse instances. Furthermore, it turns out that, on average, iterative patching with the Contract-or-Patch procedure of Glover, Gutin, Yeo and Zverovich (2001) and the Karp–Steele procedure are the fastest, and that ‘iterative’ Modified Karp–Steele patching generates the smallest search trees.     

An improvement on Marotto’s theorem and its applications to chaotification of switching systems

The controversy surrounding the correctness of Marotto’s theorem continues over the last two decades, with many researchers claiming to have found an error in the proof. In this paper, we show that Marotto’s theorem is indeed correct for analyzing the existence of chaos in the sense of Li-Yorke even after relaxing certain assumptions in the proof. In addition, we extend the theory to derive the conditions for the existence of chaos in the sense of Devaney. We show that these results can be applied to study the chaotification of linear switching systems.     

The self-validated method for polynomial zeros of high efficiency

The improved iterative method of Newton’s type for the simultaneous inclusion of all simple complex zeros of a polynomial is proposed. The presented convergence analysis, which uses the concept of the R-order of convergence of mutually dependent sequences, shows that the convergence rate of the basic third order method is increased from 3 to 6 using Ostrowski’s corrections. The new inclusion method with Ostrowski’s corrections is more efficient compared to all existing methods belonging to the same class. To demonstrate the convergence properties of the proposed method, two numerical examples are given.     

Productive public expenditures, expectation formations and nonlinear dynamics

In this paper, we investigate the dynamic properties of an overlapping generations’ model with capital accumulation and publicly funded inventions under three different expectations: perfect foresight, myopic expectations and adaptive expectations. We show that considering productive public expenditures in the model will increase the dimension of the dynamical system. To study the dynamic behavior of a high-dimensional dynamical system, we focus on the case when the elasticity of publicly funded invention to output is small and approximate the system by using a one-dimensional dynamical system. This approximation method provides an efficient way to rigorously prove the existence of chaos in high-dimensional dynamical systems. We show that when agents are perfectly foresighted, there exists a unique, nontrivial steady state which is a global attractor. Cycles or even chaos may occur under myopic and adaptive expectations when the inter-temporal elasticity of substitution of consumption is large enough. Furthermore, we find that the impact of fiscal policy is sensible to the expectation formation.     

Skew domino Schensted correspondence and sign-imbalance

Using growth diagrams, we define a skew domino Schensted correspondence which is a domino analogue of the skew Robinson–Schensted correspondence due to Sagan and Stanley. The color-to-spin property of Shimozono and White is extended. As an application, we give a simple generating function for the weighted sum of skew domino tableaux, which is a generalization of Stanley’s sign-imbalance formula. The generating function gives a method to calculate the generalized sign-imbalance formula. We also extend Sjöstrand’s theorems on sign-imbalance of skew shapes.     

The Fermat rule for multifunctions on Banach spaces

Using variational analysis, we study vector optimization problems with objectives being closed multifunctions on Banach spaces or in Asplund spaces. In particular, in terms of the coderivatives, we present Fermat’s rules as necessary conditions for an optimal solution of the above problems. As applications, we also provide some necessary conditions (in terms of Clarke’s normal cones or the limiting normal cones) for Pareto efficient points.This research was supported by a postdoctoral fellowship scheme (CUHK) and an Earmarked Grant from the Research Grant Council of Hong Kong. Research of the first author was also supported by the National Natural Science Foundation of P. R. China (Grant No. 10361008) and the Natural Science Foundation of Yunnan Province, P. R. China (Grant No. 2003A002M).