| Updating action domain descriptions. | |
| | |
MedLine Citation:
|
PMID: 21151324 Owner: NLM Status: Publisher |
Abstract/OtherAbstract:
|
Incorporating new information into a knowledge base is an important problem which has been widely investigated. In this paper, we study this problem in a formal framework for reasoning about actions and change. In this framework, action domains are described in an action language whose semantics is based on the notion of causality. Unlike the formalisms considered in the related work, this language allows straightforward representation of non-deterministic effects and indirect effects of (possibly concurrent) actions, as well as state constraints; therefore, the updates can be more general than elementary statements. The expressivity of this formalism allows us to study the update of an action domain description with a more general approach compared to related work. First of all, we consider the update of an action description with respect to further criteria, for instance, by ensuring that the updated description entails some observations, assertions, or general domain properties that constitute further constraints that are not expressible in an action description in general. Moreover, our framework allows us to discriminate amongst alternative updates of action domain descriptions and to single out a most preferable one, based on a given preference relation possibly dependent on the specified criteria. We study semantic and computational aspects of the update problem, and establish basic properties of updates as well as a decomposition theorem that gives rise to a divide and conquer approach to updating action descriptions under certain conditions. Furthermore, we study the computational complexity of decision problems around computing solutions, both for the generic setting and for two particular preference relations, viz. set-inclusion and weight-based preference. While deciding the existence of solutions and recognizing solutions are PSPACE-complete problems in general, the problems fall back into the polynomial hierarchy under restrictions on the additional constraints. We finally discuss methods to compute solutions and approximate solutions (which disregard preference). Our results provide a semantic and computational basis for developing systems that incorporate new information into action domain descriptions in an action language, in the presence of additional constraints. |
| | |
Authors:
|
Thomas Eiter; Esra Erdem; Michael Fink; Ján Senko |
Related Documents
:
|
17552134 - Is obesity really the next tobacco? lessons learned from tobacco for obesity litigation. 21452684 - Income and nutritional status of the fishing community residing in coastal bay of benga... 17973734 - Application of the community readiness model for childhood obesity prevention. 16133954 - The effects of loperamide on continence problems and anorectal function in obese subjec... 21990944 - Problem drinking among transnational mexican migrants: exploring migrant status and sit... 1733634 - Anti-neutrophil cytoplasmic autoantibodies in patients with symptomatic hiv infection. |
Publication Detail:
|
Type: JOURNAL ARTICLE |
Journal Detail:
|
Title: Artificial intelligence Volume: 174 ISSN: 0004-3702 ISO Abbreviation: - Publication Date: 2010 Oct |
Date Detail:
|
Created Date: 2010-12-14 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 0262613 Medline TA: Artif Intell Country: - |
Other Details:
|
Languages: ENG Pagination: 1172-1221 Citation Subset: - |
Affiliation:
|
Institute of Information Systems, Vienna University of Technology, Vienna, Austria. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Grammatical feature dissimilarities make relative clauses easier: A comprehension study with Italian...
Next Document: Assessing the long-term species composition predicted by PrognAus.