A normalizing system of natural deduction for intuitionistic linear logic

 The main result of this paper is a normalizing system of natural deduction for the full language of intuitionistic linear logic. No explicit weakening or contraction rules for -formulas are needed. By the systematic use of general elimination rules a correspondence between normal derivations and cut-free derivations in sequent calculus is obtained. Normalization and the subformula property for normal derivations follow through translation to sequent calculus and cut-elimination. Received: 10 October 2000 / Revised version: 26 July 2001 / Published online: 2 September 2002 Mathematics Subject Classification (2000): 03F52, 03F05 Keywords or phrases: Linear logic – Natural deduction – General elimination rules     

A Gentzen-style axiomatization for basic predicate calculus

 We introduce a Gentzen-style sequent calculus axiomatization for Basic Predicate Calculus. Our new axiomatization is an improvement of the previous axiomatizations, in the sense that it has the subformula property. In this system the cut rule is eliminated. Received: 18 April 2000 / Published online: 2 September 2002 Mathematics Subject Classification (2000): Primary 03F05; Secondary 03F99, 03B60 Key words or phrases: Basic predicate calculus – Cut elimination – Sequent     

Hájek basic fuzzy logic and Łukasiewicz infinite-valued logic

 Using the theory of BL-algebras, it is shown that a propositional formula ϕ is derivable in Łukasiewicz infinite valued Logic if and only if its double negation ˜˜ϕ is derivable in Hájek Basic Fuzzy logic. If SBL is the extension of Basic Logic by the axiom (φ & (φ→˜φ)) → ψ, then ϕ is derivable in in classical logic if and only if ˜˜ ϕ is derivable in SBL. Axiomatic extensions of Basic Logic are in correspondence with subvarieties of the variety of BL-algebras. It is shown that the MV-algebra of regular elements of a free algebra in a subvariety of BL-algebras is free in the corresponding subvariety of MV-algebras, with the same number of free generators. Similar results are obtained for the generalized BL-algebras of dense elements of free BL-algebras. Received: 20 June 2001 / Published online: 2 September 2002 This paper was prepared while the first author was visiting the Universidad de Barcelona supported by INTERCAMPUS Program E.AL 2000. The second author was partially supported by Grants 2000SGR-0007 of D. G. R. of Generalitat de Catalunya and PB 97-0888 of D. G. I. C. Y. T. of Spain. Mathematics Subject classification (2000): 03B50, 03B52, 03G25, 06D35 Keywords or Phrases: Basic fuzzy logic – Łukasiewicz logic – BL-algebras – MV-algebras – Glivenko's theorem     

CM-triviality and generic structures

 We show that any relational generic structure whose theory has finite closure and amalgamation over closed sets is stable CM-trivial with weak elimination of imaginaries. Received: 21 December 2001 / Published online: 5 November 2002 Mathematics Subject Classification (2000): 03C45 Key words or phrases: CM-triviality – Generic structures – Stability     

Distributive-Lattice Semantics of Sequent Calculi with Structural Rules

The goal of the paper is to develop a universal semantic approach to derivable rules of propositional multiple-conclusion sequent calculi with structural rules, which explicitly involve not only atomic formulas, treated as metavariables for formulas, but also formula set variables (viz., metavariables for finite sets of formulas), upon the basis of the conception of model introduced in (Fuzzy Sets Syst 121(3):27–37, 2001). One of the main results of the paper is that any regular sequent calculus with structural rules has such class of sequent models (called its semantics) that a rule is derivable in the calculus iff it is sound with respect to each model of the semantics. We then show how semantics of admissible rules of such calculi can be found with using a method of free models. Next, our universal approach is applied to sequent calculi for many-valued logics with equality determinant. Finally, we exemplify this application by studying sequent calculi for some of such logics.      

The stable forking conjecture and generic structures

 We prove that for any simple theory which is constructed via Fr?issé-Hrushovski method, if the forking independence is the same as the d-independence then the stable forking property holds. Received: 22 January 2001 / Published online: 19 December 2002 This article is part of the author's D-Phil thesis, written at the University of Oxford and supported by the Ministry of Higher Education of Iran. The author would like to thank the Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran, for its financial support whilst working on this article. Mathematics Subject Classification (2000): 03C45 Key words or phrases: Generic structures – Fr?issé-Hrushovski method – Predimension – Simple theories – Stable theories – Stable forking conjecture     

