Graph decompositions and tree automata in reasoning with uncertainty
| Autor: | Stefan Arnborg |
|---|---|
| Rok vydání: | 1993 |
| Předmět: |
Theoretical computer science
Computer science business.industry Directed graph Machine learning computer.software_genre Directed acyclic graph Feedback arc set Tree decomposition Theoretical Computer Science Artificial Intelligence Graph (abstract data type) Tree automaton Artificial intelligence business computer Computer Science::Databases Software Moral graph Directed acyclic word graph |
| Zdroj: | Journal of Experimental & Theoretical Artificial Intelligence. 5:335-357 |
| ISSN: | 1362-3079 0952-813X |
| DOI: | 10.1080/09528139308953776 |
| Popis: | We show how the theory of decomposable graphs can be used for reasoning methods involving a more refined analysis of models (in the logic sense) than classical reasoning. We introduce a directed binary graph representation of event structures. This representation gives a smaller tree-width than the more common hypergraph representation. If an event structure can be described by propositional fromuias -that can be represented by a directed acyclic graph of tree-width k, we show how models of the structure can be recognized by a tree automaton with a number of states single exponential in k. We then show how one version each of Bayesian, probabilistic, model preference and possibilistic reasoning can be performed with the automaton, in such a way that the time required is linear in the size of the formulas when k is fixed. Intuitively, the method transforms a difficult ‘equation solving’ computational problem into an easy ‘expression evaluation’ problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|