An important problem in agent verification is a lack of proper understanding of the relation between agent programs on the one hand and agent logics on the other. Understanding this relation would help to establish th...
详细信息
An important problem in agent verification is a lack of proper understanding of the relation between agent programs on the one hand and agent logics on the other. Understanding this relation would help to establish that an agent programming language is both conceptually well-founded and well-behaved, as well as yield a way to reason about agent programs by means of agent logics. As a step toward bridging this gap, we study several issues that need to be resolved in order to establish a precise mathematical relation between a modal agent logic and an agent programming language specified by means of an operational semantics. In this paper, we present an agent programming theory that provides both an agent programming language as well as a corresponding agent verification logic to verify agent programs. The theory is developed in stages to show, first, how a modal semantics can be grounded in a state-based semantics, and, second, how denotational semantics can be used to define the mathematical relation connecting the logic and agent programming language. Additionally, it is shown how to integrate declarative goals and add precompiled plans to the programming theory. In particular, we discuss the use of the concept of higher-order goals in our theory. Other issues such as a complete axiomatization and the complexity of decision procedures for the verification logic are not the focus of this paper and remain for future investigation.
There are two kinds of systems that programming language researchers use for their work. Semantics engineering tools let them interactively explore their definitions, while proof assistants can be used to check the pr...
详细信息
Despite being a quintessential example of a hard problem, the quest for finding fast algorithms for deciding satisfiability of propositional formulas has occupied computer scientists both in theory and in practice. In...
详细信息
Despite being a quintessential example of a hard problem, the quest for finding fast algorithms for deciding satisfiability of propositional formulas has occupied computer scientists both in theory and in practice. In this article, we survey recent progress on designing algorithms with strong refutation guarantees for smoothed instances of the k-SAT problem. Smoothed instances are formed by slight random perturbations of arbitrary instances, and their study is a way to bridge the gap between worst-case and average-case models of problem instances. Our methods yield new algorithms for smoothed k-SAT instances with guarantees that match those for the significantly simpler and well-studied model of random formulas. Additionally, they have led to a novel and unexpected line of attack on some long-standing extremal combinatorial problems in graph theory and coding theory. As an example, we will discuss the resolution of a 2008 conjecture of Feige on the existence of short cycles in hypergraphs.
This paper presents the main concepts of the mathematical theory PEI for parallel programming and emphasizes its derivation power. The mathematical basis of this theory leads to a nice implementation in CENTAUR of an ...
详细信息
This paper presents the main concepts of the mathematical theory PEI for parallel programming and emphasizes its derivation power. The mathematical basis of this theory leads to a nice implementation in CENTAUR of an environment whose purpose is to transform parallel programs. It is illustrated by two similar examples: the convolution sum and the Dirichlet product. The second one uses non-affine dependencies that can be easily taken into account using PEI.
We scale layered modal type theory to dependent types, introducing DeLaM, dependent layered modal type theory. This type theory is novel in that we have one uniform type theory in which we can not only compose and exe...
详细信息
We design an Interactive Oracle Proof of Proximity (IOPP) for codes on graphs inspired by the FRI protocol. The soundness is significantly improved compared to the FRI, the complexity parameters are comparable, and th...
详细信息
We present a proposal for increasing the accessibility of formal methods to the large number of students who could benefit from it but may not be well-served by traditional introductions. Several principles drive our ...
详细信息
Let nq(M, d) be the minimum length of a q-ary code of size M and minimum distance d. Bounding nq(M, d) is a fundamental problem that lies at the heart of coding theory. This work considers a generalization n‚q(M, d) o...
详细信息
We show that there are recursive sets two-variable simple programs cannot recognize. Examples include the set of prime numbers and the set L(e) of integers raised to the eth power for any fixed integer e greater-than-...
详细信息
We show that there are recursive sets two-variable simple programs cannot recognize. Examples include the set of prime numbers and the set L(e) of integers raised to the eth power for any fixed integer e greater-than-or-equal-to 2.
Some of the basic results in the theory of logic programming, e.g. the mgu lemma, lifting lemma and completeness theorem, have been incorrectly stated in standard texts. We explain how these errors arise and how they ...
详细信息
Some of the basic results in the theory of logic programming, e.g. the mgu lemma, lifting lemma and completeness theorem, have been incorrectly stated in standard texts. We explain how these errors arise and how they may be avoided by suitable ''standardising apart'' of the program clauses used. We also discuss the significance of standardising apart for other purposes, e.g. soundness, obtaining most general answer.
暂无评论