On the syntactic algorithm for the word problem of left distributivity

Here we investigate the ‘natural’ syntactic algorithm for the word problem of left distributivity, and we establish a sufficient condition which explains the convergence for all terms of a reasonable size. An algorithm for left division is also constructed. Received February 8, 1996; accepted in final form October 3, 1996     

Codimension one minimal cycles with coefficients inZ orZ p , and variational functionals on fibered spaces

Given a compact, oriented Riemannian manifold M, without boundary, and a codimension-one homology class in H_* (M, Z) (or, respectively, in H_* (M, Z_p) with p an odd prime), we consider the problem of finding a cycle of least area in the given class: this is known as the homological Plateau’s problem. We propose an elliptic regularization of this problem, by constructing suitable fiber bundles ξ (resp. ζ) on M, and one-parameter families of functionals defined on the regular sections of ξ, (resp. ζ), depending on a small parameter ε. As ε → 0, the minimizers of these functionals are shown to converge to some limiting section, whose discontinuity set is exactly the minimal cycle desired.     

On The Span Of A Random Channel Assignment Problem

In the radio channel assignment problems considered here, we must assign a ‘channel’ from the set 1,2,... of positive integers to each of n transmitters, and we wish to minimise the span of channels used, subject to the assignment leading to an acceptable level of interference. A standard form of this problem is the ‘constraint matrix’ model. The simplest case of this model (the 0, 1 case) is essentially graph colouring. We consider here a random model for the next simplest case (with lengths 0, 1 or 2), and determine the asymptotic behaviour of the span of channels needed as n→∞. We find that there is a ‘phase change’ in this behaviour, depending on the probabilities for the different lengths.     

Existence of planar curves minimizing length and curvature

We consider the problem of reconstructing a curve that is partially hidden or corrupted by minimizing the functional $ \smallint \sqrt {1 + K_\gamma ^2 ds} $ \smallint \sqrt {1 + K_\gamma ^2 ds} , depending both on the length and curvature K. We fix starting and ending points as well as initial and final directions. For this functional we discuss the problem of existence of minimizers on various functional spaces. We find nonexistence of minimizers in cases in which initial and final directions are considered with orientation. In this case, minimizing sequences of trajectories may converge to curves with angles. We instead prove the existence of minimizers for the “time-reparametrized” functional $ \smallint ||\dot \gamma (t)||\sqrt {1 + K_\gamma ^2 dt} $ \smallint ||\dot \gamma (t)||\sqrt {1 + K_\gamma ^2 dt} for all boundary conditions if the initial and final directions are considered regardless of orientation. In this case, minimizers may present cusps (at most two) but not angles.     

On a class of second order variational problems with constraints

We study the structure of optimal solutions for a class of constrained, second order variational problems on bounded intervals. We show that, for intervals of length greater than some positive constant, the optimal solutions are bounded inC ¹ by a bound independent of the length of the interval. Furthermore, for sufficiently large intervals, the ‘mass’ and ‘energy’ of optimal solutions are almost uniformly distributed.     

On balking from an empty queue

The intuition while observing the economy of queueing systems, is that one’s motivation to join the system, decreases with its level of congestion. Here we present a queueing model where sometimes the opposite is the case. The point of departure is the standard first-come first-served single server queue with Poisson arrivals. Customers commence service immediately if upon their arrival the server is idle. Otherwise, they are informed if the queue is empty or not. Then, they have to decide whether to join or not. We assume that the customers are homogeneous and when they consider whether to join or not, they assess their queueing costs against their reward due to service completion. As the whereabouts of customers interact, we look for the (possibly mixed) join/do not join Nash equilibrium strategy, a strategy that if adopted by all, then under the resulting steady-state conditions, no one has any incentive not to follow it oneself. We show that when the queue is empty then depending on the service distribution, both ‘avoid the crowd’ (ATC) and ‘follow the crowd’ (FTC) scenarios (as well as none-of-the-above) are possible. When the queue is not empty, the situation is always that of ATC. Also, we show that under Nash equilibrium it is possible (depending on the service distribution) that the joining probability when the queue is empty is smaller than it is when the queue is not empty. This research was supported by The Israel Science Foundation Grant No. 237/02.     

