Details
| Original language | English |
|---|---|
| Title of host publication | Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings |
| Editors | Carlos Martin-Vide, Shmuel Tomi Klein, Dana Shapira |
| Publisher | Springer Verlag |
| Pages | 130-142 |
| Number of pages | 13 |
| ISBN (print) | 9783319773124 |
| Publication status | Published - 2018 |
| Event | 12th International Conference on Language and Automata Theory and Applications, LATA 2018 - Ramat Gan, Israel Duration: 9 Apr 2018 → 11 Apr 2018 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 10792 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 1611-3349 |
Abstract
In this paper, we study Reiter’s propositional default logic when the treewidth of a certain graph representation (semi-primal graph) of the input theory is bounded. We establish a dynamic programming algorithm on tree decompositions that decides whether a theory has a consistent stable extension (Ext). Our algorithm can even be used to enumerate all generating defaults (EnumSE) that lead to stable extensions. We show that our algorithm decides Ext in linear time in the input theory and triple exponential time in the treewidth (so-called fixed-parameter linear algorithm). Further, our algorithm solves EnumSE with a pre-computation step that is linear in the input theory and triple exponential in the treewidth followed by a linear delay to output solutions.
Keywords
- Dynamic programming, Parameterized algorithms, Propositional logic, Reiter’s default logic, Tree decompositions
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
- General Computer Science
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings. ed. / Carlos Martin-Vide; Shmuel Tomi Klein; Dana Shapira. Springer Verlag, 2018. p. 130-142 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10792 LNCS).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Default Logic and Bounded Treewidth
AU - Fichte, Johannes K.
AU - Hecher, Markus
AU - Schindler, Irina
N1 - Funding Information: The work has been supported by the Austrian Science Fund (FWF), Grants Y698 and P26696, and the German Science Fund (DFG), Grant ME 4279/1-1. The first two authors are also affiliated with the Institute of Computer Science and Computational Science at University of Potsdam, Germany. An extended self-archived version of the paper can be found online.
PY - 2018
Y1 - 2018
N2 - In this paper, we study Reiter’s propositional default logic when the treewidth of a certain graph representation (semi-primal graph) of the input theory is bounded. We establish a dynamic programming algorithm on tree decompositions that decides whether a theory has a consistent stable extension (Ext). Our algorithm can even be used to enumerate all generating defaults (EnumSE) that lead to stable extensions. We show that our algorithm decides Ext in linear time in the input theory and triple exponential time in the treewidth (so-called fixed-parameter linear algorithm). Further, our algorithm solves EnumSE with a pre-computation step that is linear in the input theory and triple exponential in the treewidth followed by a linear delay to output solutions.
AB - In this paper, we study Reiter’s propositional default logic when the treewidth of a certain graph representation (semi-primal graph) of the input theory is bounded. We establish a dynamic programming algorithm on tree decompositions that decides whether a theory has a consistent stable extension (Ext). Our algorithm can even be used to enumerate all generating defaults (EnumSE) that lead to stable extensions. We show that our algorithm decides Ext in linear time in the input theory and triple exponential time in the treewidth (so-called fixed-parameter linear algorithm). Further, our algorithm solves EnumSE with a pre-computation step that is linear in the input theory and triple exponential in the treewidth followed by a linear delay to output solutions.
KW - Dynamic programming
KW - Parameterized algorithms
KW - Propositional logic
KW - Reiter’s default logic
KW - Tree decompositions
UR - http://www.scopus.com/inward/record.url?scp=85045348232&partnerID=8YFLogxK
U2 - 10.48550/arXiv.1706.09393
DO - 10.48550/arXiv.1706.09393
M3 - Conference contribution
AN - SCOPUS:85045348232
SN - 9783319773124
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 130
EP - 142
BT - Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings
A2 - Martin-Vide, Carlos
A2 - Klein, Shmuel Tomi
A2 - Shapira, Dana
PB - Springer Verlag
T2 - 12th International Conference on Language and Automata Theory and Applications, LATA 2018
Y2 - 9 April 2018 through 11 April 2018
ER -