Optimization of dialectical outcomes in dialogical argumentation

When informal arguments are presented, there may be imprecision in the language used, and so the audience may be uncertain as to the structure of the argument graph as intended by the presenter of the arguments. For a presenter of arguments, it is useful to know the audience's argument graph, but the presenter may be uncertain as to the structure of it. To model the uncertainty as to the structure of the argument graph in situations such as these, we can use probabilistic argument graphs. The set of subgraphs of an argument graph is a sample space. A probability value is assigned to each subgraph such that the sum is 1, thereby reflecting the uncertainty over which is the actual subgraph. We can then determine the probability that a particular set of arguments is included or excluded from an extension according to a particular Dung semantics. We represent and reason with extensions from a graph and from its subgraphs, using a logic of dialectical outcomes that we present. We harness this to define the notion of an argumentation lottery, which can be used by the audience to determine the expected utility of a debate, and can be used by the presenter to decide which arguments to present by choosing those that maximize expected utility. We investigate some of the options for using argumentation lotteries, and provide a computational evaluation.     

Probabilistic qualification of attack in abstract argumentation

An argument graph is a graph where each node denotes an argument, and each arc denotes an attack by one argument on another. It offers a valuable starting point for theoretical analysis of argumentation following the proposals by Dung. However, the definition of an argument graph does not take into account the belief in the attacks. In particular, when constructing an argument graph from informal arguments, where each argument is described in free text, it is often evident that there is uncertainty about whether some of the attacks hold. This might be because there is some expressed doubt that an attack holds or because there is some imprecision in the language used in the arguments. In this paper, we use the set of spanning subgraphs of an argument graph as a sample space. A spanning subgraph contains all the arguments, and a subset of the attacks, of the argument graph. We assign a probability value to each spanning subgraph such that the sum of the assignments is 1. This means we can reflect the uncertainty over which is the actual subgraph using this probability distribution. Using the probability distribution over subgraphs, we can then determine the probability that a set of arguments is admissible or an extension. We can also obtain the probability of an attack relationship in the original argument graph as a marginal distribution (i.e. it is the sum of the probability assigned to each subgraph containing that attack relationship). We investigate some of the features of this proposal, and we consider the utility of our framework for capturing some practical argumentation scenarios.     

New results on the equivalence between zero-one programming and continuous concave programming

In this work, we study continuous reformulations of zero-one concave programming problems. We introduce new concave penalty functions and we prove, using general equivalence results here derived, that the obtained continuous problems are equivalent to the original combinatorial problem.     

Advances in integrative statistics for logic programming

We present recent developments on the syntax of Real, a library for interfacing two Prolog systems to the statistical language R. We focus on the changes in Prolog syntax within SWI-Prolog that accommodate greater syntactic integration, enhanced user experience and improved features for web-services. We recount the full syntax and functionality of Real as well as presenting a full application and sister packages which include Prolog code interfacing a number of common and useful tasks that can be delegated to R. We argue that Real is a powerful extension to logic programming, providing access to a popular statistical system that has complementary strengths in areas such as machine learning, statistical inference and visualisation. Furthermore, Real has a central role to play in the uptake of semantic web, computational biology and bioinformatics as application areas for research in logic programming.     

Separation logic and logics with team semantics

Separation logic is a successful logical system for formal reasoning about programs that mutate their data structures. Team semantics, on the other side, is the basis of modern logics of dependence and independence. Separation logic and team semantics have been introduced with quite different motivations, and are investigated by research communities with rather different backgrounds and objectives. Nevertheless, there are obvious similarities between these formalisms. Both separation logic and logics with team semantics involve the manipulation of second-order objects, such as heaps and teams, by first-order syntax without reference to second-order variables. Moreover, these semantical objects are closely related; it is for instance obvious that a heap can be seen as a team, and the separating conjunction of separation logic is (essentially) the same as the team-semantical disjunction. Based on such similarities, the possible connections between separation logic and team semantics have been raised as a question at several occasions, and lead to informal discussions between these research communities. The objective of this paper is to make this connection precise, and to study its potential but also its obstacles and limitations.     