Energy asymptotics for Type II superconductors

We study the Ginzburg–Landau functional in the parameter regime describing ‘Type II superconductors’. In the exact regime considered minimizers are localized to the boundary — i.e. the sample is only superconducting in the boundary region. Depending on the relative size of different parameters we describe the concentration behavior and give leading order energy asymptotics. This generalizes previous results by Lu–Pan, Helffer–Pan, and Pan.     

Roof duality,complementation and persistency in quadratic 0–1 optimization

The paper is concerned with the ‘primal’ problem of maximizing a given quadratic pseudo-boolean function. Four equivalent problems are discussed—the primal, the ‘complementation’, the ‘discrete Rhys LP’ and the ‘weighted stability problem of a SAM graph’. Each of them has a relaxation—the ‘roof dual’, the ‘quadratic complementation,’ the ‘continuous Rhys LP’ and the ‘fractional weighted stability problem of a SAM graph’. The main result is that the four gaps associated with the four relaxations are equal. Furthermore, a solution to any of these problems leads at once to solutions of the other three equivalent ones. The four relaxations can be solved in polynomial time by transforming them to a bipartite maximum flow problem. The optimal solutions of the ‘roof-dual’ define ‘best’ linear majorantsp(x) off, having the following persistency property: if theith coefficient inp is positive (negative) thenx _i=1 (0) in every optimum of the primal problem. Several characterizations are given for the case where these persistency results cannot be used to fix any variable of the primal. On the other hand, a class of gap-free functions (properly including the supermodular ones) is exhibited.     

A result on large surfaces of prescribed mean curvature in a Riemannian manifold

Plateau's problem (PP) is studied for surfaces of prescribed mean curvature spanned by a given contour in a 3-d Riemannian manifold. We consider the local situation where a neighborhood of a given point on the manifold is described by a single normal chart. Under certain conditions on and the contour, existence of a small -surface to (PP) is guaranteed by [HK]. The purpose of this paper is the investigation of large -surfaces. Our result states: For sufficiently large (constant) mean curvature and a sufficiently small contour depending on the local geometry of the manifold, (PP) has at least two solutions, a small one and a large one. The proof is based on mountain pass arguments and uses – in contrast to results in the 3-d Euclidean space and in order to derive conformality directly – also a deformation constructed by variations of the independent variable. Received November 8, 1995 / Accepted April 29, 1996     

Bar-On on Self-Knowledge and Expression

I critically discuss the account of self-knowledge presented in Dorit Bar-On’s Speaking My Mind (OUP 2004), focusing on Bar-On’s understanding of what makes our capacity for self-knowledge puzzling and on her ‘neo-expressivist’ solution to the puzzle. I argue that there is an important aspect of the problem of self-knowledge that Bar-On’s account does not sufficiently address. A satisfying account of self-knowledge must explain not merely how we are able to make accurate avowals about our own present mental states, but how we can reasonably regard ourselves as entitled to claim self-knowledge. Addressing this aspect of the problem of self-knowledge requires confronting questions about the metaphysical nature of mental states, questions that Bar-On’s approach seeks to avoid.     

Convergence analysis of a conforming adaptive finite element method for an obstacle problem

The adaptive algorithm for the obstacle problem presented in this paper relies on the jump residual contributions of a standard explicit residual-based a posteriori error estimator. Each cycle of the adaptive loop consists of the steps ‘SOLVE’, ‘ESTIMATE’, ‘MARK’, and ‘REFINE’. The techniques from the unrestricted variational problem are modified for the convergence analysis to overcome the lack of Galerkin orthogonality. We establish R-linear convergence of the part of the energy above its minimal value, if there is appropriate control of the data oscillations. Surprisingly, the adaptive mesh-refinement algorithm is the same as in the unconstrained case of a linear PDE—in fact, there is no modification near the discrete free boundary necessary for R-linear convergence. The arguments are presented for a model obstacle problem with an affine obstacle χ and homogeneous Dirichlet boundary conditions. The proof of the discrete local efficiency is more involved than in the unconstrained case. Numerical results are given to illustrate the performance of the error estimator.     

