Weakly Implicative (Fuzzy) Logics I: Basic Properties

This paper presents two classes of propositional logics (understood as a consequence relation). First we generalize the well-known class of implicative logics of Rasiowa and introduce the class of weakly implicative logics. This class is broad enough to contain many “usual” logics, yet easily manageable with nice logical properties. Then we introduce its subclass–the class of weakly implicative fuzzy logics. It contains the majority of logics studied in the literature under the name fuzzy logic. We present many general theorems for both classes, demonstrating their usefulness and importance.The work was supported by grant A100300503 of the Grant Agency of the Academy of Sciences of the Czech Republic and by Institutional Research Plan AVOZ10300504.     

Sequent calculi for branching time temporal logics of knowledge and beliefwith awareness: Completeness and decidability

In this paper, we consider branching time temporal logic CT L with epistemic modalities for knowledge (belief) and with awareness operators. These logics involve the discrete-time linear temporal logic operators “next” and “until” with the branching temporal logic operator “on all paths”. In addition, the temporal logic of knowledge (belief) contains an indexed set of unary modal operators “agent i knows” (“agent i believes”). In a language of these logics, there are awareness operators. For these logics, we present sequent calculi with a restricted cut rule. Thus, we get proof systems where proof-search becomes decidable. The soundness and completeness for these calculi are proved. Published in Lietuvos Matematikos Rinkinys, Vol. 47, No. 3, pp. 328–340, July–September, 2007.     

The optimal convergence of the h–p version of the boundary element method with quasiuniform meshes for elliptic problems on polygonal domains

In the framework of the Jacobi-weighted Besov spaces, we analyze the lower and upper bounds of errors in the h–p version of boundary element solutions on quasiuniform meshes for elliptic problems on polygons. Both lower bound and upper bound are optimal in h and p, and they are of the same order. The optimal convergence of the h–p version of boundary element method with quasiuniform meshes is proved, which includes the optimal rates for h version with quasiuniform meshes and the p version with quasiuniform degrees as two special cases. Dedicated to Professor Charles Micchelli on the occasion of his sixtieth birthday Mathematics subject classification (2000) 65N38. Benqi Guo: The work of this author was supported by NSERC of Canada under Grant OGP0046726 and was complete during visiting Newton Institute for Mathematical Sciences, Cambridge University for participating in special program “Computational Challenges in PDEs” in 2003. Norbert Heuer: This author is supported by Fondecyt project No. 1010220 and by the FONDAP Program (Chile) on Numerical Analysis. Current address: Mathematical Sciences, Brunel University, Uxbridge, U.K.     

On the relation between ADM and Bondi energy-momenta Ⅲ-perturbed radiative spatial infinity

In a vacuum spacetime equipped with the Bondi’s radiating metric which is asymptotically flat at spatial infinity including gravitational radiation (Condition D), we establish the relation between the ADM total energy-momentum and the Bondi energy-momentum for perturbed radiative spatial infinity. The perturbation is given by defining the “real” time as the sum of the retarded time, the Euclidean distance and certain function f. This work is partially supported by the National Natural Science Foundation of China (Grant Nos. 10231050, 10421001), the National Key Basic Research Project of China (Grant No. 2006CB805905) and the Innovation Project of Chinese Academy of Sciences     

The number of rooted Eulerian planar maps

In this paper we provide a solution of the functional equation unsolved in the paper, by the second author, "On functional equations arising from map enumerations" that appeared in Discrete Math, 123: 93-109 (1993). It is also the number of combinatorial distinct rooted general eulerian planar maps with the valency of root-vertex, the number of non-root vertices and non-root faces of the maps as three parameters. In particular, a result in the paper, by the same author, "On the number of eulerian planar map...     

If a two-point extension of a Bernoulli shift has an ergodic square,then it is Bernoulli

A notion of “nesting” for very weakly Bernoulli distributions is developed and used to prove that any two-point extension of a Bernoulli shift, if it has ergodic square, must itself be Bernoulli. This work was supported in part by N.S.F. Grant NCS76-09159.     

No random reals in countable support iterations

We prove a preservation theorem for limit steps of countable support iterations of proper forcing notions whose particular cases are preservations of the following properties on limit steps: “no random reals are added”, “μ(Random(V))≠1”, “no dominating reals are added”, “Cohen(V) is not comeager”. Consequently, countable support iterations of σ-centered forcing notions do not add random reals. The work was supported by BRF of Israel Academy of Sciences and by grant GA SAV 365 of Slovak Academy of Sciences.     

Newton-KKT interior-point methods for indefinite quadratic programming

