Fraenkel‐Carnap properties

In the 1920's Fraenkel and Carnap raised the question of whether or not every finitely axiomatizable semantically complete theory formulated in the theory of types is categorical. Partial answers to this and a related question are presented for theories formulated in second‐order logic. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Non‐elementary speed‐ups in logic calculi

In this paper we show some non‐elementary speed‐ups in logic calculi: Both a predicative second‐order logic and a logic for fixed points of positive formulas are shown to have non‐elementary speed‐ups over first‐order logic. Also it is shown that eliminating second‐order cut formulas in second‐order logic has to increase sizes of proofs super‐exponentially, and the same in eliminating second‐order epsilon axioms. These are proved by relying on results due to P. Pudlák. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Glivenko like theorems in natural expansions of BCK‐logic

The classical Glivenko theorem asserts that a propositional formula admits a classical proof if and only if its double negation admits an intuitionistic proof. By a natural expansion of the BCK‐logic with negation we understand an algebraizable logic whose language is an expansion of the language of BCK‐logic with negation by a family of connectives implicitly defined by equations and compatible with BCK‐congruences. Many of the logics in the current literature are natural expansions of BCK‐logic with negation. The validity of the analogous of Glivenko theorem in these logics is equivalent to the validity of a simple one‐variable formula in the language of BCK‐logic with negation. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Algebraization of the Three‐valued BCK‐logic

In this paper a definition of n‐valued system in the context of the algebraizable logics is proposed. We define and study the variety V₃, showing that it is definitionally equivalent to the equivalent quasivariety semantics for the “Three‐valued BCK‐logic”. As a consequence we find an axiomatic definition of the above system.     

A logic‐mathematical point of view of the truth: Reality,perception, and language

In this article, the authors propose a theory of the truth value of propositions from a logic‐mathematical point of view. The work that the authors present is an attempt to address this question from an epistemological, linguistic, and logical‐mathematical point of view. What is it to exist and how do we define existence? The main objective of this work is an approach to the first of these questions. We leave a more thorough treatment of the problem of existence for future works. © 2014 Wiley Periodicals, Inc. Complexity 20: 58–67, 2015     

Independent sets of maximal size in tensor powers of vertex‐transitive graphs

Let G be a connected, nonbipartite vertex‐transitive graph. We prove that if the only independent sets of maximal cardinality in the tensor product G × G are the preimages of the independent sets of maximal cardinality in G under projections, then the same holds for all finite tensor powers of G, thus providing an affirmative answer to a question raised by Larose and Tardif (J Graph Theory 40(3) (2002), 162–171). © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 295‐301, 2009     

A note on Grzegorczyk's logic

Grzegorczyk's modal logic (Grz) corresponds to the class of upwards well‐founded partially ordered Kripke frames, however all known proofs of this fact utilize some form of the Axiom of Choice; G. Boolos asked in [1], whether it is provable in plain ZF. We answer his question negatively: Grz corresponds (in ZF) to a class of frames, which does not provably coincide with upwards well‐founded posets in ZF alone. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Non decomposable connectives of linear logic

This paper studies the so-called generalized multiplicative connectives of linear logic, focusing on the question of finding the “non-decomposable” ones, i.e., those that cannot be expressed as combinations of the default binary connectives of multiplicative linear logic, ⊗ (times) and ⅋ (par). In particular, we concentrate on generalized connectives of a surprisingly simple form, called “entangled connectives”, and prove a characterization theorem giving a criterion for identifying the undecomposable entangled ones.     

The complexity of the matching‐cut problem for planar graphs and other graph classes

The Matching‐Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be ‐complete when restricted to graphs with maximum degree four. In this paper it is shown that the problem remains ‐complete for planar graphs with maximum degree four, answering a question by Patrignani and Pizzonia. It is also shown that the problem is ‐complete for planar graphs with girth five. The reduction is from planar graph 3‐colorability and differs from earlier reductions. In addition, for certain graph classes polynomial time algorithms to find matching‐cuts are described. These classes include claw‐free graphs, co‐graphs, and graphs with fixed bounded tree‐width or clique‐width. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 109–126, 2009     

Completeness and interpolation of almost‐everywhere quantification over finitely additive measures

We give an axiomatization of first‐order logic enriched with the almost‐everywhere quantifier over finitely additive measures. Using an adapted version of the consistency property adequate for dealing with this generalized quantifier, we show that such a logic is both strongly complete and enjoys Craig interpolation, relying on a (countable) model existence theorem. We also discuss possible extensions of these results to the almost‐everywhere quantifier over countably additive measures.     

Pseudo quasi‐3 designs and their applications to coding theory

We define a pseudo quasi‐3 design as a symmetric design with the property that the derived and residual designs with respect to at least one block are quasi‐symmetric. Quasi‐symmetric designs can be used to construct optimal self complementary codes. In this article we give a construction of an infinite family of pseudo quasi‐3 designs whose residual designs allow us to construct a family of codes with a new parameter set that meet the Grey Rankin bound. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 411–418, 2009     

