The Experts below are selected from a list of 2478 Experts worldwide ranked by ideXlab platform
Makoto Tatsuta - One of the best experts on this subject based on the ideXlab platform.
-
Realizability interpretation of coinductive definitions and program synthesis with streams
Theoretical Computer Science, 1994Co-Authors: Makoto TatsutaAbstract:Abstract The main aim of the paper is to construct a logical system in which properties of programs can be formalized for verification, synthesis and transformation. The paper has two main Points. One Point is a realizability interpretation of coinductive definitions of predicates. The other Point is extraction of programs which treat streams. An untyped predicative theory TIDv is presented, which has the facility of coinductive definitions of predicates and is based on constructive logic. Properties defined by the Greatest Fixed Point, such as streams and the extensional equality of streams, can be formalized by the facility of coinductive definitions of predicates in TIDv. A q-realizability interpretation for TIDv is defined and the soundness of the interpretation is proved. By the realizability interpretation, a program which treats streams can be extracted from a proof of its specification in TIDv. A general program extraction theorem and a stream program extraction theorem are presented.
-
FGCS - Realizability Interpretation of Coinductive Definitions and Program Synthesis with Streams.
Future Generation Computer Systems, 1992Co-Authors: Makoto TatsutaAbstract:Abstract The main aim of the paper is to construct a logical system in which properties of programs can be formalized for verification, synthesis and transformation. The paper has two main Points. One Point is a realizability interpretation of coinductive definitions of predicates. The other Point is extraction of programs which treat streams. An untyped predicative theory TIDv is presented, which has the facility of coinductive definitions of predicates and is based on constructive logic. Properties defined by the Greatest Fixed Point, such as streams and the extensional equality of streams, can be formalized by the facility of coinductive definitions of predicates in TIDv. A q-realizability interpretation for TIDv is defined and the soundness of the interpretation is proved. By the realizability interpretation, a program which treats streams can be extracted from a proof of its specification in TIDv. A general program extraction theorem and a stream program extraction theorem are presented.
Brigitte Pientka - One of the best experts on this subject based on the ideXlab platform.
-
Fair reactive programming
ACM SIGPLAN Notices, 2014Co-Authors: Andrew Cave, Francisco Ferreira, Prakash Panangaden, Brigitte PientkaAbstract:Functional Reactive Programming (FRP) models reactive systems with events and signals, which have previously been observed to correspond to the "eventually" and "always" modalities of linear temporal logic (LTL). In this paper, we define a constructive variant of LTL with least Fixed Point and Greatest Fixed Point operators in the spirit of the modal mu-calculus, and give it a proofs-as-programs interpretation as a foundational calculus for reactive programs. Previous work emphasized the propositions-as-types part of the correspondence between LTL and FRP; here we emphasize the proofs-as-programs part by employing structural proof theory. We show that the type system is expressive enough to enforce liveness properties such as the fairness of schedulers and the eventual delivery of results. We illustrate programming in this calculus using (co)iteration operators. We prove type preservation of our operational semantics, which guarantees that our programs are causal. We give also a proof of strong normalization which provides justification that our programs are productive and that they satisfy liveness properties derived from their types.
-
POPL - Fair reactive programming
Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2014Co-Authors: Andrew Cave, Francisco Ferreira, Prakash Panangaden, Brigitte PientkaAbstract:Functional Reactive Programming (FRP) models reactive systems with events and signals, which have previously been observed to correspond to the "eventually" and "always" modalities of linear temporal logic (LTL). In this paper, we define a constructive variant of LTL with least Fixed Point and Greatest Fixed Point operators in the spirit of the modal mu-calculus, and give it a proofs-as-programs interpretation as a foundational calculus for reactive programs. Previous work emphasized the propositions-as-types part of the correspondence between LTL and FRP; here we emphasize the proofs-as-programs part by employing structural proof theory. We show that the type system is expressive enough to enforce liveness properties such as the fairness of schedulers and the eventual delivery of results. We illustrate programming in this calculus using (co)iteration operators. We prove type preservation of our operational semantics, which guarantees that our programs are causal. We give also a proof of strong normalization which provides justification that our programs are productive and that they satisfy liveness properties derived from their types.
Guoqing Chen - One of the best experts on this subject based on the ideXlab platform.
-
A Behavioral Distance for Fuzzy-Transition Systems
IEEE Transactions on Fuzzy Systems, 2013Co-Authors: Huaiqing Wang, Guoqing ChenAbstract:In contrast with the existing approaches to exact bisimulation for fuzzy systems, we introduce a robust notion of behavioral distance to measure the behavioral similarity of nondeterministic fuzzy-transition systems which are a generalization of fuzzy automata. This behavioral distance provides a quantitative analogue of bisimilarity and is defined as the Greatest Fixed Point of a suitable monotonic function. The behavioral distance has the important property that two systems are at zero distance if and only if they are bisimilar. Moreover, for any given threshold, we find that systems with behavioral distances bounded by the threshold are equivalent. In addition, we show that two system combinators-parallel composition and product-are nonexpansive with respect to our behavioral distance, which makes compositional verification possible. The theory developed here is applicable to the quantitative verification, approximate reduction, and reliability analysis of fuzzy-transition systems.
-
A Behavioral Distance for Fuzzy-Transition Systems
arXiv: Artificial Intelligence, 2011Co-Authors: Yongzhi Cao, Huaiqing Wang, Sherry X. Sun, Guoqing ChenAbstract:In contrast to the existing approaches to bisimulation for fuzzy systems, we introduce a behavioral distance to measure the behavioral similarity of states in a nondeterministic fuzzy-transition system. This behavioral distance is defined as the Greatest Fixed Point of a suitable monotonic function and provides a quantitative analogue of bisimilarity. The behavioral distance has the important property that two states are at zero distance if and only if they are bisimilar. Moreover, for any given threshold, we find that states with behavioral distances bounded by the threshold are equivalent. In addition, we show that two system combinators---parallel composition and product---are non-expansive with respect to our behavioral distance, which makes compositional verification possible.
Andrew Cave - One of the best experts on this subject based on the ideXlab platform.
-
Fair reactive programming
ACM SIGPLAN Notices, 2014Co-Authors: Andrew Cave, Francisco Ferreira, Prakash Panangaden, Brigitte PientkaAbstract:Functional Reactive Programming (FRP) models reactive systems with events and signals, which have previously been observed to correspond to the "eventually" and "always" modalities of linear temporal logic (LTL). In this paper, we define a constructive variant of LTL with least Fixed Point and Greatest Fixed Point operators in the spirit of the modal mu-calculus, and give it a proofs-as-programs interpretation as a foundational calculus for reactive programs. Previous work emphasized the propositions-as-types part of the correspondence between LTL and FRP; here we emphasize the proofs-as-programs part by employing structural proof theory. We show that the type system is expressive enough to enforce liveness properties such as the fairness of schedulers and the eventual delivery of results. We illustrate programming in this calculus using (co)iteration operators. We prove type preservation of our operational semantics, which guarantees that our programs are causal. We give also a proof of strong normalization which provides justification that our programs are productive and that they satisfy liveness properties derived from their types.
-
POPL - Fair reactive programming
Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2014Co-Authors: Andrew Cave, Francisco Ferreira, Prakash Panangaden, Brigitte PientkaAbstract:Functional Reactive Programming (FRP) models reactive systems with events and signals, which have previously been observed to correspond to the "eventually" and "always" modalities of linear temporal logic (LTL). In this paper, we define a constructive variant of LTL with least Fixed Point and Greatest Fixed Point operators in the spirit of the modal mu-calculus, and give it a proofs-as-programs interpretation as a foundational calculus for reactive programs. Previous work emphasized the propositions-as-types part of the correspondence between LTL and FRP; here we emphasize the proofs-as-programs part by employing structural proof theory. We show that the type system is expressive enough to enforce liveness properties such as the fairness of schedulers and the eventual delivery of results. We illustrate programming in this calculus using (co)iteration operators. We prove type preservation of our operational semantics, which guarantees that our programs are causal. We give also a proof of strong normalization which provides justification that our programs are productive and that they satisfy liveness properties derived from their types.
Gopal Gupta - One of the best experts on this subject based on the ideXlab platform.
-
FLOPS - Coinductive constraint logic programming
Functional and Logic Programming, 2012Co-Authors: Neda Saeedloei, Gopal GuptaAbstract:Constraint logic programming (CLP) has been proposed as a declarative paradigm for merging constraint solving and logic programming. Recently, coinductive logic programming has been proposed as a powerful extension of logic programming for handling (rational) infinite objects and reasoning about their properties. Coinductive logic programming does not include constraints while CLP's declarative semantics is given in terms of a least Fixed-Point (i.e., it is inductive) and cannot directly support reasoning about (rational) infinite objects and their properties. In this paper we combine constraint logic programming and coinduction to obtain co-constraint logic programming (co-CLP for brevity). We present the declarative semantics of co-CLP in terms of a Greatest Fixed-Point and its operational semantics based on the coinductive hypothesis rule . We prove the equivalence of these two semantics for programs with rational terms.
-
coinductive logic programming and its applications
International Conference on Logic Programming, 2007Co-Authors: Gopal Gupta, Luke Simon, Ajay Bansal, Richard Min, Ajay MallyaAbstract:Coinduction has recently been introduced as a powerful technique for reasoning about unfounded sets, unbounded structures, and interactive computations. Where induction corresponds to least Fixed Point semantics, coinduction corresponds to Greatest Fixed Point semantics. In this paper we discuss the introduction of coinduction into logic programming. We discuss applications of coinductive logic programming to verification and model checking, lazy evaluation, concurrent logic programming and non-monotonic reasoning.
-
Coinductive logic programming
Lecture Notes in Computer Science, 2006Co-Authors: Luke Simon, Ajay Bansal, Ajay Mallya, Gopal GuptaAbstract:We extend logic programming's semantics with the semantic dual of traditional Herbrand semantics by using Greatest Fixed-Points in place of least Fixed-Points. Executing a logic program then involves using coinduction to check inclusion in the Greatest Fixed-Point. The resulting coinductive logic programming language is syntactically identical to, yet semantically subsumes logic programming with rational terms and lazy evaluation. We present a novel formal operational semantics that is based on synthesizing a coinductive hypothesis for this coinductive logic programming language. We prove that this new operational semantics is equivalent to the declarative semantics. Our operational semantics lends itself to an elegant and efficient goal directed proof search in the presence of rational terms and proofs. We describe a prototype implementation of this operational semantics along with applications of coinductive logic programming.
-
ICLP - Coinductive logic programming
Logic Programming, 2006Co-Authors: Luke Simon, Ajay Bansal, Ajay Mallya, Gopal GuptaAbstract:We extend logic programming’s semantics with the semantic dual of traditional Herbrand semantics by using Greatest Fixed-Points in place of least Fixed-Points. Executing a logic program then involves using coinduction to check inclusion in the Greatest Fixed-Point. The resulting coinductive logic programming language is syntactically identical to, yet semantically subsumes logic programming with rational terms and lazy evaluation. We present a novel formal operational semantics that is based on synthesizing a coinductive hypothesis for this coinductive logic programming language. We prove that this new operational semantics is equivalent to the declarative semantics. Our operational semantics lends itself to an elegant and efficient goal directed proof search in the presence of rational terms and proofs. We describe a prototype implementation of this operational semantics along with applications of coinductive logic programming.
-
Extending logic programming with coinduction
2006Co-Authors: Gopal Gupta, Luke SimonAbstract:Traditional logic programming, with its minimal Herbrand model semantics, is useful for declaratively defining finite data structures and properties. A program in traditional logic programming defines a set of inference rules that can be used to automatically construct proofs of various logical statements. The fact that logic programming also has a goal directed, top-down operational semantics, means that these proofs can efficiently be constructed by "executing" the logical statement that is to be proved. However, since traditional logic programming's declarative semantics is given in terms of a least Fixed-Point, that is, since logic programming's semantics is inductive, it is impossible to directly reason about infinite objects and properties. In programming language terms, this means that the language cannot make use of infinite data structures and corecursion. The contribution of this dissertation is the extension of traditional logic programming with coinduction, by invoking the principle of duality on the declarative semantics of traditional logic programming and by developing an efficient top-down, goal-directed procedure based on the principle of coinduction, for deciding inclusion of a logical statement in the Greatest Fixed-Point model. This gives rise to a new field of programming languages referred to by this author as "co-logic programming".
