Abstract: Daniel Neider, Shambwaditya Saha, P. Madhusudan
We present a novel general technique that uses classifier learning to synthesize piece-wise functions (functions that split the domain into regions and apply simpler functions to each region) against logical synthesis specifications. Our framework works by combining a synthesizer of functions for fixed concrete inputs and a synthesizer of predicates that can be used to define regions. We develop a theory of single-point refutable specifications that facilitate generating concrete counterexamples using constraint solvers. We implement the framework for synthesizing piece-wise functions in linear integer arithmetic, combining leaf expression synthesis using constraint-solving with predicate synthesis using enumeration, and tie them together using a decision tree classifier. PubDate: Fri, 11 May 2018 00:00:00 GMT
Abstract: Sebastian Binnewies, Zhiqiang Zhuang, Kewen Wang, Bela Stantic
Recent methods have adapted the well-established AGM and belief base frameworks for belief change to cover belief revision in logic programs. In this study here, we present two new sets of belief change operators for logic programs. They focus on preserving the explicit relationships expressed in the rules of a program, a feature that is missing in purely semantic approaches that consider programs only in their entirety. In particular, operators of the latter class fail to satisfy preservation and support, two important properties for belief change in logic programs required to ensure intuitive results. We address this shortcoming of existing approaches by introducing partial meet and ensconcement constructions for logic program belief change, which allow us to define syntax-preserving operators for satisfying preservation and support. PubDate: Fri, 11 May 2018 00:00:00 GMT
Abstract: Zhé Hóu, Ranald Clouston, Rajeev Goré, Alwen Tiu
separation logics are a family of extensions of Hoare logic for reasoning about programs that manipulate resources such as memory locations. These logics are “abstract” because they are independent of any particular concrete resource model. Their assertion languages, called Propositional Separation Logics (PASLs), extend the logic of (Boolean) Bunched Implications (BBI) in various ways. In particular, these logics contain the connectives * and –*, denoting the composition and extension of resources, respectively. This added expressive power comes at a price, since the resulting logics are all undecidable. Given their wide applicability, even a semi-decision procedure for these logics is desirable. PubDate: Sat, 28 Apr 2018 00:00:00 GMT
We define a bi-directional embedding between hypersequent calculi and a subclass of systems of rules (2-systems). In addition to showing that the two proof frameworks have the same expressive power, the embedding allows for the recovery of the benefits of locality for 2-systems, analyticity results for a large class of such systems, and a rewriting of hypersequent rules as natural deduction rules. PubDate: Mon, 02 Apr 2018 00:00:00 GMT
Choiceless Polynomial Time (CPT) is one of the most promising candidates in the search for a logic capturing Ptime. The question whether there is a logic that expresses exactly the polynomial-time computable properties of finite structures, which has been open for more than 30 years, is one of the most important and challenging problems in finite model theory. The strength of Choiceless Polynomial Time is its ability to perform isomorphism-invariant computations over structures, using hereditarily finite sets as data structures. But, because of isomorphism-invariance, it is choiceless in the sense that it cannot select an arbitrary element of a set—an operation that is crucial for many classical algorithms. PubDate: Fri, 09 Feb 2018 00:00:00 GMT
We consider extensions of the two-variable guarded fragment, GF2, where distinguished binary predicates that occur only in guards are required to be interpreted in a special way (as transitive relations, equivalence relations, preorders, or partial orders). We prove that the only fragment that retains the finite (exponential) model property is GF2 with equivalence guards without equality. For remaining fragments, we show that the size of a minimal finite model is at most doubly exponential. To obtain the result, we invent a strategy of building finite models that are formed from a number of multidimensional grids placed over a cylindrical surface. The construction yields a 2-NExpTime upper bound on the complexity of the finite satisfiability problem for these fragments. PubDate: Fri, 09 Feb 2018 00:00:00 GMT
Hybrid journal (It can contain Open Access articles)
[45 journals]