Solving Problems with Semidefinite and Related Constraints Using Interior-Point Methods for Nonlinear Programming

 In this paper, we describe how to reformulate a problem that has second-order cone and/or semidefiniteness constraints in order to solve it using a general-purpose interior-point algorithm for nonlinear programming. The resulting problems are smooth and convex, and numerical results from the DIMACS Implementation Challenge problems and SDPLib are provided. Received: March 10, 2001 / Accepted: January 18, 2002 Published online: September 27, 2002 Key Words. semidefinite programming – second-order cone programming – interior-point methods – nonlinear programming Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

Hydrodynamic limit for ∇φ interface model on a wall

 We consider random evolution of an interface on a hard wall under periodic boundary conditions. The dynamics are governed by a system of stochastic differential equations of Skorohod type, which is Langevin equation associated with massless Hamiltonian added a strong repelling force for the interface to stay over the wall. We study its macroscopic behavior under a suitable large scale space-time limit and derive a nonlinear partial differential equation, which describes the mean curvature motion except for some anisotropy effects, with reflection at the wall. Such equation is characterized by an evolutionary variational inequality. Received: 10 January 2002 / Revised version: 18 August 2002 / Published online: 15 April 2003 Mathematics Subject Classification (2000): 60K35, 82C24, 35K55, 35K85 Key words or phrases: Hydrodynamic limit – Effective interfaces – Hard wall – Skorohod's stochastic differential equation – Evolutionary variational inequality     

A linear integer programming bound for maximum-entropy sampling

 We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the results of some computational experiments. Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002 Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral bound – Fischer's inequality – branch-and-bound – dynamic programming Mathematics Subject Classification (2000): 52B12, 90C10 Send offprint requests to: Jon Lee Correspondence to: Jon Lee     

Intuitionistic Frege systems are polynomially equivalent

In a paper by Cook and Reckhow (1979), it is shown that any two classical Frege systems polynomially simulate each other. The same proof does not work for intuitionistic Frege systems, since they can have nonderivable admissible rules. (The rule A/B is derivable if the formula A → B is derivable. The rule A/B is admissible if for all substitutions σ, if σ(A) is derivable, then σ(B) is derivable.) In this paper, we polynomially simulate a single admissible rule. Therefore any two intuitionistic Frege systems polynomially simulate each other. Bibliography: 20 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 316, 2004, pp. 129–146.     

Renormalization and homogenization of fractional diffusion equations with random data

 This paper presents a renormalization and homogenization theory for fractional-in-space or in-time diffusion equations with singular random initial conditions. The spectral representations for the solutions of these equations are provided. Gaussian and non-Gaussian limiting distributions of the renormalized solutions of these equations are then described in terms of multiple stochastic integral representations. Received: 30 May 2000 / Revised version: 9 November 2001 / Published online: 10 September 2002 Mathematics Subject Classification (2000): Primary 62M40, 62M15; Secondary 60H05, 60G60 Key words or phrases: Fractional diffusion equation – Scaling laws – Renormalised solution – Long-range dependence – Non-Gaussian scenario – Mittag-Leffler function – Stable distributions – Bessel potential – Riesz potential     

A generalization of the Dual Ellentuck Theorem

 We prove versions of the Dual Ramsey Theorem and the Dual Ellentuck Theorem for families of partitions which are defined in terms of games. Received: 8 July 1999 Published online: 19 December 2002 RID="*" ID="*" The author wishes to thank the Swiss National Science Foundation for supporting him. The authors thank the referee for helpful comments. Mathematics Subject Classification (2000): 03E02, 05D10, 03E35 Key words or phrases: Dual Ramsey Theorem – Dual Ellentuck Theorem – Partitions – Games     

