Subscribe: Journal of Logic and Computation - current issue
Added By: Feedage Forager Feedage Grade B rated
Language: English
\mathbb{s} \leq  \mathbb{s}  analytic  logic  model  possibilistic logic  possibilistic  quantum  set  solvers  symbolic  theory  weights 
Rate this Feed
Rating: 3.2 starRating: 3.2 starRating: 3.2 starRate this feedRate this feed
Rate this feed 1 starRate this feed 2 starRate this feed 3 starRate this feed 4 starRate this feed 5 star

Comments (0)

Feed Details and Statistics Feed Statistics
Preview: Journal of Logic and Computation - current issue

Journal of Logic and Computation Current Issue

Published: Thu, 01 Feb 2018 00:00:00 GMT

Last Build Date: Thu, 01 Feb 2018 09:49:15 GMT


The universal homogeneous binary tree

Thu, 01 Feb 2018 00:00:00 GMT

A partial order is called semilinear if the upper bounds of each element are linearly ordered and any two elements have a common upper bound. There exists, up to isomorphism, a unique countable existentially closed semilinear order, which we denote by $(\mathbb{S}_{2};\leq )$. We study the reducts of $(\mathbb{S}_{2};\leq )$, i.e. the relational structures with domain $\mathbb{S}_{2}$, all of whose relations are first-order definable in $(\mathbb{S}_{2};\leq )$. Our main result is a classification of the model-complete cores of the reducts of $\mathbb{S}_{2}$. From this, we also obtain a classification of reducts up to first-order interdefinability, which is equivalent to a classification of all subgroups of the full symmetric group on $\mathbb{S}_{2}$ that contain the automorphism group of $(\mathbb{S}_{2};\leq )$ and are closed with respect to the pointwise convergence topology.

On the computational complexity of detecting possibilistic locality

Thu, 01 Feb 2018 00:00:00 GMT

The proofs of quantum nonlocality due to Greenberger, Horne and Zeilinger and due to Hardy are qualitatively different from that of Bell insofar as they rely only on a consideration of whether events are possible or impossible, rather than relying on specific experimental probabilities. We consider the scenario of a bipartite nonlocality experiment, in which two separated experimenters each have access to some measurements they can perform on a system. In a physical theory, some outcomes of this experiment will be labelled possible, others impossible, and an assignment of the values 0 (impossible) and 1 (possible) to these different outcomes forms a table of possibilities. Here, we consider the computational task of determining whether or not a given table of possibilities constitutes a departure from possibilistic local realism. By considering the case in which one party has access to measurements with two outcomes and the other three, it is possible to see at exactly which point this task becomes computationally difficult.

Symbolic possibilistic logic: completeness and inference methods

Wed, 17 Jan 2018 00:00:00 GMT

This paper studies the extension of possibilistic logic to the case when weights attached to formulas are symbolic. These weights then stand for variables that lie in a totally ordered scale, and only partial knowledge is available on the relative strength of these weights in the form of inequality constraints. Reasoning in symbolic possibilistic logic means solving two problems. One is to compute symbolic expressions representing the weights of conclusions of a possibilistic knowledge base. The other problem is that of comparing the relative strength of derived weights, so as to find out if one formula is more certain than another one. Regarding the first problem, a proof of the soundness and the completeness of this logic according to the relative certainty semantics in the sense of necessity measures is provided. Based on this result, two syntactic inference methods are suggested. The first one shows how to use the notion of minimal inconsistent subsets and known techniques that compute them, so as to obtain the symbolic expression representing the necessity degree of a possibilistic formula. A second family of methods computes prime implicates and takes inspiration from the concept of assumption-based theory. It enables symbolic weights attached to consequences to be simplified in the course of their computation, taking inequality constraints into account. Finally, an algorithm is proposed to find if a consequence is more certain than another one. A comparison with the original version of symbolic possibilistic logic introduced by Benferhat and Prade in 2005 is provided.

Modal correspondence theory in the class of all Euclidean frames

Mon, 13 Nov 2017 00:00:00 GMT

The core of this article is the modal correspondence theory in the class of all Euclidean frames. It shows that with respect to the class of all Euclidean frames, every modal formula is first-order definable and the problem of deciding the modal definability of sentences is undecidable.

Shapely monads and analytic functors

Thu, 02 Nov 2017 00:00:00 GMT

In this article, we give precise mathematical form to the idea of a structure whose data and axioms are faithfully represented by a graphical calculus; some prominent examples are operads, polycategories, properads, and PROPs. Building on the established presentation of such structures as algebras for monads on presheaf categories, we describe a characteristic property of the associated monads—the shapeliness of the title—which says that ‘any two operations of the same shape agree’. An important part of this work is the study of analytic functors between presheaf categories, which are a common generalization of Joyal’s analytic endofunctors on sets and of the parametric right adjoint functors on presheaf categories introduced by Diers and studied by Carboni–Johnstone, Leinster and Weber. Our shapely monads will be found among the analytic endofunctors, and may be characterized as the submonads of a universal analytic monad with ‘exactly one operation of each shape’. In fact, shapeliness also gives a way to define the data and axioms of a structure directly from its graphical calculus, by generating a free shapely monad on the basic operations of the calculus. In this article, we do this for some of the examples listed above; in future work, we intend to use this to obtain canonical notions of denotational model for graphical calculi such as Milner’s bigraphs, Lafont’s interaction nets or Girard’s multiplicative proof nets.

Fuzzy approach to quantum Fredkin gate

Fri, 20 Oct 2017 00:00:00 GMT

In the framework of quantum computation with mixed states, we introduce a fuzzy approach to the quantum Fredkin gate. Under this perspective, we investigate the behaviour of the gate applied to factorized and non-factorized quantum states.

Not only size, but also shape counts: abstract argumentation solvers are benchmark-sensitive

Tue, 10 Oct 2017 00:00:00 GMT

We test different solvers dedicated to the solution of classical problems in Abstract Argumentation, as enumeration/existence of extensions, and sceptical/credulous acceptance of arguments. We handle a subset of the solvers tested in ICCMA15, and a superset of graphs used in the same competition. The goal is to provide considerations that can help future comparisons and competitions as ICCMA15. We offer a detailed report of this comparison from the point of view of different graphs, solvers, problems and timeouts. We show that the characteristics of graphs impact on the performance of solvers and on their final ranking. In addition, we extract other general considerations, e.g., reducing the computation timeout does not change the same ranking.

Implementing fragments of ZFC within an r.e. Universe

Wed, 13 Sep 2017 00:00:00 GMT

The present work addresses the question: to what extent do natural models of a sufficiently rich fragment of set theory exist? Such models, here called Friedberg models, are built as a class of sets of natural numbers together with the element-relation “$x$ is in $y$” given by $x\in A_y$, where $A_0$, $A_1$, $A_2$, $\ldots$ is a Friedberg numbering of all r.e. sets of natural numbers. A member $A_x$ of this numbering is considered to be a set in the given model iff the transitive closure of the induced membership relation starting from $x$ is well-founded. Furthermore, for all $k$, the set $B_k = \{x: A_x\mbox{ has size $k$ }\}$ must be recursive. It will be examined whether the axioms of set theory and some basic set-theoretic properties hold in such a model. Because they do not hold in full generality, comprehension and replacement need to be properly adapted. The validity of the axiom of power set depends on the Friedberg model under consideration. The other axioms hold in every Friedberg model.