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     

The fluted fragment with transitive relations

The fluted fragment is a fragment of first-order logic (without equality) in which, roughly speaking, the order of quantification of variables coincides with the order in which those variables appear as arguments of predicates. It is known that this fragment has the finite model property. We consider extensions of the fluted fragment with various numbers of transitive relations, as well as the equality predicate. In the presence of one transitive relation (together with equality), the finite model property is lost; nevertheless, we show that the satisfiability and finite satisfiability problems for this extension remain decidable. We also show that the corresponding problems in the presence of two transitive relations (with equality) or three transitive relations (without equality) are undecidable, even for the two-variable sub-fragment.     

The two‐variable fragment with counting and equivalence

We consider the two‐variable fragment of first‐order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NExpTime ‐complete. We further show that the corresponding problems for two‐variable first‐order logic with counting and two equivalences are both undecidable.     

Barwise's information frames and modal logics

 The paper studies Barwise's information frames and answers the John Barwise question: to find axiomatizations for the modal logics generated by information frames. We find axiomatic systems for (i) the modal logic of all complete information frames, (ii) the logic of all sound and complete information frames, (iii) the logic of all hereditary and complete information frames, (iv) the logic of all complete, sound and hereditary information frames, and (v) the logic of all consistent and complete information frames. The notion of weak modal logics is also proposed, and it is shown that the weak modal logics generated by all information frames and by all hereditary information frames are K and K4 respectively. To develop general theory, we prove that (i) any Kripke complete modal logic is the modal logic of a certain class of information frames and that (ii) the modal logic generated by any given class of complete, rarefied and fully classified information frames is Kripke complete. This paper is dedicated to the memory of talented mathematician John Barwise. Received: 7 May 2000 Published online: 10 October 2002 Key words or phrases: Knowledge presentation – Information – Information flow – Information frames – Modal logic-Kripke model     

Satisfiability of algebraic circuits over sets of natural numbers

We investigate the complexity of satisfiability problems for {∪,∩,⁻,+,×}-circuits computing sets of natural numbers. These problems are a natural generalization of membership problems for expressions and circuits studied by Stockmeyer and Meyer (1973) [10] and McKenzie and Wagner (2003) [8].Our work shows that satisfiability problems capture a wide range of complexity classes such as NL, P, NP, PSPACE, and beyond. We show that in several cases, satisfiability problems are harder than membership problems. In particular, we prove that testing satisfiability for {∩,+,×}-circuits is already undecidable. In contrast to this, the satisfiability for {∪,+,×}-circuits is decidable in PSPACE.     

Non-Classical Stems from Classical: N. A. Vasiliev’s Approach to Logic and his Reassessment of the Square of Opposition

In the XIXth century there was a persistent opposition to Aristotelian logic. Nicolai A. Vasiliev (1880–1940) noted this opposition and stressed that the way for the novel – non-Aristotelian – logic was already paved. He made an attempt to construct non-Aristotelian logic (1910) within, so to speak, the form (but not in the spirit) of the Aristotelian paradigm (mode of reasoning). What reasons forced him to reassess the status of particular propositions and to replace the square of opposition by the triangle of opposition? What arguments did Vasiliev use for the introduction of new classes of propositions and statement of existence of various levels in logic? What was the meaning and role of the “method of Lobachevsky” which was implemented in construction of imaginary logic? Why did psychologism in the case of Vasiliev happen to be an important factor in the composition of the new ‘imaginary’ logic, as he called it?      

Refined common knowledge logics or logics of common information

 In terms of formal deductive systems and multi-dimensional Kripke frames we study logical operations know, informed, common knowledge and common information. Based on [6] we introduce formal axiomatic systems for common information logics and prove that these systems are sound and complete. Analyzing the common information operation we show that it can be understood as greatest open fixed points for knowledge formulas. Using obtained results we explore monotonicity, omniscience problem, and inward monotonocity, describe their connections and give dividing examples. Also we find algorithms recognizing these properties for some particular cases. Received: 21 October 2000 / Published online: 2 September 2002 Key words or phrases: Multi-agent systems – Non-standard logic – Knowledge representation – Common knowledge – Common information – Fixed points, Kripke models – Modal logic     

Perfect IFG-Formulas

IFG logic is a variant of the independence-friendly logic of Hintikka and Sandu. We answer the question: “Which IFG-formulas are equivalent to ordinary first-order formulas?” We use the answer to prove the ordinary cylindric set algebra over a structure can be embedded into a reduct of the IFG-cylindric set algebra over the structure.      