Dynamic ordinal analysis

 Dynamic ordinal analysis is ordinal analysis for weak arithmetics like fragments of bounded arithmetic. In this paper we will define dynamic ordinals – they will be sets of number theoretic functions measuring the amount of sΠ ^b ₁(X) order induction available in a theory. We will compare order induction to successor induction over weak theories. We will compute dynamic ordinals of the bounded arithmetic theories sΣ ^b _n (X)−L ^m IND for m=n and m=n+1, n≥0. Different dynamic ordinals lead to separation. In this way we will obtain several separation results between these relativized theories. We will generalize our results to further languages extending the language of bounded arithmetic. Received: 27 April 2001 / Published online: 19 December 2002 The results for sΣ ^b _n (X)−L ^m IND are part of the authors dissertation [3]; the results for sΣ ^b _m (X)−L ^m+1 IND base on results of ARAI [1]. Mathematics Subject Classification (2000): Primary 03F30; Secondary 03F05, 03F50 Key words or phrases: Dynamic ordinal – Bounded arithmetic – Proof-theoretic ordinal – Order induction – Semi-formal system – Cut-elimination     

Multifractal products of cylindrical pulses

 New multiplicative and statistically self-similar measures μ are defined on ℝ as limits of measure-valued martingales. Those martingales are constructed by multiplying random functions attached to the points of a statistically self-similar Poisson point process defined in a strip of the plane. Several fundamental problems are solved, including the non-degeneracy and the multifractal analysis of μ. On a bounded interval, the positive and negative moments of diverge under broad conditions. First received: 14 September 1999 / Resubmited: 27 June 2001 / Revised version: 30 May 2002 / Published online: 30 September 2002 Mathematics Subject Classification (2002): 28A80, 60G18, 60G44, 60G55, 60G57 Key words or phrases: Random measures – Multifractal analysis – Continuous time martingales – Statistically self-similar Poisson point processes     

Smoothed analysis of termination of linear programming algorithms

 We perform a smoothed analysis of a termination phase for linear programming algorithms. By combining this analysis with the smoothed analysis of Renegar's condition number by Dunagan, Spielman and Teng (http://arxiv.org/abs/cs.DS/0302011) we show that the smoothed complexity of interior-point algorithms for linear programming is O(m ³ log(m/Σ)). In contrast, the best known bound on the worst-case complexity of linear programming is O(m ³ L), where L could be as large as m. We include an introduction to smoothed analysis and a tutorial on proof techniques that have been useful in smoothed analyses. Received: December 10, 2002 / Accepted: April 28, 2003 Published online: June 5, 2003 Key words. smoothed analysis – linear programming – interior-point algorithms – condition numbers Mathematics Subject Classification (1991): 90C05, 90C51, 68Q25     