A game semantics for disjunctive logic programming

Denotational semantics of logic programming and its extensions (by allowing negation, disjunctions, or both) have been studied thoroughly for many years. In 1998, a game semantics was given to definite logic programs by Di Cosmo, Loddo, and Nicolet, and a few years later it was extended to deal with negation by Rondogiannis and Wadge. Both approaches were proven equivalent to the traditional semantics. In this paper we define a game semantics for disjunctive logic programs and prove soundness and completeness with respect to the minimal model semantics of Minker. The overall development has been influenced by the games studied for PCF and functional programming in general, in the styles of Abramsky–Jagadeesan–Malacaria and Hyland–Ong–Nickau.     

Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals

Probabilistic team semantics is a framework for logical analysis of probabilistic dependencies. Our focus is on the axiomatizability, complexity, and expressivity of probabilistic inclusion logic and its extensions. We identify a natural fragment of existential second-order logic with additive real arithmetic that captures exactly the expressivity of probabilistic inclusion logic. We furthermore relate these formalisms to linear programming, and doing so obtain PTIME data complexity for the logics. Moreover, on finite structures, we show that the full existential second-order logic with additive real arithmetic can only express NP properties. Lastly, we present a sound and complete axiomatization for probabilistic inclusion logic at the atomic level.     

Possibilistic nested logic programs and strong equivalence

In this paper, the class of possibilistic nested logic programs is introduced. These possibilistic logic programs allow us to use nested expressions in the bodies and heads of their rules. By considering a possibilistic nested logic program as a possibilistic theory, a construction of a possibilistic logic programing semantics based on answer sets for nested logic programs and the proof theory of possibilistic logic is defined. In order to define a general method for computing the possibilistic answer sets of a possibilistic nested program, the idea of equivalence between possibilistic nested programs is explored. By considering properties of equivalence between possibilistic programs, a process of transforming a possibilistic nested logic program into a possibilistic disjunctive logic program is defined. Given that our approach is an extension of answer set programming, we also explore the concept of strong equivalence between possibilistic nested logic programs. To this end, we introduce the concept of poss SE-models. Therefore, we show that two possibilistic nested logic programs are strong equivalents whenever they have the same poss SE-models.The expressiveness of the possibilistic nested logic programs is illustrated by a scenario from the medical domain. In particular, we exemplify how possibilistic nested logic programs are expressive enough for capturing medical guidelines which are pervaded by vagueness and qualitative information.     

On the Presburger fragment of logics with multiteam semantics

In team semantics, which is the basis of modern logics of dependence and independence, formulae are evaluated on sets of assignments, called teams. Multiteam semantics instead takes mulitplicities of data into account and is based on multisets of assignments, called multiteams. Logics with multiteam semantics can be embedded into a two-sorted variant of existential second-order logics, with arithmetic operations on multiplicities. Here we study the Presburger fragment of such logics, permitting only addition, but not multiplication on multiplicities. It can be shown that this fragment corresponds to inclusion-exclusion logic in multiteam semantics, but, in contrast to the situation in team semantics, that it is strictly contained in independence logic. We give different characterisations of this fragment by various atomic dependency notions.     

P-stable models of strong kernel programs

The research community has long recognized the study of non-monotonic reasoning (NMR) as a promising approach to model features of commonsense reasoning. We study one of the semantics that are useful to formalize NMR, called the p-stable semantics. We introduce three different formats for normal programs: negative normal programs, restricted negative normal programs and strong kernel programs. These forms help to simplify the search of p-stable models of the original program. One of the main results of this paper indicates that the p-stable semantics for strong kernel programs is the same as the stable semantics. This way, all the applications based on stable semantics for those kernel programs (defined in [S. Costantini, A. Provetti, Normal forms for answer set programming, J. Theory Pract. Log. Program. 5 (2005) 747-760]) that are strong kernel programs can also be based on the p-stable semantics.     