Advances in the ŁΠ and logics

 The ŁΠ and logics were introduced by Godo, Esteva and Montagna. These logics extend many other known propositional and predicate logics, including the three mainly investigated ones (G?del, product and Łukasiewicz logic). The aim of this paper is to show some advances in this field. We will see further reduction of the axiomatic systems for both logics. Then we will see many other logics contained in the ŁΠ family of logics (namely logics induced by the continuous finitely constructed t-norms and Takeuti and Titani's fuzzy predicate logic). Received: 1 October 2000 / Revised version: 27 March 2002 / Published online: 5 November 2002 Partial support of the grant No. A103004/00 of the Grant agency of the Academy of Sciences of the Czech Republic is acknowledged. Key words or phrases: Fuzzy logic – Łukasiewicz logic – Product logic     

Definability of the ring of integers in pro-p galois extensions of number fields

For some infinite algebraic extensionsM of the field of rational numbers we show that the integral closure of ℤ is first-order definable. As an application we prove that the Pythagorean hull of ℚ is an undecidable field.     

Algebraic geometry in first-order logic

In every variety of algebras Θ, we can consider its logic and its algebraic geometry. In previous papers, geometry in equational logic, i.e., equational geometry, has been studied. Here we describe an extension of this theory to first-order logic (FOL). The algebraic sets in this geometry are determined by arbitrary sets of FOL formulas. The principal motivation of such a generalization lies in the area of applications to knowledge science. In this paper, the FOL formulas are considered in the context of algebraic logic. For this purpose, we define special Halmos categories. These categories in algebraic geometry related to FOL play the same role as the category of free algebras Θ⁰ play in equational algebraic geometry. This paper consists of three parts. Section 1 is of introductory character. The first part (Secs. 2–4) contains background on algebraic logic in the given variety of algebras Θ. The second part is devoted to algebraic geometry related to FOL (Secs. 5–7). In the last part (Secs. 8–9), we consider applications of the previous material to knowledge science. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 22, Algebra and Geometry, 2004.     

Entropy of formulas

A probability distribution can be given to the set of isomorphism classes of models with universe {1, ..., n} of a sentence in first-order logic. We study the entropy of this distribution and derive a result from the 0–1 law for first-order sentences.      

On equations in free semigroups with certain constraints on their solutions

It is shown that the solvability problem for equations in free semigroups with certain constraints on their solutions is undecidable. Bibliography: 23 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 358, 2008, pp. 120–129.     

An application of matrix computations to classical second-order optimality conditions

For finite dimensional optimization problems with equality and inequality constraints, a weak constant rank condition (WCR) was introduced by Andreani–Martinez–Schuverdt (AMS) (Optimization 5–6:529–542, 2007) to study classical necessary second-order optimality conditions. However, this condition is not easy to check. Using a polynomial and matrix computation tools, we can substitute it by a weak constant rank condition (WCRQ) for an approximated problem and we present a method for checking points that satisfy WCRQ. We extend the result of (Andreani et al. in Optimization 5–6:529–542, 2007), we show that WCR can be replaced by WCRQ and we prove that these two conditions are independent.     

Short proofs of normalization for the simply- typed λ-calculus,permutative conversions and Gödel's T

 Inductive characterizations of the sets of terms, the subset of strongly normalizing terms and normal forms are studied in order to reprove weak and strong normalization for the simply-typed λ-calculus and for an extension by sum types with permutative conversions. The analogous treatment of a new system with generalized applications inspired by generalized elimination rules in natural deduction, advocated by von Plato, shows the flexibility of the approach which does not use the strong computability/candidate style à la Tait and Girard. It is also shown that the extension of the system with permutative conversions by η-rules is still strongly normalizing, and likewise for an extension of the system of generalized applications by a rule of ``immediate simplification'. By introducing an infinitely branching inductive rule the method even extends to G?del's T. Received 12 October 1998 Published online: 19 December 2002 Mathematics Subject Classification (2000): 03B40 Keywords or phrases: λ-calculus – Permutative/commuting conversions – Sum types – Generalized application – G?del's T_q-ω-rule – Inductive characterization     

Leibniz filters and the strong version of a protoalgebraic logic

A filter of a sentential logic ? is Leibniz when it is the smallest one among all the ?-filters on the same algebra having the same Leibniz congruence. This paper studies these filters and the sentential logic ?⁺ defined by the class of all ?-matrices whose filter is Leibniz, which is called the strong version of ?, in the context of protoalgebraic logics with theorems. Topics studied include an enhanced Correspondence Theorem, characterizations of the weak algebraizability of ?⁺ and of the explicit definability of Leibniz filters, and several theorems of transfer of metalogical properties from ? to ?⁺. For finitely equivalential logics stronger results are obtained. Besides the general theory, the paper examines the examples of modal logics, quantum logics and Łukasiewicz's finitely-valued logics. One finds that in some cases the existence of a weak and a strong version of a logic corresponds to well-known situations in the literature, such as the local and the global consequences for normal modal logics; while in others these constructions give an independent interest to the study of other lesser-known logics, such as the lattice-based many-valued logics. Received: 30 October 1998 /?Published online: 15 June 2001     

Primal-dual first-order methods with $${\mathcal {O}(1/\epsilon)}$$ iteration-complexity for cone programming

In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov’s optimal method (Nesterov in Doklady AN SSSR 269:543–547, 1983; Math Program 103:127–152, 2005), Nesterov’s smooth approximation scheme (Nesterov in Math Program 103:127–152, 2005), and Nemirovski’s prox-method (Nemirovski in SIAM J Opt 15:229–251, 2005), and propose a variant of Nesterov’s optimal method which has outperformed the latter one in our computational experiments. We also derive iteration-complexity bounds for these first-order methods applied to the proposed primal-dual reformulations of the cone programming problem. The performance of these methods is then compared using a set of randomly generated linear programming and semidefinite programming instances. We also compare the approach based on the variant of Nesterov’s optimal method with the low-rank method proposed by Burer and Monteiro (Math Program Ser B 95:329–357, 2003; Math Program 103:427–444, 2005) for solving a set of randomly generated SDP instances.     

On the integrable rational Abel differential equations

In Cheb-Terrab and Roche (Comput Phys Commun 130(1–2):204–231, 2000) a classification of the Abel equations known as solvable in the literature was presented. In this paper, we show that all the integrable rational Abel differential equations that appear in Cheb-Terrab and Roche (Comput Phys Commun 130(1–2):204–231, 2000) and consequently in Cheb-Terrab and Roche (Eur J Appl Math 14(2):217–229, 2003) can be reduced to a Riccati differential equation or to a first-order linear differential equation through a change with a rational map. The change is given explicitly for each class. Moreover, we have found a unified way to find the rational map from the knowledge of the explicitly first integral.     

First- and second-order methods for semidefinite programming

 In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming, putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have been developed for solving large-scale SDP problems. These include first-order nonlinear programming (NLP) methods and more specialized path-following IP methods which use the (preconditioned) conjugate gradient or residual scheme to compute the Newton direction and the notion of matrix completion to exploit data sparsity. Received: December 16, 2002 / Accepted: May 5, 2003 Published online: May 28, 2003 Key words. semidefinite programming – interior-point methods – polynomial complexity – path-following methods – primal-dual methods – nonlinear programming – Newton method – first-order methods – bundle method – matrix completion The author's research presented in this survey article has been supported in part by NSF through grants INT-9600343, INT-9910084, CCR-9700448, CCR-9902010, CCR-0203113 and ONR through grants N00014-93-1-0234, N00014-94-1-0340 and N00014-03-1-0401. Mathematics Subject Classification (2000): 65K05, 90C06, 90C22, 90C25, 90C30, 90C51     

Enumerating teams in first-order team logics

We start the study of the enumeration complexity of different satisfiability problems in first-order team logics. Since many of our problems go beyond DelP, we use a framework for hard enumeration analogous to the polynomial hierarchy, which was recently introduced by Creignou et al. (Discret. Appl. Math. 2019). We show that the problem to enumerate all satisfying teams of a fixed formula in a given first-order structure is DelNP-complete for certain formulas of dependence logic and independence logic. For inclusion logic formulas, this problem is even in DelP. Furthermore, we study the variants of this problem where only maximal or minimal solutions, with respect to cardinality or inclusion, are considered. For the most part these share the same complexity as the original problem. One exception is the cardinality minimum-variant for inclusion logic, which is DelNP-complete, the other is the inclusion maximal-variant for dependence and independence logic, which is in Del⁺NP and DelNP-hard.