Archimedean classes in integral commutative residuated chains

This paper investigates a quasi‐variety of representable integral commutative residuated lattices axiomatized by the quasi‐identity resulting from the well‐known Wajsberg identity (p → q) → q ≤ (q → p) → p if it is written as a quasi‐identity, i. e., (p → q) → q ≈ 1 ? (q → p) → p ≈ 1 . We prove that this quasi‐identity is strictly weaker than the corresponding identity. On the other hand, we show that the resulting quasi‐variety is in fact a variety and provide an axiomatization. The obtained results shed some light on the structure of Archimedean integral commutative residuated chains. Further, they can be applied to various subvarieties of MTL‐algebras, for instance we answer negatively Hájek's question asking whether the variety of ΠMTL‐algebras is generated by its Archimedean members (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Complexity of clique‐coloring odd‐hole‐free graphs

In this paper we investigate the problem of clique‐coloring, which consists in coloring the vertices of a graph in such a way that no monochromatic maximal clique appears, and we focus on odd‐hole‐free graphs. On the one hand we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, but on the other hand it is NP‐hard to decide if they are 2‐clique‐colorable, and we do not know if there exists any bound k₀ such that they are all k₀ ‐clique‐colorable. First we will prove that (odd hole, codiamond)‐free graphs are 2‐clique‐colorable. Then we will demonstrate that the complexity of 2‐clique‐coloring odd‐hole‐free graphs is actually Σ₂ P‐complete. Finally we will study the complexity of deciding whether or not a graph and all its subgraphs are 2‐clique‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 139–156, 2009     

Artificial intelligence and social forecasting*

Artificial intelligence (AI) is the study of how to write programs enabling computers to do things that would require intelligence if done by people, and it could engage with social forecasting in two ways. First, it is part of the overall social‐technological context within which forecasters work. Commercial Al‐programs will affect markets and life‐styles; and advice‐giving “expert” systems will raise novel legal, social, and psychological problems. Second, AI‐programs might be used for making the social forecasts. Unlike the (essentially quantitative) computer models used for this purpose today, they could reason (and explain themselves) in verbal form. Writing an expert system requires clarification of the theories, assumptions, and “rule‐of‐thumb” inferences concerned. It would be easier to identify the inherent moral‐political bias than it is in models comprising sets of differential equations.     

Application of Exp‐function method to EW‐Burgers equation

In this article, Exp‐function method is used to obtain an exact solution of the equal‐width wave‐Burgers equation (EW‐Burgers). The method is straightforward and concise, and its applications are promising. It is shown that Exp‐function method, with the help of symbolic computation, provides a very effective and powerful mathematical tool for solving EW‐Burgers equation. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2010     

Partial characterizations of circular‐arc graphs

A circular‐arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular‐arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to any of the following classes: P₄ ‐free graphs, paw‐free graphs, claw‐free chordal graphs and diamond‐free graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 289–306, 2009     

Spanning even subgraphs of 3‐edge‐connected graphs

By Petersen's theorem, a bridgeless cubic graph has a 2‐factor. H. Fleischner extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has a spanning even subgraph. Our main result is that, under the stronger hypothesis of 3‐edge‐connectivity, we can find a spanning even subgraph in which every component has at least five vertices. We show that this is in some sense best possible by constructing an infinite family of 3‐edge‐connected graphs in which every spanning even subgraph has a 5‐cycle as a component. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 37–47, 2009     

An explicit Schilder‐type theorem for super‐Brownian motions

Like ordinary Brownian motion, super‐Brownian motion, a central object in the theory of superprocesses, is a universal object arising in a variety of settings. Schilder‐type theorems and Cramér‐type theorems are two of the major topics for large‐deviation theory. A Schilder‐type (which is also a Cramér‐type) sample large deviation for super‐Brownian motions with a good rate function represented by a variation formula was established in 1993 and 1994; since then there have been very valuable contributions for giving an affirmative answer to the question of whether this sample large deviation holds with an explicit good rate function. In this paper, thanks to previous results on this issue and the Brownian snake, we establish such a large deviation for nonzero finite initial measures. © 2010 Wiley Periodicals, Inc.     

Dual‐Context Sequent Calculus and Strict Implication

We introduce a dual‐context style sequent calculus which is complete with respectto Kripke semantics where implication is interpreted as strict implication in the modal logic K. The cut‐elimination theorem for this calculus is proved by a variant of Gentzen's method.     

Commutative rings whose ideals form an MV‐algebra

In this work we introduce a class of commutative rings whose defining condition is that its lattice of ideals, augmented with the ideal product, the semi‐ring of ideals, is isomorphic to an MV‐algebra. This class of rings coincides with the class of commutative rings which are direct sums of local Artinian chain rings with unit (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)