interpretation allows constructing sound static analysis tools by safely approximating program semantics. Frameworks for abstract interpretation typically provide an implementation of a specialized iteration strategy ...
详细信息
ISBN:
(纸本)9783031457838;9783031457845
interpretation allows constructing sound static analysis tools by safely approximating program semantics. Frameworks for abstract interpretation typically provide an implementation of a specialized iteration strategy to compute an abstract fixpoint, as well as a number of abstract domains in order to approximate different program properties. However, the design and implementation of additional domains, as well as their combinations, is eventually necessary to successfully prove arbitrary program properties. We propose a rule-based methodology for rapid design and prototyping of new domains and combining existing ones, with a focus on the analysis of logic programs. We provide several examples for domains combining numerical properties and data types and apply them to proving complex program properties.
Sampling over combinatorial spaces is a fundamental problem in artificial intelligence with a wide variety of applications. Since state-of-the-art techniques heavily rely on heuristics whose rigorous analysis remain b...
详细信息
Sampling over combinatorial spaces is a fundamental problem in artificial intelligence with a wide variety of applications. Since state-of-the-art techniques heavily rely on heuristics whose rigorous analysis remain beyond the reach of current theoretical tools, the past few years have witnessed interest in the design of techniques to test the quality of samplers. The current state-of-the-art techniques, Barbarik and Barbarik2, focus on the cases where combinatorial spaces are encoded as Conjunctive Normal Form (CNF) formulas. While CNF is a general-purpose form, often techniques rely on exploiting specific representations to achieve speedup. Of particular interest are Horn clauses, which form the basis of the logic programming tools in AI. In this context, a natural question is whether it is possible to design a tester that can determine the correctness of a given Horn sampler. The primary contribution of this paper is an affirmative answer to the above question. We design the first tester, Flash, which tests the correctness of a given Horn sampler: given a specific distribution I and parameters eta, epsilon, and delta, the tester Flash correctly (with probability at least 1 -delta) distinguishes whether the underlying distribution of the Horn-sampler is "epsilon-close" to I or "eta-far" from I by sampling only (O) over tilde (tilt(3) /(eta -epsilon)(4)) samples from the Hornsampler, where the tilt is the ratio of the maximum and the minimum (non-zero) probability masses of I. We also provide a prototype implementation of Flash and test three state-of-the-art samplers on a set of benchmarks.
We present Rhyme, an expressive language designed for high-level data manipulation, with a primary focus on querying and transforming nested structures such as JSON and tensors, while yielding nested structures as out...
详细信息
ISBN:
(纸本)9783031520372;9783031520389
We present Rhyme, an expressive language designed for high-level data manipulation, with a primary focus on querying and transforming nested structures such as JSON and tensors, while yielding nested structures as output. Rhyme draws inspiration from a diverse range of declarative languages, including Datalog, JQ, JSONiq, Einstein summation (Einsum), GraphQL, and more recent functional logic programming languages like Verse. It has a syntax that closely resembles existing object notation, is compositional, and has the ability to perform query optimization and code generation through the construction of an intermediate representation (IR). Our IR comprises loop-free and branch-free code with program structure implicitly captured via dependencies. To demonstrate Rhyme's versatility, we implement Rhyme in JavaScript (as an embedded DSL) and illustrate its application across various domains, showcasing its ability to express common data manipulation queries, tensor expressions (a la Einsum), and more.
In answer set programming, two groups of rules are considered strongly equivalent if replacing one group by the other within any program does not affect the set of stable models. Jan Heuer has designed and implemented...
详细信息
ISBN:
(纸本)9783031436185;9783031436192
In answer set programming, two groups of rules are considered strongly equivalent if replacing one group by the other within any program does not affect the set of stable models. Jan Heuer has designed and implemented a system that verifies strong equivalence of programs in the ASP language mini-gringo. The design is based on the syntactic transformation tau * that converts mini-gringo programs into first-order formulas. Heuer's assertion about tau * that was supposed to justify this procedure turned out to be incorrect, and in this paper we propose an alternative justification for his algorithm. We show also that if tau * is replaced by the simpler and more natural translation nu then the algorithm will still produce correct results.
This system demonstration presents Nemo, a new logic programming engine with a focus on reliability and performance. Nemo is built for data-centric analytic computations, modelled in a fully declarative Datalog dialec...
详细信息
This system demonstration presents Nemo, a new logic programming engine with a focus on reliability and performance. Nemo is built for data-centric analytic computations, modelled in a fully declarative Datalog dialect. Its scalability for these tasks matches or exceeds that of leading Datalog systems. We demonstrate uses in reasoning with knowledge graphs and ontologies with 10(5)-10(8) input facts, all on a laptop. Nemo is written in Rust and available as a free and open source tool.
Answer-Set programming (ASP) is a popular declarative reasoning and problem solving formalism. Due to the increasing interest in explainability, several explanation approaches have been developed for ASP. However, whi...
详细信息
ISBN:
(纸本)9783031436185;9783031436192
Answer-Set programming (ASP) is a popular declarative reasoning and problem solving formalism. Due to the increasing interest in explainability, several explanation approaches have been developed for ASP. However, while those formalisms are correct and interesting on their own, most are more technical and less oriented towards philosophical or social concepts of explanation. In this work, we study the notion of contrastive explanation, i.e., answering questions of the form "Why P instead of Q?", in the context of ASP. In particular, we are interested in answering why atoms are included in an answer set, whereas others are not. Contrastive explainability has recently become popular due to its strong support from the philosophical, cognitive, and social sciences and its apparent ability to provide explanations that are concise and intuitive for humans. We formally define contrastive explanations for ASP based on counterfactual reasoning about programs. Furthermore, we demonstrate the usefulness of the concept on example applications and give some complexity results. The latter also provide a guideline as to how the explanations can be computed in practice.
When modelling expert knowledge as logic programs, default negation is very useful, but might lead to there being no stable models. Detecting the exact causes of the incoherence in the logic program manually can becom...
详细信息
When modelling expert knowledge as logic programs, default negation is very useful, but might lead to there being no stable models. Detecting the exact causes of the incoherence in the logic program manually can become quite cumbersome, especially in larger programs. Moreover, establishing coherence requires expertise regarding the modelled knowledge as well as technical knowledge about the program and its rules. In this demo, we present the implementation of a workflow that enables knowledge experts to obtain a coherent logic program by modifying it in interaction with a system that explains the causes of the incoherence and provides possible solutions to choose from.
Recently, ABA Learning has been proposed as a form of symbolic machine learning for drawing Assumption-Based Argumentation frameworks from background knowledge and positive and negative examples. We propose a novel me...
详细信息
Recently, ABA Learning has been proposed as a form of symbolic machine learning for drawing Assumption-Based Argumentation frameworks from background knowledge and positive and negative examples. We propose a novel method for implementing ABA Learning using Answer Set programming as a way to help guide Rote Learning and generalisation in ABA Learning.
Communicating Datalog Programs (CDPs) are a distributed computing model grounded on logic programming: networks of nodes perform Datalog-like computations, leveraging on information coming from incoming messages and d...
详细信息
ISBN:
(纸本)9783031450716;9783031450723
Communicating Datalog Programs (CDPs) are a distributed computing model grounded on logic programming: networks of nodes perform Datalog-like computations, leveraging on information coming from incoming messages and databases received from external services. In previous works, the decidability and complexity border of verification for different variants of CDPs was charted. In general, the problem is undecidable, but model-checking of CTL formulas specialized to the data-centric and distributed setting is decidable for CDPs where all data-sources, except the external inputs, are bounded. An intuitive explanation is that "a bounded state is unable to fully take advantage of an unbounded input", a formal justification is missing. However, we note that traditional CDPs have a limited capability of handling external inputs, i.e., they cannot directly compare two successive inputs or messages. Thus, an alternative explanation is that an unbounded data-source does per se not cause undecidability, as long as the CDP cannot compare two successive instances.
This article proposes an approach to the data-aware multi-service application placement problem in Cloud-Edge settings. We propose both declarative programming and a Mixed-Integer Linear programming (MILP) approach to...
详细信息
ISBN:
(纸本)9798350304817
This article proposes an approach to the data-aware multi-service application placement problem in Cloud-Edge settings. We propose both declarative programming and a Mixed-Integer Linear programming (MILP) approach to determine eligible placements that minimise operational costs and reduce the number of used nodes to contain the amount of data transfers. After assessing the performance of both approaches, we reconcile them into a methodology that combines the best of the two worlds by exploiting a declarative pre-processing step to boost the MILP solver while determining optimal solutions. We open-sourced the methodology into a prototype that is 10x faster than pure MILP, determines optimal results, and easily accommodates non-numerical constraints on application placements.
暂无评论