The distribution semantics for normal programs with function symbols

The distribution semantics integrates logic programming and probability theory using a possible worlds approach. Its intuitiveness and simplicity have made it the most widely used semantics for probabilistic logic programming, with successful applications in many domains. When the program has function symbols, the semantics was defined for special cases: either the program has to be definite or the queries must have a finite number of finite explanations. In this paper we show that it is possible to define the semantics for all programs. We also show that this definition coincides with that of Sato and Kameya on positive programs. Moreover, we highlight possible approaches for inference, both exact and approximate.     

Probabilistic abductive logic programming using Dirichlet priors

Probabilistic programming is an area of research that aims to develop general inference algorithms for probabilistic models expressed as probabilistic programs whose execution corresponds to inferring the parameters of those models. In this paper, we introduce a probabilistic programming language (PPL) based on abductive logic programming for performing inference in probabilistic models involving categorical distributions with Dirichlet priors. We encode these models as abductive logic programs enriched with probabilistic definitions and queries, and show how to execute and compile them to boolean formulas. Using the latter, we perform generalized inference using one of two proposed Markov Chain Monte Carlo (MCMC) sampling algorithms: an adaptation of uncollapsed Gibbs sampling from related work and a novel collapsed Gibbs sampling (CGS). We show that CGS converges faster than the uncollapsed version on a latent Dirichlet allocation (LDA) task using synthetic data. On similar data, we compare our PPL with LDA-specific algorithms and other PPLs. We find that all methods, except one, perform similarly and that the more expressive the PPL, the slower it is. We illustrate applications of our PPL on real data in two variants of LDA models (Seed and Cluster LDA), and in the repeated insertion model (RIM). In the latter, our PPL yields similar conclusions to inference with EM for Mallows models.     

Algorithmic equivalence in quadratic programming,I: A least-distance programming problem

It is demonstrated that Wolfe's algorithm for finding the point of smallest Euclidean norm in a given convex polytope generates the same sequence of feasible points as does the van de Panne-Whinstonsymmetric algorithm applied to the associated quadratic programming problem. Furthermore, it is shown how the latter algorithm may be simplified for application to problems of this type.This work was supported by the National Science Foundation, Grant No. MCS-71-03341-AO4, and by the Office of Naval Research, Contract No. N00014-75-C-0267.     

On intuitionistic modal and tense logics and their classical companion logics: Topological semantics and bisimulations

We take the well-known intuitionistic modal logic of Fischer Servi with semantics in bi-relational Kripke frames, and give the natural extension to topological Kripke frames. Fischer Servi’s two interaction conditions relating the intuitionistic pre-order (or partial-order) with the modal accessibility relation generalize to the requirement that the relation and its inverse be lower semi-continuous with respect to the topology. We then investigate the notion of topological bisimulation relations between topological Kripke frames, as introduced by Aiello and van Benthem, and show that their topology-preserving conditions are equivalent to the properties that the inverse relation and the relation are lower semi-continuous with respect to the topologies on the two models. The first main result is that this notion of topological bisimulation yields semantic preservation w.r.t. topological Kripke models for both intuitionistic tense logics, and for their classical companion multi-modal logics in the setting of the Gödel translation. After giving canonical topological Kripke models for the Hilbert-style axiomatizations of the Fischer Servi logic and its classical companion logic, we use the canonical model in a second main result to characterize a Hennessy–Milner class of topological models between any pair of which there is a maximal topological bisimulation that preserve the intuitionistic semantics.     

On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method