The modal logic of the countable random frame

 We study the modal logic M L ^r of the countable random frame, which is contained in and `approximates' the modal logic of almost sure frame validity, i.e. the logic of those modal principles which are valid with asymptotic probability 1 in a randomly chosen finite frame. We give a sound and complete axiomatization of M L ^r and show that it is not finitely axiomatizable. Then we describe the finite frames of that logic and show that it has the finite frame property and its satisfiability problem is in EXPTIME. All these results easily extend to temporal and other multi-modal logics. Finally, we show that there are modal formulas which are almost surely valid in the finite, yet fail in the countable random frame, and hence do not follow from the extension axioms. Therefore the analog of Fagin's transfer theorem for almost sure validity in first-order logic fails for modal logic. Received: 1 May 2000 / Revised version: 29 July 2001 / Published online: 2 September 2002 Mathematics Subject Classification (2000): 03B45, 03B70, 03C99 Key words or phrases: Modal logic – Random frames – Almost sure frame validity – Countable random frame – Axiomatization – Completeness     

Natural deduction with general elimination rules

The structure of derivations in natural deduction is analyzed through isomorphism with a suitable sequent calculus, with twelve hidden convertibilities revealed in usual natural deduction. A general formulation of conjunction and implication elimination rules is given, analogous to disjunction elimination. Normalization through permutative conversions now applies in all cases. Derivations in normal form have all major premisses of elimination rules as assumptions. Conversion in any order terminates. Through the condition that in a cut-free derivation of the sequent Γ⇒C, no inactive weakening or contraction formulas remain in Γ, a correspondence with the formal derivability relation of natural deduction is obtained: All formulas of Γ become open assumptions in natural deduction, through an inductively defined translation. Weakenings are interpreted as vacuous discharges, and contractions as multiple discharges. In the other direction, non-normal derivations translate into derivations with cuts having the cut formula principal either in both premisses or in the right premiss only. Received: 1 December 1998 / Revised version: 30 June 2000 / Published online: 18 July 2001     

Many-Place Sequent Calculi for Finitely-Valued Logics

In this paper, we study multiplicative extensions of propositional many-place sequent calculi for finitely-valued logics arising from those introduced in Sect. 5 of Pynko (J Multiple-Valued Logic Soft Comput 10:339–362, 2004) through their translation by means of singularity determinants for logics and restriction of the original many-place sequent language. Our generalized approach, first of all, covers, on a uniform formal basis, both the one developed in Sect. 5 of Pynko (J Multiple-Valued Logic Soft Comput 10:339–362, 2004) for singular finitely-valued logics (when singularity determinants consist of a variable alone) and conventional Gentzen-style (i.e., two-place sequent) calculi suggested in Pynko (Bull Sect Logic 33(1):23–32, 2004) for finitely-valued logics with equality determinant. In addition, it provides a universal method of constructing Tait-style (i.e., one-place sequent) calculi for finitely-valued logics with singularity determinant (in particular, for Łukasiewicz finitely-valued logics) that fits the well-known Tait calculus (Lecture Notes in Mathematics, Springer, Berlin, 1968) for the classical logic. We properly extend main results of Pynko (J Multiple-Valued Logic Soft Comput 10:339–362, 2004) and explore calculi under consideration within the framework of Sect. 7 of Pynko (Arch Math Logic 45:267–305, 2006), generalizing the results obtained in Sect. 7.5 of Pynko (Arch Math Logic 45:267–305 2006) for two-place sequent calculi associated with finitely-valued logics with equality determinant according to Pynko (Bull Sect Logic 33(1):23–32, 2004). We also exemplify our universal elaboration by applying it to some denumerable families of well-known finitely-valued logics.     

Multi-self-similar Markov processes on ℝ<Subscript>+</Subscript><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> and their Lamperti representations

 A classical result, due to Lamperti, establishes a one-to-one correspondence between a class of strictly positive Markov processes that are self-similar, and the class of one-dimensional Lévy processes. This correspondence is obtained by suitably time-changing the exponential of the Lévy process. In this paper we generalise Lamperti's result to processes in n dimensions. For the representation we obtain, it is essential that the same time-change be applied to all coordinates of the processes involved. Also for the statement of the main result we need the proper concept of self-similarity in higher dimensions, referred to as multi-self-similarity in the paper. The special case where the Lévy process ξ is standard Brownian motion in n dimensions is studied in detail. There are also specific comments on the case where ξ is an n-dimensional compound Poisson process with drift. Finally, we present some results concerning moment sequences, obtained by studying the multi-self-similar processes that correspond to n-dimensional subordinators. Received: 22 August 2002 / Revised version: 10 February 2003 Published online: 15 April 2003 RID="*" ID="*" MaPhySto – Centre for Mathematical Physics and Stochastics, funded by a grant from the Danish National Research Foundation Mathematics Subject Classification (2000): 60G18, 60G51, 60J25, 60J60, 60J75 Key words or phrases: Lévy process – Self-similarity – Time-change – Exponential functional – Brownian motion – Bessel process – Piecewise deterministic Markov process – Moment sequence     

Stochastic flows associated to coalescent processes

 We study a class of stochastic flows connected to the coalescent processes that have been studied recently by M?hle, Pitman, Sagitov and Schweinsberg in connection with asymptotic models for the genealogy of populations with a large fixed size. We define a bridge to be a right-continuous process (B(r),r[0,1]) with nondecreasing paths and exchangeable increments, such that B(0)=0 and B(1)=1. We show that flows of bridges are in one-to-one correspondence with the so-called exchangeable coalescents. This yields an infinite-dimensional version of the classical Kingman representation for exchangeable partitions of ℕ. We then propose a Poissonian construction of a general class of flows of bridges and identify the associated coalescents. We also discuss an important auxiliary measure-valued process, which is closely related to the genealogical structure coded by the coalescent and can be viewed as a generalized Fleming-Viot process. Received: 26 November 2002 / Revised version: 10 February 2003 / Published online: 15 April 2003 Mathematics Subject Classification (2000): 60G09, 60J25, 92D30 Key words or phrases: Flow – Coalescence – Exchangeability – Bridge