Many intractable problems have been shown to become tractable if the treewidth of the Underlying Structure is bounded by a constant. An important tool for deriving Such results is Courcelle's theorem, which states...
详细信息
ISBN:
(纸本)9783540894384
Many intractable problems have been shown to become tractable if the treewidth of the Underlying Structure is bounded by a constant. An important tool for deriving Such results is Courcelle's theorem, which states that all properties defined by Monadic-Second Order (MSO) sentences are fixed-parameter tractable with respect to the treewidth. Arnborg, et al, extended this result to counting problems defined via MSO properties. However, the MSO description of a problem is of course not an algorithm. Consequently, proving the fixed-parameter tractability of some problem via Courcelle's theorem can be considered as the starting point rather than the endpoint of the search for ail efficient algorithm. Gottlob et al. have recently presented a new approach via monadic datalog to actually devise efficient algorithms for decision problems whose tractability follows front Courcelle's theorem. In this paper, we extend this approach and apply it to some fundamental counting problems in logic an artificialintelligence.
We distill Penrose's argument against the "artificialintelligence premiss", and analyze its logical alternatives. We then clarify the different positions one can take in answer to the question raised by...
详细信息
ISBN:
(纸本)354030553X
We distill Penrose's argument against the "artificialintelligence premiss", and analyze its logical alternatives. We then clarify the different positions one can take in answer to the question raised by the argument, skirting the issue of introspection per se.
the proceedings contain 24 papers. the topics discussed include: a comparative study of the use of a robust color image segmentation method;a logicprogramming language designed for the modeling of abductive reasoning...
ISBN:
(纸本)9781538677353
the proceedings contain 24 papers. the topics discussed include: a comparative study of the use of a robust color image segmentation method;a logicprogramming language designed for the modeling of abductive reasoning in an educational context;a modified-ABC: an explicit-memory based approach with a new memory updating and retrieval in dynamic environments;a polynomial time algorithm for counting the number of independent sets of cactus graphs;a statistical comparison of objective functions for the vehicle routing problem with route balancing;a study on pattern-based spectral clustering methods in DWN;an improved automated definition extraction method based on lexicographic and lexico-semantic features;and an unsupervised approach for automatic discovery of metadata in document images.
this paper introduces a novel monotonic modal logic, able to characterise reflexive autoepistemic reasoning of the nonmonotonic variant of modal logic SW5: we add a second new modal operator into the original language...
详细信息
ISBN:
(纸本)9783319616605;9783319616599
this paper introduces a novel monotonic modal logic, able to characterise reflexive autoepistemic reasoning of the nonmonotonic variant of modal logic SW5: we add a second new modal operator into the original language of SW5, and show that the resulting formalism called MRAE* is strong enough to capture the minimal model notion underlying some major forms of nonmonotonic logic among which are autoepistemic logic, default logic, and nonmonotonic logicprogramming. the paper ends with a discussion of a general strategy, naturally embedding several nonmonotonic logics of similar kinds.
In this paper we introduce a multi-context variant of Reiter's default logic. the logic provides a syntactical counterpart of Roelofsen and Serafini's information chain approach (IJCAI-05), yet has several adv...
详细信息
In this paper we introduce a multi-context variant of Reiter's default logic. the logic provides a syntactical counterpart of Roelofsen and Serafini's information chain approach (IJCAI-05), yet has several advantages: it is closer to standard ways of representing nonmonotonic inference and a number of results from that area come "for free";it is closer to implementation, in particular the restriction to logicprogramming gives us a computationally attractive framework;and it allows us to handle a problem withthe information chain approach related to skeptical reasoning.
Extensional higher-order logicprogramming has been recently proposed as an interesting extension of classical logicprogramming An important characteristic of the new paradigm is that it preserves all the well-known ...
详细信息
Extensional higher-order logicprogramming has been recently proposed as an interesting extension of classical logicprogramming An important characteristic of the new paradigm is that it preserves all the well-known properties of traditional logicprogramming In this paper we enhance extensional higher-order logicprogramming with constructive negation. We argue that the main ideas underlying constructive negation are quite close to the existing proof procedure for extensional higher-order logicprogramming and for this reason the two notions amalgamate quite conveniently. We demonstrate the soundness of the resulting proof procedure and describe an actual implementation of a language that embodies the above ideas. In this way we obtain the first (to our knowledge) higher-order logicprogramming language supporting constructive negation and offering a new style of programmingthat genuinely extends that of traditional logicprogramming.
Although epistemic logicprogramming has an enhanced capacity to handle complex incomplete information reasoning and represent agents' epistemic behaviours, it embeds a significantly higher computational complexit...
详细信息
Although epistemic logicprogramming has an enhanced capacity to handle complex incomplete information reasoning and represent agents' epistemic behaviours, it embeds a significantly higher computational complexity than non-disjunctive and disjunctive answer set programming. In this paper, we investigate some important properties of epistemic logic programs. In particular, we show that Lee and Lifschitz's result on loop formulas for disjunctive logic programs can be extended to a special class of epistemic logic programs. We also study the polysize model property for epistemic logic programs. Based on these discoveries, we identify two non-trivial classes of epistemic logic programs whose consistency checking complexity is reduced from PSPACE-complete to NP-complete and Sigma(P)(2)-complete respectively. We observe that many important applications on epistemic representation fall into these two classes of epistemic logic programs.
the nosocomial infections are a growing concern because they affect a large number of people and they increase the admission time in healthcare facilities. Additionally, its diagnosis is very tricky, requiring multipl...
详细信息
ISBN:
(纸本)9783319393841
the nosocomial infections are a growing concern because they affect a large number of people and they increase the admission time in healthcare facilities. Additionally, its diagnosis is very tricky, requiring multiple medical exams. So, this work is focused on the development of a clinical decision support system to prevent these events from happening. the proposed solution is unique once it caters for the explicit treatment of incomplete, unknown, or even contradictory information under a logicprogramming basis, that to our knowledge is something that happens for the first time.
暂无评论