TY  - JOUR
A1  - Andjelkovic, Marko
A1  - Simevski, Aleksandar
A1  - Chen, Junchao
A1  - Schrape, Oliver
A1  - Stamenkovic, Zoran
A1  - Krstić, Miloš
A1  - Ilic, Stefan
A1  - Ristic, Goran
A1  - Jaksic, Aleksandar
A1  - Vasovic, Nikola
A1  - Duane, Russell
A1  - Palma, Alberto J.
A1  - Lallena, Antonio M.
A1  - Carvajal, Miguel A.
T1  - A design concept for radiation hardened RADFET readout system for space applications
JF  - Microprocessors and microsystems
N2  - Instruments for measuring the absorbed dose and dose rate under radiation exposure, known as radiation dosimeters, are indispensable in space missions. They are composed of radiation sensors that generate current or voltage response when exposed to ionizing radiation, and processing electronics for computing the absorbed dose and dose rate. Among a wide range of existing radiation sensors, the Radiation Sensitive Field Effect Transistors (RADFETs) have unique advantages for absorbed dose measurement, and a proven record of successful exploitation in space missions. It has been shown that the RADFETs may be also used for the dose rate monitoring. In that regard, we propose a unique design concept that supports the simultaneous operation of a single RADFET as absorbed dose and dose rate monitor. This enables to reduce the cost of implementation, since the need for other types of radiation sensors can be minimized or eliminated. For processing the RADFET's response we propose a readout system composed of analog signal conditioner (ASC) and a self-adaptive multiprocessing system-on-chip (MPSoC). The soft error rate of MPSoC is monitored in real time with embedded sensors, allowing the autonomous switching between three operating modes (high-performance, de-stress and fault-tolerant), according to the application requirements and radiation conditions.
KW  - RADFET
KW  - Radiation hardness
KW  - Absorbed dose
KW  - Dose rate
KW  - Self-adaptive MPSoC
Y1  - 2022
U6  - https://doi.org/10.1016/j.micpro.2022.104486
SN  - 0141-9331
SN  - 1872-9436
VL  - 90
PB  - Elsevier
CY  - Amsterdam
ER  - 
TY  - JOUR
A1  - Tran, Son Cao
A1  - Pontelli, Enrico
A1  - Balduccini, Marcello
A1  - Schaub, Torsten
T1  - Answer set planning
BT  - a survey
JF  - Theory and practice of logic programming
N2  - Answer Set Planning refers to the use of Answer Set Programming (ASP) to compute plans, that is, solutions to planning problems, that transform a given state of the world to another state. The development of efficient and scalable answer set solvers has provided a significant boost to the development of ASP-based planning systems. This paper surveys the progress made during the last two and a half decades in the area of answer set planning, from its foundations to its use in challenging planning domains. The survey explores the advantages and disadvantages of answer set planning. It also discusses typical applications of answer set planning and presents a set of challenges for future research.
KW  - planning
KW  - knowledge representation and reasoning
KW  - logic programming
Y1  - 2022
U6  - https://doi.org/10.1017/S1471068422000072
SN  - 1471-0684
SN  - 1475-3081
PB  - Cambridge University Press
CY  - New York
ER  - 
TY  - JOUR
A1  - Steinert, Fritjof
A1  - Stabernack, Benno
T1  - Architecture of a low latency H.264/AVC video codec for robust ML based image classification how region of interests can minimize the impact of coding artifacts
JF  - Journal of Signal Processing Systems for Signal, Image, and Video Technology
N2  - The use of neural networks is considered as the state of the art in the field of image classification. A large number of different networks are available for this purpose, which, appropriately trained, permit a high level of classification accuracy. Typically, these networks are applied to uncompressed image data, since a corresponding training was also carried out using image data of similar high quality. However, if image data contains image errors, the classification accuracy deteriorates drastically. This applies in particular to coding artifacts which occur due to image and video compression. Typical application scenarios for video compression are narrowband transmission channels for which video coding is required but a subsequent classification is to be carried out on the receiver side. In this paper we present a special H.264/Advanced Video Codec (AVC) based video codec that allows certain regions of a picture to be coded with near constant picture quality in order to allow a reliable classification using neural networks, whereas the remaining image will be coded using constant bit rate. We have combined this feature with the ability to run with lowest latency properties, which is usually also required in remote control applications scenarios. The codec has been implemented as a fully hardwired High Definition video capable hardware architecture which is suitable for Field Programmable Gate Arrays.
KW  - H.264
KW  - Advanced Video Codec (AVC)
KW  - Low Latency
KW  - Region of Interest
KW  - Machine Learning
KW  - Inference
KW  - FPGA
KW  - Hardware accelerator
Y1  - 2022
U6  - https://doi.org/10.1007/s11265-021-01727-2
SN  - 1939-8018
SN  - 1939-8115
VL  - 94
IS  - 7
SP  - 693
EP  - 708
PB  - Springer
CY  - New York
ER  - 
TY  - JOUR
A1  - Al Laban, Firas
A1  - Reger, Martin
A1  - Lucke, Ulrike
T1  - Closing the Policy Gap in the Academic Bridge
JF  - Education sciences
N2  - The highly structured nature of the educational sector demands effective policy mechanisms close to the needs of the field. That is why evidence-based policy making, endorsed by the European Commission under Erasmus+ Key Action 3, aims to make an alignment between the domains of policy and practice. Against this background, this article addresses two issues: First, that there is a vertical gap in the translation of higher-level policies to local strategies and regulations. Second, that there is a horizontal gap between educational domains regarding the policy awareness of individual players. This was analyzed in quantitative and qualitative studies with domain experts from the fields of virtual mobility and teacher training. From our findings, we argue that the combination of both gaps puts the academic bridge from secondary to tertiary education at risk, including the associated knowledge proficiency levels. We discuss the role of digitalization in the academic bridge by asking the question: which value does the involved stakeholders expect from educational policies? As a theoretical basis, we rely on the model of value co-creation for and by stakeholders. We describe the used instruments along with the obtained results and proposed benefits. Moreover, we reflect on the methodology applied, and we finally derive recommendations for future academic bridge policies.
KW  - policy evaluation
KW  - higher education
KW  - virtual mobility
KW  - teacher training
Y1  - 2022
U6  - https://doi.org/10.3390/educsci12120930
SN  - 2227-7102
VL  - 12
IS  - 12
PB  - MDPI
CY  - Basel
ER  - 
TY  - JOUR
A1  - Lorenz, Claas
A1  - Clemens, Vera Elisabeth
A1  - Schrötter, Max
A1  - Schnor, Bettina
T1  - Continuous verification of network security compliance
JF  - IEEE transactions on network and service management
N2  - Continuous verification of network security compliance is an accepted need. Especially, the analysis of stateful packet filters plays a central role for network security in practice. But the few existing tools which support the analysis of stateful packet filters are based on general applicable formal methods like Satifiability Modulo Theories (SMT) or theorem prover and show runtimes in the order of minutes to hours making them unsuitable for continuous compliance verification. In this work, we address these challenges and present the concept of state shell interweaving to transform a stateful firewall rule set into a stateless rule set. This allows us to reuse any fast domain specific engine from the field of data plane verification tools leveraging smart, very fast, and domain specialized data structures and algorithms including Header Space Analysis (HSA). First, we introduce the formal language FPL that enables a high-level human-understandable specification of the desired state of network security. Second, we demonstrate the instantiation of a compliance process using a verification framework that analyzes the configuration of complex networks and devices - including stateful firewalls - for compliance with FPL policies. Our evaluation results show the scalability of the presented approach for the well known Internet2 and Stanford benchmarks as well as for large firewall rule sets where it outscales state-of-the-art tools by a factor of over 41.
KW  - Security
KW  - Tools
KW  - Network security
KW  - Engines
KW  - Benchmark testing;
KW  - Analytical models
KW  - Scalability
KW  - Network
KW  - security
KW  - compliance
KW  - formal
KW  - verification
Y1  - 2021
U6  - https://doi.org/10.1109/TNSM.2021.3130290
SN  - 1932-4537
VL  - 19
IS  - 2
SP  - 1729
EP  - 1745
PB  - Institute of Electrical and Electronics Engineers
CY  - New York
ER  - 
TY  - JOUR
A1  - Abdelwahab, Ahmed
A1  - Landwehr, Niels
T1  - Deep Distributional Sequence Embeddings Based on a Wasserstein Loss
JF  - Neural processing letters
N2  - Deep metric learning employs deep neural networks to embed instances into a metric space such that distances between instances of the same class are small and distances between instances from different classes are large. In most existing deep metric learning techniques, the embedding of an instance is given by a feature vector produced by a deep neural network and Euclidean distance or cosine similarity defines distances between these vectors. This paper studies deep distributional embeddings of sequences, where the embedding of a sequence is given by the distribution of learned deep features across the sequence. The motivation for this is to better capture statistical information about the distribution of patterns within the sequence in the embedding. When embeddings are distributions rather than vectors, measuring distances between embeddings involves comparing their respective distributions. The paper therefore proposes a distance metric based on Wasserstein distances between the distributions and a corresponding loss function for metric learning, which leads to a novel end-to-end trainable embedding model. We empirically observe that distributional embeddings outperform standard vector embeddings and that training with the proposed Wasserstein metric outperforms training with other distance functions.
KW  - Metric learning
KW  - Sequence embeddings
KW  - Deep learning
Y1  - 2022
U6  - https://doi.org/10.1007/s11063-022-10784-y
SN  - 1370-4621
SN  - 1573-773X
PB  - Springer
CY  - Dordrecht
ER  - 
TY  - JOUR
A1  - Michallek, Florian
A1  - Genske, Ulrich
A1  - Niehues, Stefan Markus
A1  - Hamm, Bernd
A1  - Jahnke, Paul
T1  - Deep learning reconstruction improves radiomics feature stability and discriminative power in abdominal CT imaging
BT  - a phantom study
JF  - European Radiology
N2  - Objectives To compare image quality of deep learning reconstruction (AiCE) for radiomics feature extraction with filtered back projection (FBP), hybrid iterative reconstruction (AIDR 3D), and model-based iterative reconstruction (FIRST). Methods Effects of image reconstruction on radiomics features were investigated using a phantom that realistically mimicked a 65-year-old patient's abdomen with hepatic metastases. The phantom was scanned at 18 doses from 0.2 to 4 mGy, with 20 repeated scans per dose. Images were reconstructed with FBP, AIDR 3D, FIRST, and AiCE. Ninety-three radiomics features were extracted from 24 regions of interest, which were evenly distributed across three tissue classes: normal liver, metastatic core, and metastatic rim. Features were analyzed in terms of their consistent characterization of tissues within the same image (intraclass correlation coefficient >= 0.75), discriminative power (Kruskal-Wallis test p value < 0.05), and repeatability (overall concordance correlation coefficient >= 0.75). Results The median fraction of consistent features across all doses was 6%, 8%, 6%, and 22% with FBP, AIDR 3D, FIRST, and AiCE, respectively. Adequate discriminative power was achieved by 48%, 82%, 84%, and 92% of features, and 52%, 20%, 17%, and 39% of features were repeatable, respectively. Only 5% of features combined consistency, discriminative power, and repeatability with FBP, AIDR 3D, and FIRST versus 13% with AiCE at doses above 1 mGy and 17% at doses >= 3 mGy. AiCE was the only reconstruction technique that enabled extraction of higher-order features. Conclusions AiCE more than doubled the yield of radiomics features at doses typically used clinically. Inconsistent tissue characterization within CT images contributes significantly to the poor stability of radiomics features.
KW  - Tomography
KW  - X-ray computed
KW  - Phantoms
KW  - imaging
KW  - Liver neoplasms
KW  - Algorithms
KW  - Reproducibility of results
Y1  - 2022
U6  - https://doi.org/10.1007/s00330-022-08592-y
SN  - 1432-1084
VL  - 32
IS  - 7
SP  - 4587
EP  - 4595
PB  - Springer
CY  - New York
ER  - 
TY  - JOUR
A1  - Marco Figuera, Ramiro
A1  - Riedel, Christian
A1  - Rossi, Angelo Pio
A1  - Unnithan, Vikram
T1  - Depth to diameter analysis on small simple craters at the lunar south pole - possible implications for ice harboring
JF  - Remote sensing
N2  - In this paper, we present a study comparing the depth to diameter (d/D) ratio of small simple craters (200-1000 m) of an area between -88.5 degrees to -90 degrees latitude at the lunar south pole containing Permanent Shadowed Regions (PSRs) versus craters without PSRs. As PSRs can reach temperatures of 110 K and are capable of harboring volatiles, especially water ice, we analyzed the relationship of depth versus diameter ratios and its possible implications for harboring water ice. Variations in the d/D ratios can also be caused by other processes such as degradation, isostatic adjustment, or differences in surface properties. The conducted d/D ratio analysis suggests that a differentiation between craters containing PSRs versus craters without PSRs occurs. Thus, a possible direct relation between d/D ratio, PSRs, and water ice harboring might exist. Our results suggest that differences in the target's surface properties may explain the obtained results. The resulting d/D ratios of craters with PSRs can help to select target areas for future In-Situ Resource Utilization (ISRU) missions.
KW  - craters
KW  - lunar exploration
KW  - ice harboring
Y1  - 2022
U6  - https://doi.org/10.3390/rs14030450
SN  - 2072-4292
VL  - 14
IS  - 3
PB  - MDPI
CY  - Basel
ER  - 
TY  - JOUR
A1  - Möring, Sebastian
A1  - Leino, Olli Tapio
T1  - Die neoliberale Bedingung von Computerspielen
JF  - Kontrollmaschinen - zur Dispositivtheorie des Computerspiels
Y1  - 2022
SN  - 978-3-643-14780-6
SP  - 41
EP  - 61
PB  - LiteraturWissenschaft.de
CY  - Münster
ER  - 
TY  - JOUR
A1  - Breitenreiter, Anselm
A1  - Andjelković, Marko
A1  - Schrape, Oliver
A1  - Krstić, Miloš
T1  - Fast error propagation probability estimates by answer set programming and approximate model counting
JF  - IEEE Access
N2  - We present a method employing Answer Set Programming in combination with Approximate Model Counting for fast and accurate calculation of error propagation probabilities in digital circuits. By an efficient problem encoding, we achieve an input data format similar to a Verilog netlist so that extensive preprocessing is avoided. By a tight interconnection of our application with the underlying solver, we avoid iterating over fault sites and reduce calls to the solver. Several circuits were analyzed with varying numbers of considered cycles and different degrees of approximation. Our experiments show, that the runtime can be reduced by approximation by a factor of 91, whereas the error compared to the exact result is below 1%.
KW  - Circuit faults
KW  - Integrated circuit modeling
KW  - Programming
KW  - Analytical models
KW  - Search problems
KW  - Flip-flops
KW  - Encoding
KW  - Answer set programming
KW  - approximate model counting
KW  - error propagation
KW  - radhard design
KW  - reliability analysis
KW  - selective fault tolerance
KW  - single event upsets
Y1  - 2022
U6  - https://doi.org/10.1109/ACCESS.2022.3174564
SN  - 2169-3536
VL  - 10
SP  - 51814
EP  - 51825
PB  - Inst. of Electr. and Electronics Engineers
CY  - Piscataway
ER  - 
TY  - JOUR
A1  - Prasse, Paul
A1  - Iversen, Pascal
A1  - Lienhard, Matthias
A1  - Thedinga, Kristina
A1  - Bauer, Christopher
A1  - Herwig, Ralf
A1  - Scheffer, Tobias
T1  - Matching anticancer compounds and tumor cell lines by neural networks with ranking loss
JF  - NAR: genomics and bioinformatics
N2  - Computational drug sensitivity models have the potential to improve therapeutic outcomes by identifying targeted drug components that are likely to achieve the highest efficacy for a cancer cell line at hand at a therapeutic dose. State of the art drug sensitivity models use regression techniques to predict the inhibitory concentration of a drug for a tumor cell line. This regression objective is not directly aligned with either of these principal goals of drug sensitivity models: We argue that drug sensitivity modeling should be seen as a ranking problem with an optimization criterion that quantifies a drug's inhibitory capacity for the cancer cell line at hand relative to its toxicity for healthy cells. We derive an extension to the well-established drug sensitivity regression model PaccMann that employs a ranking loss and focuses on the ratio of inhibitory concentration and therapeutic dosage range. We find that the ranking extension significantly enhances the model's capability to identify the most effective anticancer drugs for unseen tumor cell profiles based in on in-vitro data.
Y1  - 2022
U6  - https://doi.org/10.1093/nargab/lqab128
SN  - 2631-9268
VL  - 4
IS  - 1
PB  - Oxford Univ. Press
CY  - Oxford
ER  - 
TY  - THES
A1  - Klockmann, Alexander
T1  - Modifizierte Unidirektionale Codes für Speicherfehler
N2  - Das Promotionsvorhaben verfolgt das Ziel, die Zuverlässigkeit der Datenspeicherung und die Speicherdichte von neu entwickelten Speichern (Emerging Memories) mit Multi-Level-Speicherzellen zu verbessern bzw. zu erhöhen. Hierfür werden Codes zur Erkennung von unidirektionalen Fehlern analysiert, modifiziert und neu entwickelt, um sie innerhalb der neuen Speicher anwenden zu können. Der Fokus liegt dabei auf sog. Berger-Codes und m-aus-n-Codes. Da Multi-Level-Speicherzellen nicht mehr binär, sondern mit mehreren Leveln arbeiten, können bisher verwendete Codes nicht mehr verwendet werden, bzw. müssen entsprechend angepasst werden. Auf Basis der Berger-Codes und m-aus-n-Codes werden in dieser Arbeit neue Codes abgeleitet, welche in der Lage sind, Daten auch in mehrwertigen Systemen zu schützen.
KW  - Fehlererkennung
KW  - Codierungstheorie
KW  - Speicher
KW  - unidirektionale Fehler
Y1  - 2022
ER  - 
TY  - JOUR
A1  - Prasse, Paul
A1  - Iversen, Pascal
A1  - Lienhard, Matthias
A1  - Thedinga, Kristina
A1  - Herwig, Ralf
A1  - Scheffer, Tobias
T1  - Pre-Training on In Vitro and Fine-Tuning on Patient-Derived Data Improves Deep Neural Networks for Anti-Cancer Drug-Sensitivity Prediction
JF  - MDPI
N2  - Large-scale databases that report the inhibitory capacities of many combinations of candidate drug compounds and cultivated cancer cell lines have driven the development of preclinical drug-sensitivity models based on machine learning. However, cultivated cell lines have devolved from human cancer cells over years or even decades under selective pressure in culture conditions. Moreover, models that have been trained on in vitro data cannot account for interactions with other types of cells. Drug-response data that are based on patient-derived cell cultures, xenografts, and organoids, on the other hand, are not available in the quantities that are needed to train high-capacity machine-learning models. We found that pre-training deep neural network models of drug sensitivity on in vitro drug-sensitivity databases before fine-tuning the model parameters on patient-derived data improves the models’ accuracy and improves the biological plausibility of the features, compared to training only on patient-derived data. From our experiments, we can conclude that pre-trained models outperform models that have been trained on the target domains in the vast majority of cases.
KW  - deep neural networks
KW  - drug-sensitivity prediction
KW  - anti-cancer drugs
Y1  - 2022
U6  - https://doi.org/10.3390/cancers14163950
SN  - 2072-6694
VL  - 14
SP  - 1
EP  - 14
PB  - MDPI
CY  - Basel, Schweiz
ET  - 16
ER  - 
TY  - JOUR
A1  - Ristic, Goran S.
A1  - Ilic, Stefan D.
A1  - Andjelkovic, Marko S.
A1  - Duane, Russell
A1  - Palma, Alberto J.
A1  - Lalena, Antonio M.
A1  - Krstić, Miloš
A1  - Jaksic, Aleksandar B.
T1  - Sensitivity and fading of irradiated RADFETs with different gate voltages
JF  - Nuclear Instruments and Methods in Physics Research Section A
N2  - The radiation-sensitive field-effect transistors (RADFETs) with an oxide thickness of 400 nm are irradiated with gate voltages of 2, 4 and 6 V, and without gate voltage. 
A detailed analysis of the mechanisms responsible for the creation of traps during irradiation is performed. 
The creation of the traps in the oxide, near and at the silicon/silicon-dioxide (Si/SiO2) interface during irradiation is modelled very well. This modelling can also be used for other MOS transistors containing SiO2. 