Interest in linear programming has been intensified recently by Karmarkar’s publication in 1984 of an algorithm that is claimed to be much faster than the simplex method for practical problems. We review classical barrier-function methods for nonlinear programming based on applying a logarithmic transformation to inequality constraints. For the special case of linear programming, the transformed problem can be solved by a “projected Newton barrier” method. This method is shown to be equivalent to Karmarkar’s projective method for a particular choice of the barrier parameter. We then present details of a specific barrier algorithm and its practical implementation. Numerical results are given for several non-trivial test problems, and the implications for future developments in linear programming are discussed. The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AA03-76SF00326, PA No. DE-AS03-76ER72018; National Science Foundation Grants DCR-8413211 and ECS-8312142; the Office of Naval Research Contract N00014-85-K-0343; and the U.S. Army Research Office Contract DAAG29-84-K-0156. The research of J.A. Tomlin was supported by Ketron, Inc. and the Office of Naval Research Contract N00014-85-C-0338.     

On geometric programming and complementary slackness

When the terms in a convex primal geometric programming (GP) problem are multiplied by slack variables whose values must be at least unity, the invariance conditions may be solved as constraints in a linear programming (LP) problem in logarithmically transformed variables. The number of transformed slack variables included in the optimal LP basis equals the degree of difficulty of the GP problem, and complementary slackness conditions indicate required changes in associated GP dual variables. A simple, efficient search procedure is used to generate a sequence of improving primal feasible solutions without requiring the use of the GP dual objective function. The solution procedure appears particularly advantageous when solving very large geometric programming problems, because only the right-hand constants in a system of linear equations change at each iteration.The influence of J. G. Ecker, the writer's teacher, is present throughout this paper. Two anonymous referees and the Associate Editor made very helpful suggestions. Dean Richard W. Barsness provided generous support for this work.     

An equivalence between two algorithms for quadratic programming

In this paper, we demonstrate that the Van de Panne—Whinston symmetric simplex method when applied to a certain implicit formulation of a quadratic program generates the same sequence of primal feasible vectors as does the Von Hohenbalken simplicial decomposition algorithm specialized to the same program. Such an equivalence of the two algorithms extends earlier results for a least-distance program due to Cottle—Djang.This research was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University, under Contract N00014-75-C-0621 NR 047-048 with the Office of Naval Research.     

On fuzzy linear programming

Fuzzy multi-objective and fuzzy Goal Programming are discussed in connection with several membership functions which are used to transform the original problem into three equivalent linear programming problems. Existence and uniqueness theorems are given. Fuzzy duality is presented, and an extension of the initial fuzzy problem arises immediately from it.     

On the gap between the quadratic integer programming problem and its semidefinite relaxation

Consider the semidefinite relaxation (SDR) of the quadratic integer program (QIP): where Q is a given symmetric matrix and D is diagonal. We consider the SDR gap We establish the uniqueness of the SDR solution and prove that if and only if γ_r:=n⁻¹max{x^TVV^Tx:x ∈ {-1, 1}ⁿ}=1 where V is an orthogonal matrix whose columns span the (r–dimensional) null space of D−Q and where D is the unique SDR solution. We also give a test for establishing whether that involves 2^r−1 function evaluations. In the case that γ_r<1 we derive an upper bound on γ which is tighter than Thus we show that `breaching' the SDR gap for the QIP problem is as difficult as the solution of a QIP with the rank of the cost function matrix equal to the dimension of the null space of D−Q. This reduced rank QIP problem has been recently shown to be solvable in polynomial time for fixed r.     

On ℓp programming

Our paper treats the primal and dual program of ?_p programming. ?_p programming is a generalization of ?_p approximation problems. There is a strict connection between ?_p programming and geometrical programming, because in both of them geometrical inequality plays a fundamental role. The structure of our paper follows that of Klafszkys [1].In the first Sections duality theorems are proved, which play an important role in mathematical programming. Most of these results can be found in Petersons and Eckers [3,4,5], but our proofs are much more simple and we show these fundamental properties more detailed.Afterwards the relation between the Lagrange function and the optimal solution pair is investigated. Regularity is investigated as well and we show the marginal value of ?_p programming. In the end linear programming ?_p constrained ?_p approximation problems, the quadratically constrained quadratic programming and compromise programming are shown as special cases of ?_p programming.