Variational problems with topological constraints

We introduce a decomposition that captures much of the topology of level sets for functions in certain Sobolev spaces, and allows the definition of an analog of the decreasing rearrangement of a function which respects the topology of level sets. In a variety of settings this decomposition is preserved under weak limits, and so is useful in establishing existence of minimizers of various variational problems with prescribed topological properties. These include variational problems in which ‘topological rearrangements’ are fixed, and ones in which the functional depends on derivatives of rearrangements. Received: December 16, 1998 / Accepted: July 16, 1999     

Constructing greedy linear extensions by interchanging chains

A natural way to prove that a particular linear extension of an ordered set is ‘optimal’ with respect to the ‘jump number’ is to transform this linear extension ‘canonically’ into one that is ‘optimal’. We treat a ‘greedy chain interchange’ transformation which has applications to ordered sets for which each ‘greedy’ linear extension is ‘optimal’.     

Continuous rearrangement and symmetry of solutions of elliptic problems

This work presents new results and applications for the continuous Steiner symmetrization. There are proved some functional inequalities, e.g. for Dirichlet-type integrals and convolutions and also continuity properties in Sobolev spacesW ^1,p. Further it is shown that the local minimizers of some variational problems and the nonnegative solutions of some semilinear elliptic problems in symmetric domains satisfy a weak, ‘local’ kind of symmetry.     

A Ramsey bound on stable sets in Jordan pillage games

Jordan (J Econ Theory 131(1):26–44, 2006) defined ‘pillage games’, a class of cooperative games whose dominance operator is represented by a ‘power function’ satisfying coalitional and resource monotonicity axioms. In this environment, he proved that stable sets must be finite. We provide a graph theoretical interpretation of the problem which tightens the finite bound to a Ramsey number. We also prove that the Jordan pillage axioms are independent.     

The universal torsion-free image of a group

We show that the universal torsion free homomorphic image of any group given by a sufficiently ‘small’ presentation is locally indicable, and give an application to a conjecture of Levin about equations over torsion free groups. Supported by SERC Visiting Fellowship GR/F 97355.     

Weak Keys in MST 1

The public key cryptosystem MST₁ has been introduced by Magliveras et al. [12] (Public Key Cryptosystems from Group Factorizations. Jatra Mountain Mathematical Publications). Its security relies on the hardness of factoring with respect to wild logarithmic signatures. To identify ‘wild-like’ logarithmic signatures, the criterion of being totally-non-transversal has been proposed. We present tame totally-non-transversal logarithmic signatures for the alternating and symmetric groups of degree ≥ 5. Hence, basing a key generation procedure on the assumption that totally-non-transversal logarithmic signatures are ‘wild like’ seems critical. We also discuss the problem of recognizing ‘weak’ totally-non-transversal logarithmic signatures, and demonstrate that another proposed key generation procedure based on permutably transversal logarithmic signatures may produce weak keys. Communicated by: P. Wild     

Isotonic tests for spread and tail

Summary One-sample test problem for ‘stochastically more (or less) spread’ is defined and a family of tests with isotonic power is given. The problem is closely related to that for ‘longer (or shorter) tail’ in the reliability theory and the correspondence between them is shown. To characterize the tests three spread preorders inR ⁿ and corre-sponding tail preorders inR ₊ ⁿ are introduced. Functions which are ‘monotone’ in these orders, and subsets which are ‘centrifugal’ or ‘centripetal’ with respect to these orders are studied. These notions generalize the Schur convexity. The Institute of Statistical Mathematics     

Metaheuristics can solve sudoku puzzles

In this paper we present, to our knowledge, the first application of a metaheuristic technique to the very popular and NP-complete puzzle known as ‘sudoku’. We see that this stochastic search-based algorithm, which uses simulated annealing, is able to complete logic-solvable puzzle-instances that feature daily in many of the UK’s national newspapers. We also introduce a new method for producing sudoku problem instances (that are not necessarily logic-solvable) and use this together with the proposed SA algorithm to try and discover for what types of instances this algorithm is best suited. Consequently we notice the presence of an ‘easy-hard-easy’ style phase-transition similar to other problems encountered in operational research.