Institut für Informatik und Computational Science
Refine
Year of publication
- 2022 (21) (remove)
Document Type
- Article (16)
- Doctoral Thesis (2)
- Postprint (2)
- Master's Thesis (1)
Is part of the Bibliography
- yes (21)
Keywords
- teacher training (3)
- Analytical models (2)
- Answer set programming (2)
- anti-cancer drugs (2)
- deep neural networks (2)
- drug-sensitivity prediction (2)
- higher education (2)
- policy evaluation (2)
- virtual mobility (2)
- Absorbed dose (1)
- Advanced Video Codec (AVC) (1)
- Algorithms (1)
- Benchmark testing; (1)
- Circuit faults (1)
- Codierungstheorie (1)
- Complexity (1)
- Computational Science (1)
- Deep Learning (1)
- Deep learning (1)
- Dempster-Shafer-Theorie (1)
- Dempster–Shafer theory (1)
- Dose rate (1)
- Encoding (1)
- Engines (1)
- Evidenztheorie (1)
- FPGA (1)
- Fehlererkennung (1)
- Flip-flops (1)
- H.264 (1)
- Hardware accelerator (1)
- Hochschulbildung (1)
- Inference (1)
- Informatik (1)
- Informatikdidaktik (1)
- Integrated circuit modeling (1)
- Klassifikator-Kalibrierung (1)
- Konstruktivismus (1)
- Lehrkräfteausbildung (1)
- Liver neoplasms (1)
- Low Latency (1)
- Machine Learning (1)
- Machine learning (1)
- Mehrklassen-Klassifikation (1)
- Metric learning (1)
- Network (1)
- Network security (1)
- Parameterized complexity (1)
- Phantoms (1)
- Programming (1)
- RADFET (1)
- RADFETs (1)
- Radiation hardness (1)
- Random access memory (1)
- Region of Interest (1)
- Reproducibility of results (1)
- Scalability (1)
- Search problems (1)
- Security (1)
- Self-adaptive MPSoC (1)
- Sequence embeddings (1)
- Single event upsets (1)
- Speicher (1)
- Tomography (1)
- Tools (1)
- Tree decomposition (1)
- Treewidth (1)
- Treewidth-aware reductions (1)
- X-ray computed (1)
- analysis (1)
- annealing (1)
- approximate model counting (1)
- classifier calibration (1)
- compliance (1)
- construktivism (1)
- craters (1)
- didactics (1)
- dynamic classification (1)
- dynamische Klassifikation (1)
- education (1)
- error propagation (1)
- evidence theory (1)
- fading (1)
- formal (1)
- hardware accelerator (1)
- ice harboring (1)
- imaging (1)
- irradiation (1)
- knowledge representation and reasoning (1)
- logic programming (1)
- lunar exploration (1)
- machine learning (1)
- machine learning algorithms (1)
- monitoring (1)
- multi-class classification (1)
- online learning (1)
- pMOS radiation dosimeter (1)
- planning (1)
- predictive models (1)
- radhard design (1)
- reliability (1)
- reliability analysis (1)
- security (1)
- selective fault tolerance (1)
- self-adaptive multiprocessing system (1)
- sensitivity (1)
- single event upset (1)
- single event upsets (1)
- solar particle event (1)
- space missions (1)
- unidirektionale Fehler (1)
- university education (1)
- verification (1)
Institute
Answer Set Programming (ASP) is a paradigm for modeling and solving problems for knowledge representation and reasoning. There are plenty of results dedicated to studying the hardness of (fragments of) ASP. So far, these studies resulted in characterizations in terms of computational complexity as well as in fine-grained insights presented in form of dichotomy-style results, lower bounds when translating to other formalisms like propositional satisfiability (SAT), and even detailed parameterized complexity landscapes. A generic parameter in parameterized complexity originating from graph theory is the socalled treewidth, which in a sense captures structural density of a program. Recently, there was an increase in the number of treewidth-based solvers related to SAT. While there are translations from (normal) ASP to SAT, no reduction that preserves treewidth or at least keeps track of the treewidth increase is known. In this paper we propose a novel reduction from normal ASP to SAT that is aware of the treewidth, and guarantees that a slight increase of treewidth is indeed sufficient. Further, we show a new result establishing that, when considering treewidth, already the fragment of normal ASP is slightly harder than SAT (under reasonable assumptions in computational complexity). This also confirms that our reduction probably cannot be significantly improved and that the slight increase of treewidth is unavoidable. Finally, we present an empirical study of our novel reduction from normal ASP to SAT, where we compare treewidth upper bounds that are obtained via known decomposition heuristics. Overall, our reduction works better with these heuristics than existing translations. (c) 2021 Elsevier B.V. All rights reserved.