Guarded Interaction Trees are a structure and a fully formalized framework for representing higher-order computations with higher-order effects in Coq. We present an extension of Guarded Interaction Trees to supp...
详细信息
Concurrent randomized programs in the oblivious adversary model are extremely difficult for modular verification because the interaction between threads is very sensitive to the program structure and the exe...
详细信息
We study the relationship between two approaches to higher-order program verification: a semi-automated method using Dijkstra monads and a fully automated method using a higher-order fixpoint logic called HFL(Z). Alth...
详细信息
A central challenge in mechanizing the meta-theory of substructural languages is modeling contexts. Although various ad hoc approaches to this problem exist, we lack a set of good practices and a simple infrastructure...
详细信息
ISBN:
(纸本)9798400713477
A central challenge in mechanizing the meta-theory of substructural languages is modeling contexts. Although various ad hoc approaches to this problem exist, we lack a set of good practices and a simple infrastructure that can be leveraged for mechanizing a wide range of substructural systems. In this work, we describe Contexts as Resource Vectors (CARVe), a general syntactic infrastructure for managing substructural contexts, where elements are annotated with tags from a resource algebra denoting their availability. Assumptions persist as contexts are manipulated since we model resource consumption by changing their tags. We may thus define relations between substructural contexts via simultaneous substitutions without the need to split them. Moreover, we establish a series of algebraic properties about context operations that are typically required to carry out proofs in practice. CARVe is implemented in the proof assistant Beluga. To illustrate best practices for using our infrastructure, we give a detailed reformulation of the linear sequent calculus and bidirectional linear lambda-calculus in terms of CARVe's context operations and prove their equivalence using the aforementioned algebraic properties. In addition, we apply CARVe to mechanize a diverse set of systems, from the affine lambda-calculus to the session-typed process calculus CP, giving us confidence that CARVe is sufficiently general to mechanize a broad range of substructural systems.
DLV2 is an AI tool for knowledge representation and reasoning that supports answer set programming (ASP) - a logic-based declarative formalism, successfully used in both academic and industrial applications. Given a l...
详细信息
DLV2 is an AI tool for knowledge representation and reasoning that supports answer set programming (ASP) - a logic-based declarative formalism, successfully used in both academic and industrial applications. Given a logic program modeling a computational problem, an execution of DLV2 produces the so-called answer sets that correspond one-to-one to the solutions to the problem at hand. The computational process of DLV2 relies on the typical ground & solve approach, where the grounding step transforms the input program into a new, equivalent ground program, and the subsequent solving step applies propositional algorithms to search for the answer sets. Recently, emerging applications in contexts such as stream reasoning and event processing created a demand for multi-shot reasoning: here, the system is expected to be reactive while repeatedly executed over rapidly changing data. In this work, we present a new incremental reasoner obtained from the evolution of DLV2 toward iterated reasoning. Rather than restarting the computation from scratch, the system remains alive across repeated shots, and it incrementally handles the internal grounding process. At each shot, the system reuses previous computations for building and maintaining a large, more general ground program, from which a smaller yet equivalent portion is determined and used for computing answer sets. Notably, the incremental process is performed in a completely transparent fashion for the user. We describe the system, its usage, its applicability, and performance in some practically relevant domains.
Biabduction-based shape analysis is a compositional verification and analysis technique that can prove memory safety in the presence of complex, linked data structures. Despite its usefulness, several open proble...
详细信息
Processing programs as data is one of the successes of functional and logicprogramming. Higher-order functions, as program-processing programs are called in functional programming, and meta-programs, as they are call...
详细信息
Processing programs as data is one of the successes of functional and logicprogramming. Higher-order functions, as program-processing programs are called in functional programming, and meta-programs, as they are called in logicprogramming, are widespread declarative programming techniques. In logicprogramming, there is a gap between the meta-programmingpractice and its theory: The formalizations of meta-programming do not explicitly address its impredicativity and are not fully adequate. This article aims at overcoming this unsatisfactory situation by discussing the relevance of impredicativity to meta-programming, by revisiting former formalizations of meta-programming, and by defining Reflective Predicate logic, a conservative extension of first-order logic, which provides a simple formalization of meta-programming.
The 30th edition of the International Conference of logicprogramming took place in Vienna in July 2014 at the Vienna Summer of logic - the largest scientific conference in the history of logic. Following the initiati...
The 30th edition of the International Conference of logicprogramming took place in Vienna in July 2014 at the Vienna Summer of logic - the largest scientific conference in the history of logic. Following the initiative in 2010 taken by the Association for logicprogramming and Cambridge University Press, the full papers accepted for the International Conference on logicprogramming again appear as a special issue of theory and practice of logic programming (TPLP) - the 30th International Conference on logicprogramming Special Issue. Papers describing original, previously unpublished research and not simultaneously submitted for publication elsewhere were solicited in all areas of logicprogramming including but not restricted to: theory: Semantic Foundations, Formalisms, Non- monotonic Reasoning, Knowledge Representation; Implementation: Compilation, Memory Management, Virtual Machines, Parallelism; Environments: Program Analysis, Transformation, Validation, Verification, Debugging, Profiling, Testing; Language Issues: Concurrency, Objects, Coordination, Mobility, Higher Order, Types, Modes, Assertions, programming Techniques; Related Paradigms: Abductive logicprogramming, Inductive logicprogramming, Constraint logicprogramming, Answer-Set programming; Applications: Databases, Data Integration and Federation, Software Engineering, Natural Language Processing, Web and Semantic Web, Agents, Artificial Intelligence, Bioinformatics.
Several formal systems, such as resolution and minimal model semantics, provide a framework for logicprogramming. In this article, we will survey the use of structural proof theory as an alternative foundation. Resea...
详细信息
Several formal systems, such as resolution and minimal model semantics, provide a framework for logicprogramming. In this article, we will survey the use of structural proof theory as an alternative foundation. Researchers have been using this foundation for the past 35 years to elevate logicprogramming from its roots in first-order classical logic into higher-order versions of intuitionistic and linear logic. These more expressive logicprogramming languages allow for capturing stateful computations and rich forms of abstractions, including higher-order programming, modularity, and abstract data types. Term-level bindings are another kind of abstraction, and these are given an elegant and direct treatment within both proof theory and these extended logicprogramming languages. logicprogramming has also inspired new results in proof theory, such as those involving polarity and focused proofs. These recent results provide a high-level means for presenting the differences between forward-chaining and backward-chaining style inferences. Anchoring logicprogramming in proof theory has also helped identify its connections and differences with functional programming, deductive databases, and model checking.
This paper looks at logicprogramming with three kinds of negation: default, weak and strict negations. A 3-valued logic model theory is discussed for logic programs with three kinds of negation. The procedure is cons...
详细信息
This paper looks at logicprogramming with three kinds of negation: default, weak and strict negations. A 3-valued logic model theory is discussed for logic programs with three kinds of negation. The procedure is constructed for negations so that a soundness of the procedure is guaranteed in terms of 3-valued logic model theory.
暂无评论