Two interior-point algorithms are proposed and analyzed, for the (local) solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (much like in the case of primal-dual algorithms for linear programming) search directions for the “primal” variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton (or quasi-Newton) direction for the solution of the equalities in the first-order KKT conditions of optimality or a perturbed version of these conditions. Our algorithms are adapted from previously proposed algorithms for convex quadratic programming and general nonlinear programming. First, inspired by recent work by P. Tseng based on a “primal” affine-scaling algorithm (à la Dikin) [J. of Global Optimization, 30 (2004), no. 2, 285–300], we consider a simple Newton-KKT affine-scaling algorithm. Then, a “barrier” version of the same algorithm is considered, which reduces to the affine-scaling version when the barrier parameter is set to zero at every iteration, rather than to the prescribed value. Global and local quadratic convergence are proved under nondegeneracy assumptions for both algorithms. Numerical results on randomly generated problems suggest that the proposed algorithms may be of great practical interest. The work of the first author was supported in part by the School of Computational Science of Florida State University through a postdoctoral fellowship. Part of this work was done while this author was a Research Fellow with the Belgian National Fund for Scientific Research (Aspirant du F.N.R.S.) at the University of Liège. The work of the second author was supported in part by the National Science Foundation under Grants DMI9813057 and DMI-0422931 and by the US Department of Energy under Grant DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation or those of the US Department of Energy.     

Light affine lambda calculus and polynomial time strong normalization

Light Linear Logic (LLL) and Intuitionistic Light Affine Logic (ILAL) are logics that capture polynomial time computation. It is known that every polynomial time function can be represented by a proof of these logics via the proofs-as-programs correspondence. Furthermore, there is a reduction strategy which normalizes a given proof in polynomial time. Given the latter polynomial time “weak” normalization theorem, it is natural to ask whether a “strong” form of polynomial time normalization theorem holds or not. In this paper, we introduce an untyped term calculus, called Light Affine Lambda Calculus (λLA), which corresponds to ILAL. λLA is a bi-modal λ-calculus with certain constraints, endowed with very simple reduction rules. The main property of LALC is the polynomial time strong normalization: any reduction strategy normalizes a given λLA term in a polynomial number of reduction steps, and indeed in polynomial time. Since proofs of ILAL are structurally representable by terms of λLA, we conclude that the same holds for ILAL. This is a full version of the paper [21] presented at LICS 2001.     

Weighted norm inequalities,off-diagonal estimates and elliptic operators Part II: Off-diagonal estimates on spaces of homogeneous type

This is the second part of a series of four articles on weighted norm inequalities, off-diagonal estimates and elliptic operators. We consider a substitute to the notion of pointwise bounds for kernels of operators which usually is a measure of decay. This substitute is that of off-diagonal estimates expressed in terms of local and scale invariant L^p − L^q estimates. We propose a definition in spaces of homogeneous type that is stable under composition. It is particularly well suited to semigroups. We study the case of semigroups generated by elliptic operators. This work was partially supported by the European Union (IHP Network “Harmonic Analysis and Related Problems” 2002-2006, Contract HPRN-CT-2001-00273-HARP). The second author was also supported by MEC “Programa Ramón y Cajal, 2005” and by MEC Grant MTM2004-00678.     

On homogeneous and self-dual algorithms for LCP

We present some generalizations of a homogeneous and self-dual linear programming (LP) algorithm to solving the monotone linear complementarity problem (LCP). Again, while it achieves the best known interior-point iteration complexity, the algorithm does not need to use any “big-M” number, and it detects LCP infeasibility by generating a certificate. To our knowledge, this is the first interior-point and infeasible-starting algorithm for the LCP with these desired features. Research supported in part by NSF Grant DDM-9207347, the University of Iowa Oberman Fellowship and the Iowa College of Business Administration Summer Grant. Part of this work is done while the author is visiting the Delft Optimization Center at the University of Technology, Delft, Netherlands, supported by the Dutch Organization for Scientific Research (NWO).     

A characterization of vector measure games inpNA

We give a complete characterization of games inpNA of the formf ^o μ (where μ is a vector of finite number of non-atomic probability measures, andf is a real valued function on the range of μ withf(0)=0). Specifically, we show thatf ^o μ is inpNA iff “f is continuous at μ” (the definition of the latter is given in the paper). This work was supported by National Science Foundation Grant SOC 75-21820-A01 at the Institute for Mathematical Studies in the Social Sciences, Stanford University.     

On weakening the Deduction Theorem and strengthening Modus Ponens

This paper studies, with techniques of Abstract Algebraic Logic, the effects of putting a bound on the cardinality of the set of side formulas in the Deduction Theorem, viewed as a Gentzen‐style rule, and of adding additional assumptions inside the formulas present in Modus Ponens, viewed as a Hilbert‐style rule. As a result, a denumerable collection of new Gentzen systems and two new sentential logics have been isolated. These logics are weaker than the positive implicative logic. We have determined their algebraic models and the relationships between them, and have classified them according to several standard criteria of Abstract Algebraic Logic. One of the logics is protoalgebraic but neither equivalential nor weakly algebraizable, a rare situation where very few natural examples were hitherto known. In passing we have found new, alternative presentations of positive implicative logic, both in Hilbert style and in Gentzen style, and have characterized it in terms of the restricted Deduction Theorem: it is the weakest logic satisfying Modus Ponens and the Deduction Theorem restricted to at most 2 side formulas. The algebraic part of the work has lead to the class of quasi‐Hilbert algebras, a quasi‐variety of implicative algebras introduced by Pla and Verdú in 1980, which is larger than the variety of Hilbert algebras. Its algebraic properties reflect those of the corresponding logics and Gentzen systems. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Modes of the tectorial membrane, transversal eigenfunctions, and the origin of the outer hair cell oscillations

