We study the decidability of termination for two CH R dialects which, similarly to the Datalog like languages, are defined by using a signature which does not allow function symbols (of arity > 0). Both languages a...
详细信息
We study the decidability of termination for two CH R dialects which, similarly to the Datalog like languages, are defined by using a signature which does not allow function symbols (of arity > 0). Both languages allow the use of the = built-in in the body of rules, thus are built on a host language that supports unification. However each imposes one further restriction. The first CHR dialect allows only range-restricted rules, that is, it does not allow the use of variables in the body or in the guard of a rule if they do not appear in the head. We show that the existence of an infinite computation is decidable for this dialect. The second dialect instead limits the number of atoms in the head of rules to one. We prove that in this case, the existence of a terminating computation is decidable. These results show that both dialects are strictly less expressive(1) than Turing Machines. It is worth noting that the language (without function symbols) without these restrictions is as expressive as Turing Machines.
Flow logic is an approach to the static analysis of programs that has been developed for functional, imperative and object-oriented programming languages and for concurrent, distributed, mobile and cryptographic proce...
详细信息
ISBN:
(纸本)9783642120312
Flow logic is an approach to the static analysis of programs that has been developed for functional, imperative and object-oriented programming languages and for concurrent, distributed, mobile and cryptographic process calculi. In this paper we extend it;to deal with modal logics and prove that it can give an exact characterisation of the semantics of formulae in a modal logic. This shows that model checking can be performed by means of state-of-the-art approaches to static analysis and allow us to conclude that the problems of model checking and static analysis are reducible to each other. In terms of computational complexity we show that model checking by means of static analysis gives the same complexity bounds as are known for traditional approaches to model checking.
Inductive logicprogramming (ILP) [12] is concerned with the induction of theories from specific examples and background knowledge, using first-order logic representations for all the three ingredients. In its early d...
详细信息
The proceedings contain 32 papers. The topics discussed include: the audacity of hope: thoughts on reclaiming the database dream;dynamic boundaries: information hiding by second order framing with first order assertio...
ISBN:
(纸本)3642119565
The proceedings contain 32 papers. The topics discussed include: the audacity of hope: thoughts on reclaiming the database dream;dynamic boundaries: information hiding by second order framing with first order assertions;coupling policy iteration with semi-definite relaxation to compute accurate numerical invariants in static analysis;precise and automated contract-based reasoning for verification and certification of information flow properties of programs with arrays;a semantic framework for declassification and endorsement;a polytime functional language from light linear logic;formal verification of coalescing graph-coloring register allocation;a theory of speculative computation;propositional interpolation and abstract interpretation;functional programming in sublinear space;logical concurrency control from sequential proofs;and amortized resource analysis with polynomial potential: a static inference of polynomial bounds for functional programs.
Why did it take us 50 years since the birth of the quantum mechanical formalism to discover that unknown quantum states cannot be cloned? Yet, the proof of the 'no-cloning theorem' is easy, and its consequence...
详细信息
Why did it take us 50 years since the birth of the quantum mechanical formalism to discover that unknown quantum states cannot be cloned? Yet, the proof of the 'no-cloning theorem' is easy, and its consequences and potential for applications are immense. Similarly, why did it take us 60 years to discover the conceptually intriguing and easily derivable physical phenomenon of 'quantum teleportation'? We claim that the quantum mechanical formalism doesn't support our intuition, nor does it elucidate the key concepts that govern the behaviour of the entities that are subject to the laws of quantum physics. The arrays of complex numbers are kin to the arrays of 0s and 1s of the early days of computer programmingpractice. Using a technical term from computer science, the quantum mechanical formalism is 'low-level'. In this review we present steps towards a diagrammatic 'high-level' alternative for the Hilbert space formalism, one which appeals to our intuition. The diagrammatic language as it currently stands allows for intuitive reasoning about interacting quantum systems, and trivialises many otherwise involved and tedious computations. It clearly exposes limitations such as the no-cloning theorem, and phenomena such as quantum teleportation. As a logic, it supports 'automation': it enables a (classical) computer to reason about interacting quantum systems, prove theorems, and design protocols. It allows for a wider variety of underlying theories, and can be easily modified, having the potential to provide the required step-stone towards a deeper conceptual understanding of quantum theory, as well as its unification with other physical theories. Specific applications discussed here are purely diagrammatic proofs of several quantum computational schemes, as well as an analysis of the structural origin of quantum non-locality. The underlying mathematical foundation of this high-level diagrammatic formalism relies on so-called monoidal categories, a product of a fairly r
The proceedings contain 16 papers. The special focus in this conference is on Rewriting logic and its Applications. The topics include: A Formal Pattern Architecture for Safe Medical Systems;on the Behavioral Semantic...
ISBN:
(纸本)9783642163098
The proceedings contain 16 papers. The special focus in this conference is on Rewriting logic and its Applications. The topics include: A Formal Pattern Architecture for Safe Medical Systems;on the Behavioral Semantics of Real-Time Domain Specific Visual Languages;multiset Rewriting: A Semantic Framework for Concurrency with Name Binding;the Linear Temporal logic of Rewriting Maude Model Checker;enhancing the Debugging of Maude Specifications;the Third Rewrite Engines Competition;twenty Years of Rewriting logic;proving Termination in the Context-Sensitive Dependency Pair Framework;a Dependency Pair Framework for A ∨ C-Termination;folding Variant Narrowing and Optimal Variant Termination;a Church-Rosser Checker Tool for Conditional Order-Sorted Equational Maude Specifications;a Maude Coherence Checker Tool for Conditional Order-Sorted Rewrite Theories;k-Maude: A Rewriting Based Tool for Semantics of programming Languages;collecting Semantics under Predicate Abstraction in the K Framework.
This paper describes a compositional analysis algorithm for statically detecting leaks in Java programs. The algorithm is based on separation logic and exploits the concept of bi-abductive inference for identifying th...
详细信息
ISBN:
(数字)9783642120299
ISBN:
(纸本)9783642120282
This paper describes a compositional analysis algorithm for statically detecting leaks in Java programs. The algorithm is based on separation logic and exploits the concept of bi-abductive inference for identifying the objects which are reachable but no longer used by the program.
One of the central goals of programming-language research is to develop mathematically sound formal methods for precisely specifying and reasoning about the behavior of programs. However, just as software developers s...
One of the central goals of programming-language research is to develop mathematically sound formal methods for precisely specifying and reasoning about the behavior of programs. However, just as software developers sometimes make mistakes when programming, researchers sometimes make mistakes when proving that a formal method is mathematically sound. As the field of programming-language research has grown, these proofs have become larger and more complex, and thus harder to verify on paper. This phenomenon has motivated a great deal of research into the development of logical systems that provide an automated means to apply—and verify the application of—trusted reasoning principles to concrete proofs. The boundary between trusted and untrusted reasoning principles is inherently blurry, and different researchers draw the line in different places. However, just as certain principles are widely recognized to allow the proofs of contradictory statements, others are so uncontroversially ubiquitous in practice that they can be considered beyond reproach. We posit the following questions: (1) what are these principles and (2) how much can we do with them? Although neither has an uncontroversial answer, in this dissertation we propose an answer to the former by describing a philosophical viewpoint we refer to as syntactic finitism, in which the principles of case analysis and structural induction on abstract syntax are viewed as being a priori justified. We explore the latter question using some of the ideas and results from proof theory; along the way, we provide a syntactically finitary account of proofs by logical relations, and investigate the consequences of replacing structural induction with well-founded induction on the lexicographic path ordering from term rewriting theory. Finally, we argue that syntactically finitary proofs can be formalized in the proofs as logic programs paradigm popularized by the proof assistant Twelf; we prove the soundness of a modular term
This paper presents a logic language for expressing search and optimization problems. Specifically, first a language obtained by extending (positive) DATALOG with intuitive and efficient constructs (namely, stratifie...
详细信息
This paper presents a logic language for expressing search and optimization problems. Specifically, first a language obtained by extending (positive) DATALOG with intuitive and efficient constructs (namely, stratified negation, constraints, and exclusive disjunction) is introduced. Next, a further restricted language only using a restricted form of disjunction to define (nondeterministically) subsets (or partitions) of relations is investigated. This language, called atalog, captures the power of DATALOG¬ in expressing search and optimization problems. A system prototype implementing atalog is presented. The system translates atalog queries into Optimization programming Language (OPL) programs which are executed by the ILOG OPL Development Studio. Our proposal combines easy formulation of problems, expressed by means of a declarative logic language, with the efficiency of the ILOG System. Several experiments show the effectiveness of this approach.
We review the Italian contribution to proof-theoretic and higher-order extensions of logicprogramming;this originated from the realization that Horn clauses lacked standard abstraction mechanisms such as higher-order...
详细信息
暂无评论