LPAR-17-short:Papers with Abstracts

Abstract. We outline the beginnings of a proof-theory for the dialogical logic N introduced in [Alama & Uckelman, 2010].

Abstract. We announce an interactive website for exploring logic with the help of Lorenzen dialogue games. The site allows one to play concrete dialogue games and compute winning plays and winning strategies from initial segments of such games. A variety of dialogue rule sets are available, allowing one to explore different logics through a uniform framework. We have also implemented several formula translations, so that one can explore how games vary as one changes the initial formula of a dialogue game, and we consider some heuristics for computing winning plays and winning strategies.

Abstract. We consider Gödel logics extended by an operator whose semantics is given by I(oA)=min{1,r+I(A)}.

Abstract. The notion of feasibility, applicable in various areas related to logic, is arguably of gradual nature---some tasks are more feasible than others. The possibility of modeling a gradual notion of feasibility in t-norm logics is brought forward and illustrated on the gradual notions of feasible number, feasible knowledge, feasible formula, and feasible computability.

Abstract. Nitpick is a counterexample generator for Isabelle/HOL that builds on Kodkod, a SAT-based first-order relational model finder. Nitpick supports unbounded quantification, (co)inductive predicates and datatypes, and (co)recursive functions. Fundamentally a finite model finder, it approximates infinite types by finite subsets. Our experimental results on Isabelle theories and the TPTP library indicate that Nitpick generates more counterexamples than other model finders for higher-order logic, without restrictions on the form of the formulas to falsify.

Abstract. In this short paper we present a finer analysis of the variants of Local Deduction Theorem in contraction-free logics. We define some natural generalisations called Implicational Deduction Theorems and study their basic properties. The hierarchy of classes of logics defined by these theorems is presented.

Abstract. The goal of this paper is to study the complexity of the set of admissible rules of the implication-negation fragment of intuitionistic logic IPC. Surprisingly perhaps, although this set strictly contains the set of derivable rules (the fragment is not structurally complete), it is also PSPACE-complete. This differs from the situation in the full logic IPC where the admissible rules form a co-NEXP-complete set.

Abstract. AC-completion efficiently handles equality modulo associative and commutative function symbols. In the ground case, the procedure terminates and provides a decision algorithm for the word problem. In this paper, we present a modular extension of ground AC-completion for deciding formulas in the combination of the theory of equality with user-defined AC symbols, uninterpreted symbols and an arbitrary signature disjoint Shostak theory X. The main ideas of our algorithm are first to adapt the definition of rewriting in order to integrate the canonizer of X and second, to replace the equation orientation mechanism found in ground AC-completion with the solver for X.

Abstract. Generalizing the novel clause elimination procedures developed in [1], we introduce explicit (CCE), hidden (HCCE), and asymmetric (ACCE) variants of a procedure that eliminates covered clauses from CNF formulas. We show that these procedures are more effective in reducing CNF formulas than the respective variants of blocked clause elimination, and may hence be interesting as new preprocessing/simplification techniques for SAT solving.

Abstract. The changing of arguments and their attack relation is an intrinsic property of a variety of argumentation systems. So, it is very important to efficiently figure out how the status of arguments in a system evolves when the system is updated. However, unlike other areas of argumentation that have been deeply explored, such as argumentation semantics, proof theories, and algorithms, etc., dynamics of argumentation systems has been comparatively neglected. In this paper, we introduce a general theory (called a division-based method) to cope with this problem based on a new concept: the division of an argumentation framework. When an argumentation framework is updated, it is divided into three parts: an unaffected, an affected, and a conditioning part. The status of arguments in the unaffected sub-framework remains unchanged, while the status of the affected arguments is computed in a special argumentation framework (called a conditioned argumentation framework, or briefly CAF) that is composed of an affected part and a conditioning part. We have proved that under a certain semantics that satisfies the directionality criterion (complete, preferred, ideal, or grounded semantics), the extensions of the updated framework are equal to the result of a combination of the extensions of an unaffected sub-framework and sets of the extensions of a set of assigned CAFs. The theory shows that the complexity of computing the dynamics of argumentation will decrease to a lesser or greater extent, depending on the types of argumentation semantics, the topologies of argumentation frameworks, and the number of affected arguments with respect to an addition or a deletion. As a result, this theory is expected to be very useful in various kinds of argumentation systems where arguments and attacks are dynamics, due to the changing of underlying knowledge and information.

Abstract. n² x n² Sudoku puzzles can be straightforwardly encoded as SAT problems. However, solving such puzzles for large n requires a significant amount of optimization. We present some ideas for reducing the number of clauses, for improving the encoding, and for the selection of suitable SAT solvers.

Abstract. In a recent paper, Baumann et al. provided a comprehensive framework for default reasoning in action theories. Yet, the approach was only defined for a very basic class of domains where all actions have only unconditional, local effects. In this paper, we show that the framework can be substantially extended to domains with action effects that are conditional (i.e. are context-sensitive to the state in which they are applied) and non-local (i.e. the range of effects is not pre-determined by the action arguments). Notably, these features can be carefully added without sacrificing important nice properties of the basic framework, such as modularity of domain specifications or the existence of default extensions. In the last part of the paper, we demonstrate how (a subclass of) the framework can be straightforwardly implemented using the answer set programming paradigm.