The tectorial membrane (TM) of the mammalian inner ear is considered as a system of weakly bent beams and is modeled by a long flat anisotropic plate with one edge supported by the immovable “limbus,” while the opposite edge rests on top of the outer hair cells (OHC). The cross-sectional eigenfunctions of the tectorial membrane isolated from Corti's organ are calculated. It is shown that, under the condition that the limbal edge is supported, the first eigenfunction has an immovable nodal point near the free edge. If the corresponding eigenfrequency of the tectorial membrane coincides with the fundamental eigenfrequency of the cross section, the middle part of the tectorial membrane moves in phase with the basilar membrane, while its marginal edge moves in the opposite direction. As a consequence, the outer hair cells, connecting the middle line of the basilar membrane with its marginal edge, are subject to altering compressive and stretching forces. Thus, the oscillations of the outer hair cells seem to be merely a forced, “passive” mechanical movement rather than an “active” biological process. Taking into account the shapes of the graphs of the tectorial membrane cross-sectional eigenfunctions provides a possibility of explaining a great deal of various experimental data in a simple and natural way without conjecturing negative damping. Bibliography: 25 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 218, 1994, pp. 138–148. This work was supported by the Russian Foundation of Fundamental Research (Grant 93-011-16148). Translated by S. M. Novoselova.     

New series of weakly implicative selector sets

In this paper we specify classes of weakly implicative selector sets and describe their interconnections for the case when the number of variables n does exceed 3 (see A. N. Degtev and D. I. Ivanov, “Weakly Implicative Selector Sets of Dimension 3” Diskretn. Matem. 11 (3), 126–132 (1999)).     

Abelian Logic and the Logics of Pointed Lattice-Ordered Varieties

We consider the class of pointed varieties of algebras having a lattice term reduct and we show that each such variety gives rise in a natural way, and according to a regular pattern, to at least three interesting logics. Although the mentioned class includes several logically and algebraically significant examples (e.g. Boolean algebras, MV algebras, Boolean algebras with operators, residuated lattices and their subvarieties, algebras from quantum logic or from depth relevant logic), we consider here in greater detail Abelian ℓ-groups, where such logics respectively correspond to: i) Meyer and Slaney’s Abelian logic [31]; ii) Galli et al.’s logic of equilibrium [21]; iii) a new logic of “preservation of truth degrees”. This paper was written while the second author was a Visiting Professor in the Department of Education at the University of Cagliari. The facilities and assistance provided by the University and by the Department are gratefully acknowledged.     

Exploring the complexity boundary between coloring and?list-coloring

Many classes of graphs where the vertex coloring problem is polynomially solvable are known, the most prominent being the class of perfect graphs. However, the list-coloring problem is NP-complete for many subclasses of perfect graphs. In this work we explore the complexity boundary between vertex coloring and list-coloring on such subclasses of perfect graphs where the former admits polynomial-time algorithms but the latter is NP-complete. Our goal is to analyze the computational complexity of coloring problems lying “between” (from a computational complexity viewpoint) these two problems: precoloring extension, μ-coloring, and (γ,μ)-coloring. Flavia Bonomo partially supported by UBACyT Grants X606 and X069 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil). Guillermo Durán partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems” (Chile), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil). Javier Marenco partially supported by UBACyT Grant X069 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil).     

Concentrating solutions for the Hénon equation in ℝ2

We consider the boundary value problem Δu+⋎x⋎^2α u ^p =0, α>0, in the unit ballB with homogeneous Dirichlet boundary condition andp a large exponent. We find a condition which ensures the existence of a positive solutionu _p concentrating outside the origin atk symmetric points asp goes to +∞. The same techniques lead also to a more general result on general domains. In particular, we find that concentration at the origin is always possible, provided α⊄IN. The first author is supported by M.U.R.S.T., project “Variational methods and nonlinear differential equations” and a PIMS Postdoctoral Fellowship. The second author is supported by M.U.R.S.T., project “Metodi variazionali e topologici nello studio di fenomeni non lineari.” The third author is supported by an Earmarked Grant from RGC of HK.     

Geometric Aspects of Force Controllability for a Swimming Model

We study controllability properties (swimming capabilities) of a mathematical model of an abstract object which “swims” in the 2-D Stokes fluid. Our goal is to investigate how the geometric shape of this object affects the forces acting upon it. Such problems are of interest in biology and engineering applications dealing with propulsion systems in fluids. This work was supported in part by NSF Grant DMS-0504093.