The paper studies reductions of propositional theories in equilibrium logic to logic programs under answer set semantics. Specifically we are concerned with the question of how to transform an arbitrary set of proposi...
详细信息
ISBN:
(纸本)3540307370
The paper studies reductions of propositional theories in equilibrium logic to logic programs under answer set semantics. Specifically we are concerned with the question of how to transform an arbitrary set of propositional formulas into an equivalent logic program and what are the complexity constraints on this process. We want the transformed program to be equivalent in a strong sense so that theory parts can be transformed independent of the wider context in which they might be embedded. It was only recently established [1] that propositional theories are indeed equivalent (in a strong sense) to logic programs. Here this result is extended with the following contributions. (i) We show how to effectively obtain an equivalent program starting from an arbitrary theory. (ii) We show that in general there is no polynomial time transformation if we require the resulting program to share precisely the vocabulary or signature of the initial theory. (iii) Extending previous work we show how polynomial transformations can be achieved if one allows the resulting program to contain new atoms. The program obtained is still in a strong sense equivalent to the original theory, and the answer sets of the theory can be retrieved from it.
Software architecture description languages (ADLs) allow software designers to focus on high level aspects of an application by abstracting from the details of the components that compose architecture. It is precisely...
详细信息
ISBN:
(纸本)0769523617
Software architecture description languages (ADLs) allow software designers to focus on high level aspects of an application by abstracting from the details of the components that compose architecture. It is precisely this abstraction that makes ADLs suitable for verification using model checking techniques. ADLs are, in a way, domain-specific languages for aspects such as coordination and distribution. LfP (Language for Prototyping) is a formal approach for distributed software architectures that is based on RM-ODP and that can be linked to an UML methodology. We propose in this paper a rewriting of the LfP semantics, specified in rewriting logic which is well suited for axiomatization of concurrent languages. Using the Maude system, a high-performance interpreter based on rewriting logic, we illustrate through an example how this rewriting semantics can be exploited for verification aspects related to distributed object interactions.
The integration of powerful partial evaluation methods into practical compilers for logic programs is still far from reality. This is related both to 1) efficiency issues and to 2) the complications of dealing with pr...
详细信息
ISBN:
(纸本)3540266550
The integration of powerful partial evaluation methods into practical compilers for logic programs is still far from reality. This is related both to 1) efficiency issues and to 2) the complications of dealing with practical programs. Regarding efficiency, the most successful unfolding rules used nowadays are based on structural orders applied over (covering) ancestors, i.e., a subsequence of the atoms selected during a derivation. Unfortunately, maintaining the structure of the ancestor relation during unfolding introduces significant overhead. We propose an efficient, practical local unfolding rule based on the notion of covering ancestors which can be used in combination with any structural order and allows a stack-based implementation without losing any opportunities for specialization. Regarding the second issue, we propose assertion-based techniques which allow our approach to deal with real programs that include (Prolog) built-ins and external predicates in a very extensible manner. Finally, we report on our implementation of these techniques in a practical partial evaluator, embedded in a state of the art compiler which uses global analysis extensively (the Ciao compiler and, specifically, its preprocessor CiaoPP). The performance analysis of the resulting system shows that our techniques, in addition to dealing with practical programs, are also significantly more efficient in time and somewhat more efficient in memory than traditional tree-based implementations.
The Specification Pattern System (SPS) and the Property Specification (Prospec) tool assist a user in generating formal specifications in Linear Temporal logic (LTL), as well as other languages, from property patterns...
详细信息
ISBN:
(纸本)3540281959
The Specification Pattern System (SPS) and the Property Specification (Prospec) tool assist a user in generating formal specifications in Linear Temporal logic (LTL), as well as other languages, from property patterns and scopes. Patterns are high-level abstractions that provide descriptions of common properties, and scopes describe the extent of program execution over which the property holds. The purpose of the work presented in this paper is to verify that the generated LTL formulas match the natural language descriptions, timelines, and traces of computation that describe the pattern and scope. The LTL formulas were verified using the Spin model checker on test cases developed using boundary value analysis and equivalence class testing strategies. A test case is an LTL formula and a sequence of Boolean valuations, The LTL formulas were those generated from SPS and Prospec. The Boolean valuations of propositions in the LTL formula are generated by a deterministic, single-threaded Promela program that was run using the software model-checker Spin. For each pattern, a suite of test cases was. The experiments uncovered several errors in both the SPS-generated and the Prospec-generated formulas.
logic of proofs LP introduced by S. Artemov in 1995 describes properties of proof predicate 't is a proof of F' in the propositional language extended by atoms of the form [t]F. Proof are represented by terms ...
详细信息
logic of proofs LP introduced by S. Artemov in 1995 describes properties of proof predicate 't is a proof of F' in the propositional language extended by atoms of the form [t]F. Proof are represented by terms constructed by three elementary recursive operations on proofs. In order to make the language more expressive we introduce the additional storage predicate with the intended interpretation 'x is a label for F'. It can play the role of syntax encoding, so it is useful for specification of operations that require formula arguments. In this paper we study operations on proofs and labels that can be specified in the extended language. First, we give a formal definition of an operation on proofs and labels. Then, for an arbitrary finite set of operations F the logic LPS(F) is defined. We provide LPS(F) with symbolic semantics and arithmetical semantics. The main result of the paper is the uniform completeness theorem for this family of logics with respect to the both types of semantics.
To verify software and system functionality during the design process of complex SoCs, designers routinely use instruction set simulators (ISSs) as high level processor models. Typically, an ISS needs to simulate bill...
详细信息
ISBN:
(纸本)0780392108
To verify software and system functionality during the design process of complex SoCs, designers routinely use instruction set simulators (ISSs) as high level processor models. Typically, an ISS needs to simulate billions of target instructions to verify a single task of the system in design, which is a very time-consuming process. Therefore, the simulation speed of ISSs has become one important concern of SoC designers. In this paper, we present a new technique to improve the speed of ISSs. Specifically, we focus on the translation of memory addresses between the target memory space and the host memory space. Such translation is performed by 4 hash table in many ISS implementations. To accelerate the translation, we introduce a software cache called translation buffer (TB) to cache the hashing results for quick future access. With properly chosen TB sizes, our implementation effectively exploits the abundant locality inherent in the memory footprints of real-world application programs and greatly reduces the overall address translation overhead. We integrated the technique into three popular ISSs and achieved a 15-32% improvement in simulation speed.
We present a theory of proof denotations in classical propositional logic. The abstract definition is in terms of a semiring of weights, and two concrete instances are explored. With the Boolean semiring we get a theo...
详细信息
ISBN:
(数字)9783540320142
ISBN:
(纸本)3540255931
We present a theory of proof denotations in classical propositional logic. The abstract definition is in terms of a semiring of weights, and two concrete instances are explored. With the Boolean semiring we get a theory of classical proof nets, with a geometric correctness criterion, a sequentialization theorem, and a strongly normalizing cut-elimination procedure. This gives us a "Boolean" category, which is not a poset. With the semiring of natural numbers, we obtain a sound semantics for classical logic, in which fewer proofs are identified. Though a "real" sequentialization theorem is missing, these proof nets have a grip on complexity issues. In both cases the cut elimination procedure is closely related to its equivalent in the calculus of structures.
Constraint Handling Rules is a logical concurrent committed-choice rule-based language. Recently it was shown that the classical union-find algorithm can be implemented in CHR with optimal time complexity. Here we inv...
详细信息
ISBN:
(纸本)354029208X
Constraint Handling Rules is a logical concurrent committed-choice rule-based language. Recently it was shown that the classical union-find algorithm can be implemented in CHR with optimal time complexity. Here we investigate if a parallel implementation of this algorithm is also possible in CHR. The problem is hard for several reasons: Up to now, no parallel computation model for CHR was defined. Tarjan's optimal union-find is known to be hard to parallelize. The paxallel code should be as close as possible to the sequential one. It turns out that confluence analysis of the sequential implementation gives almost all the information needed to parallelize the union-find algorithm under a rather general parallel computation model for CHR.
We observe, that subsumption of clauses (in the language of first order logic), so far understood as a syntactic notion, can also be defined by semantical means. Subsumption is NP-complete and testing subsumption take...
详细信息
ISBN:
(纸本)3540252363
We observe, that subsumption of clauses (in the language of first order logic), so far understood as a syntactic notion, can also be defined by semantical means. Subsumption is NP-complete and testing subsumption takes roughly half of the running time of a typical first order resolution-based theorem prover. We also give some experimental evidence, that replacing syntactic indexing for subsumption by our semantic Monte Carlo technique can, in some situations, significantly decrease the cost of subsumption. testing. Finally, we provide some evidence that a similar semantic idea can be probably successfully used for testing for AC matching, which is another NP-complete problem whose millions of instances are being solved by theorem provers.
ID-logic uses ideas from the field of logic programming to extend second order logic with non-monotone inductive defintions. In this work, we reformulate the semantics of this logic in terms of approximation theory, a...
详细信息
ISBN:
(纸本)3540285385
ID-logic uses ideas from the field of logic programming to extend second order logic with non-monotone inductive defintions. In this work, we reformulate the semantics of this logic in terms of approximation theory, an algebraic theory which generalizes the semantics of several non-monotonic reasoning formalisms. This allows us to apply certain abstract modularity theorems, developed within the framework of approximation theory, to ID-logic. As such, we are able to offer elegant and simple proofs of generalizations of known theorems, m well as some new results.
暂无评论