The behaviour of radiation traps during postirradiation annealing is analysed, and the corresponding functions for their modelling are obtained. The switching traps (STs) do not have significant influence on threshold voltage shift, and two radiation-induced trap types fit the fixed traps (FTs) very well. The fading does not depend on the positive gate voltage applied during irradiation, but it is twice lower in case there is no gate voltage. 

A new dosimetric parameter, called the Golden Ratio (GR), is proposed, which represents the ratio between the threshold voltage shift after irradiation and fading after spontaneous annealing. This parameter can be useful for comparing MOS dosimeters.
KW  - pMOS radiation dosimeter
KW  - RADFETs
KW  - irradiation
KW  - sensitivity
KW  - annealing
KW  - fading
Y1  - 2022
U6  - https://doi.org/10.1016/j.nima.2022.166473
SN  - 0168-9002
SN  - 1872-9576
VL  - 1029
PB  - Elsevier
CY  - Amsterdam
ER  - 
TY  - JOUR
A1  - Chen, Junchao
A1  - Lange, Thomas
A1  - Andjelkovic, Marko
A1  - Simevski, Aleksandar
A1  - Lu, Li
A1  - Krstić, Miloš
T1  - Solar particle event and single event upset prediction from SRAM-based monitor and supervised machine learning
JF  - IEEE transactions on emerging topics in computing / IEEE Computer Society, Institute of Electrical and Electronics Engineers
N2  - The intensity of cosmic radiation may differ over five orders of magnitude within a few hours or days during the Solar Particle Events (SPEs), thus increasing for several orders of magnitude the probability of Single Event Upsets (SEUs) in space-borne electronic systems. Therefore, it is vital to enable the early detection of the SEU rate changes in order to ensure timely activation of dynamic radiation hardening measures. In this paper, an embedded approach for the prediction of SPEs and SRAM SEU rate is presented. The proposed solution combines the real-time SRAM-based SEU monitor, the offline-trained machine learning model and online learning algorithm for the prediction. With respect to the state-of-the-art, our solution brings the following benefits: (1) Use of existing on-chip data storage SRAM as a particle detector, thus minimizing the hardware and power overhead, (2) Prediction of SRAM SEU rate one hour in advance, with the fine-grained hourly tracking of SEU variations during SPEs as well as under normal conditions, (3) Online optimization of the prediction model for enhancing the prediction accuracy during run-time, (4) Negligible cost of hardware accelerator design for the implementation of selected machine learning model and online learning algorithm. The proposed design is intended for a highly dependable and self-adaptive multiprocessing system employed in space applications, allowing to trigger the radiation mitigation mechanisms before the onset of high radiation levels.
KW  - Machine learning
KW  - Single event upsets
KW  - Random access memory
KW  - monitoring
KW  - machine learning algorithms
KW  - predictive models
KW  - space missions
KW  - solar particle event
KW  - single event upset
KW  - machine learning
KW  - online learning
KW  - hardware accelerator
KW  - reliability
KW  - self-adaptive multiprocessing system
Y1  - 2022
U6  - https://doi.org/10.1109/TETC.2022.3147376
SN  - 2168-6750
VL  - 10
IS  - 2
SP  - 564
EP  - 580
PB  - Institute of Electrical and Electronics Engineers
CY  - [New York, NY]
ER  - 
TY  - JOUR
A1  - Bandyopadhyay, Soumyadip
A1  - Sarkar, Dipankar
A1  - Mandal, Chittaranjan
A1  - Giese, Holger
T1  - Translation validation of coloured Petri net models of programs on integers
JF  - Acta informatica
N2  - Programs are often subjected to significant optimizing and parallelizing transformations based on extensive dependence analysis. Formal validation of such transformations needs modelling paradigms which can capture both control and data dependences in the program vividly. Being value-based with an inherent scope of capturing parallelism, the untimed coloured Petri net (CPN) models, reported in the literature, fit the bill well; accordingly, they are likely to be more convenient as the intermediate representations (IRs) of both the source and the transformed codes for translation validation than strictly sequential variable-based IRs like sequential control flow graphs (CFGs). In this work, an efficient path-based equivalence checking method for CPN models of programs on integers is presented. Extensive experimentation has been carried out on several sequential and parallel examples. Complexity and correctness issues have been treated rigorously for the method.
Y1  - 2022
U6  - https://doi.org/10.1007/s00236-022-00419-z
SN  - 0001-5903
SN  - 1432-0525
VL  - 59
IS  - 6
SP  - 725
EP  - 759
PB  - Springer
CY  - New York
ER  - 
TY  - JOUR
A1  - Hecher, Markus
T1  - Treewidth-aware reductions of normal ASP to SAT
BT  - is normal ASP harder than SAT after all?
JF  - Artificial intelligence
N2  - 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.
KW  - Answer set programming
KW  - Treewidth
KW  - Parameterized complexity
KW  - Complexity
KW  - analysis
KW  - Tree decomposition
KW  - Treewidth-aware reductions
Y1  - 2022
U6  - https://doi.org/10.1016/j.artint.2021.103651
SN  - 0004-3702
SN  - 1872-7921
VL  - 304
PB  - Elsevier
CY  - Amsterdam
ER  -