Tree logic, inherited from ambient logic, is introduced as the formal foundation of related programming language and type systems, In this paper, we introduce recursion into such logic system, which can describe the t...Tree logic, inherited from ambient logic, is introduced as the formal foundation of related programming language and type systems, In this paper, we introduce recursion into such logic system, which can describe the tree data more dearly and concisely. By making a distinction between proposition and predicate, a concise semantics interpretation for our modal logic is given. We also develop a model checking algorithm for the logic without △ operator. The correctness of the algorithm is shown. Such work can be seen as the basis of the semi-structured data processing language and more flexible type system.展开更多
Ambient logics have been proposed to describe properties for mobile agentswhich may evolve over time as well as space. This paper takes a predicate-based approach toextending an ambient logic with recursion, yielding ...Ambient logics have been proposed to describe properties for mobile agentswhich may evolve over time as well as space. This paper takes a predicate-based approach toextending an ambient logic with recursion, yielding a predicate μ-calculus in which fixpointformulas are formed using predicate variables. An algorithm is developed for model checkingfinite-control mobile ambients against formulas of the logic, providing the first decidabilityresult for model checking a spatial logic with recursion.展开更多
Przymusinski extended the notion of stratified logic programs,developed by Apt,Blair and Walker,and by van Gelder,to stratified databases that allow both negative premises and disjunctive consequents.However,he did no...Przymusinski extended the notion of stratified logic programs,developed by Apt,Blair and Walker,and by van Gelder,to stratified databases that allow both negative premises and disjunctive consequents.However,he did not provide a fixpoint theory for such class of databases.On the other hand,although a fixpoint semantics has been developed by Minker and Rajasekar for non-Horn logic programs,it is tantamount to traditional minimal model semantics which is not sufficient to capture the intended meaning of negation in the premises of clauses in stratified databases.In this paper,a fixpoint approach to stratified databases is developed,which corresponds with the perfect model semantics. Moreover,algorithms are proposed for computing the set of perfect models of a stratified database.展开更多
We give two generalizations of Tarski’s fixpoint theorem in the setting of residuated lattices and use them to establish van Emdem-Kowalski’s least fixpoint semantics for residuated lattice-valued logic programs.
This paper investigates the semantics of conditional term rewriting systemswith negation (denoted by EI-CTRS), called constructor-based EI-model se-mantics. The introduction of '≠' in EI-CTRS make EI-CTRS mor...This paper investigates the semantics of conditional term rewriting systemswith negation (denoted by EI-CTRS), called constructor-based EI-model se-mantics. The introduction of '≠' in EI-CTRS make EI-CTRS more difficult tostudy. This is in part because of a failure of EI-CTRS to guarantee that thereexist least Herbrand models in classical logical point of views. The key idea ofEI-model is to explain that 't ≠ s' means that the two concepts representedby t and s respectively actually belong to distinguished basic concepts repre-sented by two constructor-ground terms. We define the concept of EI-model,and show that there exist least Herbrand ELmodels for EI-satisfiable EI-CTRS.From algebraic and logic point of view, we show that there are very strong rea-sons for regarding the least Herbrand EI-models as the intended semantics ofEI-CTRS. According to fixpoint theory, we develop a method to construct leastHerbrand EI-models in a bottom-up manner. Moreover, we discuss soundnessand completeness of EI-rewrite for EI-model semantics.展开更多
The development of the object-oriented paradigm has suffered from the lackof any generally accepted formal foundations for its semantic definition. Toaddress this issue, we propose the development of the logic-based s...The development of the object-oriented paradigm has suffered from the lackof any generally accepted formal foundations for its semantic definition. Toaddress this issue, we propose the development of the logic-based semantics ofthe object-oriented paradigm. By combining the logic- with the object-orientedparadigm of computing first, this paper discusses formally the semantics of aquite purely object-oriented logic paradigm in terms of proof theory modeltheory and Aspoint theory from the viewpoint of logic. The operational anddeclarative semantics is given. And then the correspondence between soundnessand completeness has been discussed formally.展开更多
The famous diagonal argument plays a prominent role in set the ory as well as in the proof of undecidability results in computability the ory and incompleteness results in metamathematics.Lawvere(1969)brings to light ...The famous diagonal argument plays a prominent role in set the ory as well as in the proof of undecidability results in computability the ory and incompleteness results in metamathematics.Lawvere(1969)brings to light the common schema among them through a pretty neat fixpoint the orem which generalizes the diagonal argument behind Cantor's theorem and characterizes self-reference explicitly in category theory.Not until Yanofsky(2003)rephrases Lawvere’s fixpoint theorem using sets and functions,Lawvere's work has been overlooked by logicians.This paper will continue Yanofsky's work,and show more applications of Lawvere's fixpoint theorem to demonstrate the ubiquity of the theorem.For example,this paper will use it to construct uncomputable real number,unnameable real number,partial re cursive but not potentially recursive function,Berry paradox,and fast growing Busy Beaver function.Many interesting lambda fixpoint combinators can also be fitted into this schema.Both Curry's Y combinator and Turing's combinator follow from Lawvere's theorem,as well as their call-by-value versions.At last,it can be shown that the lambda calculus version of the fixpoint lemma also fits Lawvere’s schema.展开更多
基金Supported by the National Natural Sciences Foun-dation of China (60233010 ,60273034 ,60403014) ,863 ProgramofChina (2002AA116010) ,973 Programof China (2002CB312002)
文摘Tree logic, inherited from ambient logic, is introduced as the formal foundation of related programming language and type systems, In this paper, we introduce recursion into such logic system, which can describe the tree data more dearly and concisely. By making a distinction between proposition and predicate, a concise semantics interpretation for our modal logic is given. We also develop a model checking algorithm for the logic without △ operator. The correctness of the algorithm is shown. Such work can be seen as the basis of the semi-structured data processing language and more flexible type system.
文摘Ambient logics have been proposed to describe properties for mobile agentswhich may evolve over time as well as space. This paper takes a predicate-based approach toextending an ambient logic with recursion, yielding a predicate μ-calculus in which fixpointformulas are formed using predicate variables. An algorithm is developed for model checkingfinite-control mobile ambients against formulas of the logic, providing the first decidabilityresult for model checking a spatial logic with recursion.
文摘Przymusinski extended the notion of stratified logic programs,developed by Apt,Blair and Walker,and by van Gelder,to stratified databases that allow both negative premises and disjunctive consequents.However,he did not provide a fixpoint theory for such class of databases.On the other hand,although a fixpoint semantics has been developed by Minker and Rajasekar for non-Horn logic programs,it is tantamount to traditional minimal model semantics which is not sufficient to capture the intended meaning of negation in the premises of clauses in stratified databases.In this paper,a fixpoint approach to stratified databases is developed,which corresponds with the perfect model semantics. Moreover,algorithms are proposed for computing the set of perfect models of a stratified database.
文摘We give two generalizations of Tarski’s fixpoint theorem in the setting of residuated lattices and use them to establish van Emdem-Kowalski’s least fixpoint semantics for residuated lattice-valued logic programs.
文摘This paper investigates the semantics of conditional term rewriting systemswith negation (denoted by EI-CTRS), called constructor-based EI-model se-mantics. The introduction of '≠' in EI-CTRS make EI-CTRS more difficult tostudy. This is in part because of a failure of EI-CTRS to guarantee that thereexist least Herbrand models in classical logical point of views. The key idea ofEI-model is to explain that 't ≠ s' means that the two concepts representedby t and s respectively actually belong to distinguished basic concepts repre-sented by two constructor-ground terms. We define the concept of EI-model,and show that there exist least Herbrand ELmodels for EI-satisfiable EI-CTRS.From algebraic and logic point of view, we show that there are very strong rea-sons for regarding the least Herbrand EI-models as the intended semantics ofEI-CTRS. According to fixpoint theory, we develop a method to construct leastHerbrand EI-models in a bottom-up manner. Moreover, we discuss soundnessand completeness of EI-rewrite for EI-model semantics.
文摘The development of the object-oriented paradigm has suffered from the lackof any generally accepted formal foundations for its semantic definition. Toaddress this issue, we propose the development of the logic-based semantics ofthe object-oriented paradigm. By combining the logic- with the object-orientedparadigm of computing first, this paper discusses formally the semantics of aquite purely object-oriented logic paradigm in terms of proof theory modeltheory and Aspoint theory from the viewpoint of logic. The operational anddeclarative semantics is given. And then the correspondence between soundnessand completeness has been discussed formally.
文摘The famous diagonal argument plays a prominent role in set the ory as well as in the proof of undecidability results in computability the ory and incompleteness results in metamathematics.Lawvere(1969)brings to light the common schema among them through a pretty neat fixpoint the orem which generalizes the diagonal argument behind Cantor's theorem and characterizes self-reference explicitly in category theory.Not until Yanofsky(2003)rephrases Lawvere’s fixpoint theorem using sets and functions,Lawvere's work has been overlooked by logicians.This paper will continue Yanofsky's work,and show more applications of Lawvere's fixpoint theorem to demonstrate the ubiquity of the theorem.For example,this paper will use it to construct uncomputable real number,unnameable real number,partial re cursive but not potentially recursive function,Berry paradox,and fast growing Busy Beaver function.Many interesting lambda fixpoint combinators can also be fitted into this schema.Both Curry's Y combinator and Turing's combinator follow from Lawvere's theorem,as well as their call-by-value versions.At last,it can be shown that the lambda calculus version of the fixpoint lemma also fits Lawvere’s schema.
