Argumentation (abduction) is widely applied in artificial intelligence (AI) and law reasoning. However, the problem of how to perform argumentation in disjunctive logic programming (DLP) is still open.In addition, a u...Argumentation (abduction) is widely applied in artificial intelligence (AI) and law reasoning. However, the problem of how to perform argumentation in disjunctive logic programming (DLP) is still open.In addition, a unifying semantic framework is required for incorporating various semantics for DLP. An argumentation-theoretic framework for DLP by taking the disjuncts of negative literals as abducibles is presented. This semantics not only is a simple and intuitive framework for performing argumentation and abduction in DLP, but also provides a unifying framework for many key semantics of disjunctive logic programs. In particular, it is shown that the EGCWA, well-founded model and disjunctive stable models can all be embedded into this semantics.展开更多
In this paper, it is shown that stable model semantics, perfect model semantics, and partial stable model semantics of disjunctive logic programs have the same expressive power with respect to the polynomial-time mode...In this paper, it is shown that stable model semantics, perfect model semantics, and partial stable model semantics of disjunctive logic programs have the same expressive power with respect to the polynomial-time model-equivalent reduction. That is, taking perfect model semantics and stable model semantic as an example, any logic program P can be transformed in polynomial time to another logic program P＇ such that perfect models （resp. stable models） of P i-i correspond to stable models （resp. perfect models） of P＇, and the correspondence can be computed also in polynomial time. However, the minimal model semantics has weaker expressiveness than other mentioned semantics, otherwise, the polynomial hierarchy would collapse to NP.展开更多
In common sense reasoning with incomplete knowledge bases, conclusions are made by defaultHowever, it is observed that when the negation-by-default operator not is defined as not provable , the disjunctive logic progr...In common sense reasoning with incomplete knowledge bases, conclusions are made by defaultHowever, it is observed that when the negation-by-default operator not is defined as not provable , the disjunctive logic program { a V b, not a, not b} should be consistent because a being not provable and b being nor provable does not imply a V b being riot provable. Such an observation is significant for non-monotonic reasoning, but none of the major current semantics for disjunctive logic programs is able to support it because they are all based on classical first-order logic in which assuming not a and not b implies assuming no: (a V b) A new first-order logic (disjunctive logic ) is developed that fully complies with this observation and new semantics for disjunctive logic programs are established This theory is able to formalize and solve some paradoxical problems, such as the lottery paradox展开更多
By translating each disjunctive logic program into an abductive framework, a declarative semantics for the class of disjunctive logic programs, called the typical abductive semantics (TAS), is presented, which is quit...By translating each disjunctive logic program into an abductive framework, a declarative semantics for the class of disjunctive logic programs, called the typical abductive semantics (TAS), is presented, which is quite simple and highly intuitive. TAS is complete and coincides with the stable semantics for the class of disjunctive programs that possess stable models. By the coherence principle, TAS can be easily generalized to extended disjunctive programs and can properly handle some benchmark problems in commonsense reasoning展开更多
The paradigm of disjunctive logic programming (DLP) enhances greatly the expressive power of normal logic programming (NLP) and many (declarative) semantics have beeu defined for DLP to cope with various problems of ...The paradigm of disjunctive logic programming (DLP) enhances greatly the expressive power of normal logic programming (NLP) and many (declarative) semantics have beeu defined for DLP to cope with various problems of knowledge representation in artificial intelligence. However, the expressive ability of the semantics and the soundness of program transformations for DLP have been rarely explored. This paper defines an immediate consequence operator TGP for each disjunctive program and shows that TGP has the least and computable fixpoint Lft(P). Lft is, in fact, a program transformation for DLP which transforms all disjunctive programs into negative programs. It is shown that Lft preserves many key semantics, including the disjunctive stable models, well-founded model, disjunctive argument semantics DAS, three-valued models, etc. This means that every disjunctive program P has a unique canonical form Lft(P) with respect to these semanics. As a result, the work in this paper provides a unifying frameword for studying the expressive ability of various semantics for DLP.On the other hand, the computing of the above semantics for negative programs is just a trivial task, therefore, Lft(P) is also an optimization method for DLP. Another application of Lft is to derive some interesting semantic results for DLP.展开更多
Inductive logic programming adopts the standard horn lope program as its logic framework for inductivelearning. Due to the fact, however, that the expressive power of horn logic is relatively limited and the mechansm ...Inductive logic programming adopts the standard horn lope program as its logic framework for inductivelearning. Due to the fact, however, that the expressive power of horn logic is relatively limited and the mechansm ofnegation is mostly that of negation as failure, it is difficult to make full use of negative information and consequentlynot suitable for inductive learning. This Paper adopts nounal lope program as me language of inductive logic programsand presents accordingly a kind of semantics called Limited Negation semantics. The issues of direct denotation andinference of negation in concept induction are solved. The paper shows that LN is directly generalized for the semantics of Well-Founded in die significance Of optional negation and has superior theoretical features, especially the capability Of expressing and processing negation by introducing the constant ’false’. ExperimentS also show that the inductive concepts in learning are accurately interpreted with LN.展开更多
In this article, we present a systemic approach toward a fuzzy logic based formalization of an approximate reasoning methodology in a fuzzy resolution, where we derive a truth value of A from both values of B → A and...In this article, we present a systemic approach toward a fuzzy logic based formalization of an approximate reasoning methodology in a fuzzy resolution, where we derive a truth value of A from both values of B → A and B by some mechanism. For this purpose, we utilize a t-norm fuzzy logic, in which an implication operator is a root of both graduated conjunction and disjunction operators. Furthermore by using an inverse approximate reasoning, we conclude the truth value of A from both values of B → A and B, applying an altogether different mechanism. A current research is utilizing an approximate reasoning methodology, which is based on a similarity relation for a fuzzification, while similarity measure is utilized in fuzzy inference mechanism. This approach is applied to both generalized modus-ponens/modus-tollens syllogisms and is well-illustrated with artificial examples.展开更多
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.
Atomic blocks, a high-level language construct that allows programmers to explicitly specify the atomicity of operations without worrying about the implementations, are a promising approach that simplifies concurrent ...Atomic blocks, a high-level language construct that allows programmers to explicitly specify the atomicity of operations without worrying about the implementations, are a promising approach that simplifies concurrent programming. On the other hand, temporal logic is a successful model in logic programming and concurrency verification, but none of existing temporal programming models supports concurrent programming with atomic blocks yet. In this paper, we propose a temporal programming model （αPTL） which extends the projection temporal logic （PTL） to support concurrent programming with atomic blocks. The novel construct that formulates atomic execution of code blocks, which we call atomic interval formulas, is always interpreted over two consecutive states, with the internal states of the block being abstracted away. We show that the framing mechanism in projection temporal logic also works in the new model, which consequently supports our development of an executive language. The language supports concurrency by introducing a loose interleaving semantics which tracks only the mutual exclusion between atomic blocks. We demonstrate the usage of αPTL by modeling and verifying both the fine-grained and coarse-grained concurrency.展开更多
The technique of forcing created by Cohen is adopted to discuss the semantics of medium logic program without closed-world assumption (CWA).The fixed point and complete-meet semilattice property ofprogram generic set ...The technique of forcing created by Cohen is adopted to discuss the semantics of medium logic program without closed-world assumption (CWA).The fixed point and complete-meet semilattice property ofprogram generic set is proved.展开更多
It is argued that some symmetric structure in logic programs could be taken into account when implementing semantics in logic programming. This may enhance the declarative ability or expressive power of the semantics....It is argued that some symmetric structure in logic programs could be taken into account when implementing semantics in logic programming. This may enhance the declarative ability or expressive power of the semantics. The work presented here may be seen as representative examples along this line. The focus is on the derivation of negative information and some other classic semantic issues. We first define a permutation group associated with a given logic program. Since usually the canonical models used to reflect the common sense or intended meaning are minimal or completed models of the program, we expose the relationships between minimal models and completed models of the original program and its so-called G-reduced form newlt-derived via the permutation group defined. By means of this G reduced form, we introduce a rule to assume negative information termed G-CWA, which is actually a generalization of the GCWA. We also develop the notions of G-definite, G-hierarchical and G-stratified logic programs, which are more general than definite, hierarchical and stratified programs, and extend some well-known declarative and procedural semantics to them, respectively. Keywords symmetry - logic programming - semantics Partially supported by the National Natural Science Foundation of China under Grant No.60373113.Jin-Zhao Wu was born in 1965. He obtained his Ph.D. degree in 1994 from the Institute of Systems Science, the Chinese Academy of Sciences. From 1994 to 1999 he was a post-doctoral and research scientist in Peking University and Max-Planck Institute of Computer Science. Since 2000 he has been working on the Faculty of Mathematics and Computer Science, University of Mannheim.Harald Fecher was born in 1972. He obtained his Ph.D. degree in 2003 from the Faculty of Mathematics and Computer Science, University of Mannheim. Since 2004 he has been research scientist in the Faculty of Computer Science, University of Kiel.展开更多
针对非循环概念提出了一种对SHOIN(D)-概念可满足性进行判断的方法——CDNF(complete disjunctive normal form)算法.该算法通过把非循环定义的概念描述本身构建成分层次的析取范式群,并通过子句重用技术阻止无谓的子概念扩展,这样的析...针对非循环概念提出了一种对SHOIN(D)-概念可满足性进行判断的方法——CDNF(complete disjunctive normal form)算法.该算法通过把非循环定义的概念描述本身构建成分层次的析取范式群,并通过子句重用技术阻止无谓的子概念扩展,这样的析取范式群具有可满足性自明性,从而可以实现对SHOIN(D)-概念可满足性的直接判断.该算法基本上消除了判断过程中描述重复的现象,从而在空间、时间性能上都比Tableau算法有更好的表现.关键词:描述逻辑推理;可满足性;析取范式;SHOIN(D);展开更多
文摘Argumentation (abduction) is widely applied in artificial intelligence (AI) and law reasoning. However, the problem of how to perform argumentation in disjunctive logic programming (DLP) is still open.In addition, a unifying semantic framework is required for incorporating various semantics for DLP. An argumentation-theoretic framework for DLP by taking the disjuncts of negative literals as abducibles is presented. This semantics not only is a simple and intuitive framework for performing argumentation and abduction in DLP, but also provides a unifying framework for many key semantics of disjunctive logic programs. In particular, it is shown that the EGCWA, well-founded model and disjunctive stable models can all be embedded into this semantics.
基金This research was partially supported by the National Natural Science Foundation of China under Grant Nos.60573011,10410638an MOE Project of Key Institute at Universities under Grant No.05JJD72040122.
文摘In this paper, it is shown that stable model semantics, perfect model semantics, and partial stable model semantics of disjunctive logic programs have the same expressive power with respect to the polynomial-time model-equivalent reduction. That is, taking perfect model semantics and stable model semantic as an example, any logic program P can be transformed in polynomial time to another logic program P＇ such that perfect models （resp. stable models） of P i-i correspond to stable models （resp. perfect models） of P＇, and the correspondence can be computed also in polynomial time. However, the minimal model semantics has weaker expressiveness than other mentioned semantics, otherwise, the polynomial hierarchy would collapse to NP.
基金Project supported in part by the National Natural Science Foundation of China, the State Education Commission and the Sichuan Youth Science and Technology Foundation of China The research was completed during the authors vist to the mverstty of Maryland
文摘In common sense reasoning with incomplete knowledge bases, conclusions are made by defaultHowever, it is observed that when the negation-by-default operator not is defined as not provable , the disjunctive logic program { a V b, not a, not b} should be consistent because a being not provable and b being nor provable does not imply a V b being riot provable. Such an observation is significant for non-monotonic reasoning, but none of the major current semantics for disjunctive logic programs is able to support it because they are all based on classical first-order logic in which assuming not a and not b implies assuming no: (a V b) A new first-order logic (disjunctive logic ) is developed that fully complies with this observation and new semantics for disjunctive logic programs are established This theory is able to formalize and solve some paradoxical problems, such as the lottery paradox
基金Project supported by the State Climbing Project of China, the High-Tech Program of China and the fund from the National University of Defense Technology.
文摘By translating each disjunctive logic program into an abductive framework, a declarative semantics for the class of disjunctive logic programs, called the typical abductive semantics (TAS), is presented, which is quite simple and highly intuitive. TAS is complete and coincides with the stable semantics for the class of disjunctive programs that possess stable models. By the coherence principle, TAS can be easily generalized to extended disjunctive programs and can properly handle some benchmark problems in commonsense reasoning
文摘The paradigm of disjunctive logic programming (DLP) enhances greatly the expressive power of normal logic programming (NLP) and many (declarative) semantics have beeu defined for DLP to cope with various problems of knowledge representation in artificial intelligence. However, the expressive ability of the semantics and the soundness of program transformations for DLP have been rarely explored. This paper defines an immediate consequence operator TGP for each disjunctive program and shows that TGP has the least and computable fixpoint Lft(P). Lft is, in fact, a program transformation for DLP which transforms all disjunctive programs into negative programs. It is shown that Lft preserves many key semantics, including the disjunctive stable models, well-founded model, disjunctive argument semantics DAS, three-valued models, etc. This means that every disjunctive program P has a unique canonical form Lft(P) with respect to these semanics. As a result, the work in this paper provides a unifying frameword for studying the expressive ability of various semantics for DLP.On the other hand, the computing of the above semantics for negative programs is just a trivial task, therefore, Lft(P) is also an optimization method for DLP. Another application of Lft is to derive some interesting semantic results for DLP.
文摘Inductive logic programming adopts the standard horn lope program as its logic framework for inductivelearning. Due to the fact, however, that the expressive power of horn logic is relatively limited and the mechansm ofnegation is mostly that of negation as failure, it is difficult to make full use of negative information and consequentlynot suitable for inductive learning. This Paper adopts nounal lope program as me language of inductive logic programsand presents accordingly a kind of semantics called Limited Negation semantics. The issues of direct denotation andinference of negation in concept induction are solved. The paper shows that LN is directly generalized for the semantics of Well-Founded in die significance Of optional negation and has superior theoretical features, especially the capability Of expressing and processing negation by introducing the constant ’false’. ExperimentS also show that the inductive concepts in learning are accurately interpreted with LN.
文摘In this article, we present a systemic approach toward a fuzzy logic based formalization of an approximate reasoning methodology in a fuzzy resolution, where we derive a truth value of A from both values of B → A and B by some mechanism. For this purpose, we utilize a t-norm fuzzy logic, in which an implication operator is a root of both graduated conjunction and disjunction operators. Furthermore by using an inverse approximate reasoning, we conclude the truth value of A from both values of B → A and B, applying an altogether different mechanism. A current research is utilizing an approximate reasoning methodology, which is based on a similarity relation for a fuzzification, while similarity measure is utilized in fuzzy inference mechanism. This approach is applied to both generalized modus-ponens/modus-tollens syllogisms and is well-illustrated with artificial examples.
文摘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.
基金Acknowledgements We thank for anonymous referees for their suggestions and comments. This research was based on work supported by grants from Science Foundation of China Project （60833001, 61100063, 61073040 and 61103023）, and by a Humboldt Fellowship （X.Y.） from Alexander von Humboldt Foundation.
文摘Atomic blocks, a high-level language construct that allows programmers to explicitly specify the atomicity of operations without worrying about the implementations, are a promising approach that simplifies concurrent programming. On the other hand, temporal logic is a successful model in logic programming and concurrency verification, but none of existing temporal programming models supports concurrent programming with atomic blocks yet. In this paper, we propose a temporal programming model （αPTL） which extends the projection temporal logic （PTL） to support concurrent programming with atomic blocks. The novel construct that formulates atomic execution of code blocks, which we call atomic interval formulas, is always interpreted over two consecutive states, with the internal states of the block being abstracted away. We show that the framing mechanism in projection temporal logic also works in the new model, which consequently supports our development of an executive language. The language supports concurrency by introducing a loose interleaving semantics which tracks only the mutual exclusion between atomic blocks. We demonstrate the usage of αPTL by modeling and verifying both the fine-grained and coarse-grained concurrency.
基金Project supported by the High Technology Research and Development Program of China. the Key Project of Fundamental Research. Climbing Project.
文摘The technique of forcing created by Cohen is adopted to discuss the semantics of medium logic program without closed-world assumption (CWA).The fixed point and complete-meet semilattice property ofprogram generic set is proved.
文摘It is argued that some symmetric structure in logic programs could be taken into account when implementing semantics in logic programming. This may enhance the declarative ability or expressive power of the semantics. The work presented here may be seen as representative examples along this line. The focus is on the derivation of negative information and some other classic semantic issues. We first define a permutation group associated with a given logic program. Since usually the canonical models used to reflect the common sense or intended meaning are minimal or completed models of the program, we expose the relationships between minimal models and completed models of the original program and its so-called G-reduced form newlt-derived via the permutation group defined. By means of this G reduced form, we introduce a rule to assume negative information termed G-CWA, which is actually a generalization of the GCWA. We also develop the notions of G-definite, G-hierarchical and G-stratified logic programs, which are more general than definite, hierarchical and stratified programs, and extend some well-known declarative and procedural semantics to them, respectively. Keywords symmetry - logic programming - semantics Partially supported by the National Natural Science Foundation of China under Grant No.60373113.Jin-Zhao Wu was born in 1965. He obtained his Ph.D. degree in 1994 from the Institute of Systems Science, the Chinese Academy of Sciences. From 1994 to 1999 he was a post-doctoral and research scientist in Peking University and Max-Planck Institute of Computer Science. Since 2000 he has been working on the Faculty of Mathematics and Computer Science, University of Mannheim.Harald Fecher was born in 1972. He obtained his Ph.D. degree in 2003 from the Faculty of Mathematics and Computer Science, University of Mannheim. Since 2004 he has been research scientist in the Faculty of Computer Science, University of Kiel.
文摘针对非循环概念提出了一种对SHOIN(D)-概念可满足性进行判断的方法——CDNF(complete disjunctive normal form)算法.该算法通过把非循环定义的概念描述本身构建成分层次的析取范式群,并通过子句重用技术阻止无谓的子概念扩展,这样的析取范式群具有可满足性自明性,从而可以实现对SHOIN(D)-概念可满足性的直接判断.该算法基本上消除了判断过程中描述重复的现象,从而在空间、时间性能上都比Tableau算法有更好的表现.关键词:描述逻辑推理;可满足性;析取范式;SHOIN(D);
