56508
2020
2020
eng
29
44
354
article
Elsevier
Amsterdam [u.a.]
1
2020-11-24
2020-11-24
--
Towards an answer set programming methodology for constructing programs following a semi-automatic approach
Answer Set Programming (ASP) is a successful rule-based formalism for modeling and solving knowledge-intense combinatorial (optimization) problems. Despite its success in both academic and industry, open challenges like automatic source code optimization, and software engineering remains. This is because a problem encoded into an ASP might not have the desired solving performance compared to an equivalent representation. Motivated by these two challenges, this paper has three main contributions. First, we propose a developing process towards a methodology to implement ASP programs, being faithful to existing methods. Second, we present ASP encodings that serve as the basis from the developing process. Third, we demonstrate the use of ASP to reverse the standard solving process. That is, knowing answer sets in advance, and desired strong equivalent properties, “we” exhaustively reconstruct ASP programs if they exist. This paper was originally motivated by the search of propositional formulas (if they exist) that represent the semantics of a new aggregate operator. Particularly, a parity aggregate. This aggregate comes as an improvement from the already existing parity (xor) constraints from xorro, where lacks expressiveness, even though these constraints fit perfectly for reasoning modes like sampling or model counting. To this end, this extended version covers the fundaments from parity constraints as well as the xorro system. Hence, we delve a little more in the examples and the proposed methodology over parity constraints. Finally, we discuss our results by showing the only representation available, that satisfies different properties from the classical logic xor operator, which is also consistent with the semantics of parity constraints from xorro.
Electronic notes in theoretical computer science
extended and revised version
10.1016/j.entcs.2020.10.004
1571-0661
outputup:dataSource:ScienceDirect:2020
Universidad de las Americas Puebla, Mexico, flavio.everardo@cs.uni-potsdamde; osoriomauri@gmail.com
Osorio, Mauricio
2022-10-27T06:07:23+00:00
sword
importub
filename=package.tar
952bf00ac9870b7827e5d6b90430757f
2033227-0
false
true
CC-BY-NC-ND - Namensnennung, nicht kommerziell, keine Bearbeitungen 4.0 International
Flavio Omar Everardo Pérez
Mauricio Osorio
eng
uncontrolled
answer set programming
eng
uncontrolled
combinatorial optimization problems
eng
uncontrolled
parity aggregate operator
Informatik, Informationswissenschaft, allgemeine Werke
Institut für Informatik und Computational Science
Referiert
Import
Gold Open-Access
DOAJ gelistet
5765
2011
2012
eng
doctoralthesis
1
2012-06-01
--
2012-03-13
Modeling biological systems with Answer Set Programming
Modellierung biologischer Systeme mit Answer Set Programming
Biology has made great progress in identifying and measuring the building blocks of life. The availability of high-throughput methods in molecular biology has dramatically accelerated the growth of biological knowledge for various organisms. The advancements in genomic, proteomic and metabolomic technologies allow for constructing complex models of biological systems. An increasing number of biological repositories is available on the web, incorporating thousands of biochemical reactions and genetic regulations. Systems Biology is a recent research trend in life science, which fosters a systemic view on biology. In Systems Biology one is interested in integrating the knowledge from all these different sources into models that capture the interaction of these entities. By studying these models one wants to understand the emerging properties of the whole system, such as robustness. However, both measurements as well as biological networks are prone to considerable incompleteness, heterogeneity and mutual inconsistency, which makes it highly non-trivial to draw biologically meaningful conclusions in an automated way. Therefore, we want to promote Answer Set Programming (ASP) as a tool for discrete modeling in Systems Biology. ASP is a declarative problem solving paradigm, in which a problem is encoded as a logic program such that its answer sets represent solutions to the problem. ASP has intrinsic features to cope with incompleteness, offers a rich modeling language and highly efficient solving technology. We present ASP solutions, for the analysis of genetic regulatory networks, determining consistency with observed measurements and identifying minimal causes for inconsistency. We extend this approach for computing minimal repairs on model and data that restore consistency. This method allows for predicting unobserved data even in case of inconsistency. Further, we present an ASP approach to metabolic network expansion. This approach exploits the easy characterization of reachability in ASP and its various reasoning methods, to explore the biosynthetic capabilities of metabolic reaction networks and generate hypotheses for extending the network. Finally, we present the BioASP library, a Python library which encapsulates our ASP solutions into the imperative programming paradigm. The library allows for an easy integration of ASP solution into system rich environments, as they exist in Systems Biology.
In den letzten Jahren wurden große Fortschritte bei der Identifikation und Messung der Bausteine des Lebens gemacht. Die Verfügbarkeit von Hochdurchsatzverfahren in der Molekularbiology hat das Anwachsen unseres biologischen Wissens dramatisch beschleunigt. Durch die technische Fortschritte in Genomic, Proteomic und Metabolomic wurde die Konstruktion komplexer Modelle biologischer Systeme ermöglicht. Immer mehr biologische Datenbanken sind über das Internet verfügbar, sie enthalten tausende Daten biochemischer Reaktionen und genetischer Regulation. System Biologie ist ein junger Forschungszweig der Biologie, der versucht Biologische Systeme in ihrer Ganzheit zu erforschen. Dabei ist man daran interessiert möglichst viel Wissen aus den unterschiedlichsten Bereichen in ein Modell zu aggregieren, welches das Zusammenwirken der verschiedensten Komponenten nachbildet. Durch das Studium derartiger Modelle erhofft man sich ein Verständnis der aufbauenden Eigenschaften, wie zum Beispiel Robustheit, des Systems zu erlangen. Es stellt sich jedoch die Problematik, das sowohl die biologischen Modelle als auch die verfügbaren Messwerte, oft unvollständig, miteinander unvereinbar oder fehlerhaft sind. All dies macht es schwierig biologisch sinnvolle Schlussfolgerungen zu ziehen. Daher, möchten wir in dieser Arbeit Antwortmengen Programmierung (engl. Answer Set Programming; ASP) als Werkzeug zur diskreten Modellierung system biologischer Probleme vorschlagen. ASP verfügt über eingebaute Eigenschaften zum Umgang mit unvollständiger Information, eine reichhaltige Modellierungssprache und hocheffiziente Berechnungstechniken. Wir präsentieren ASP Lösungen zur Analyse von Netzwerken genetischer Regulierungen, zur Prüfung der Konsistenz mit gemessene Daten, und zur Identifikation von Gründen für Inkonsistenz. Diesen Ansatz erweitern wir um die Möglichkeit zur Berechnung minimaler Reparaturen an Modell und Daten, welche Konsistenz erzeugen. Mithilfe dieser Methode werden wir in die Lage versetzt, auch im Fall von Inkonsistenz, noch ungemessene Daten vorherzusagen. Weiterhin, präsentieren wir einen ASP Ansatz zur Analyse metabolischer Netzwerke. Bei diesem Ansatz, nutzen wir zum einen aus das sich Erreichbarkeit mit ASP leicht spezifizieren lässt und das ASP mehrere mächtige Methoden zur Schlussfolgerung bereitstellt, welche sich auch kombiniert lassen. Dadurch wird es möglich die Synthese Möglichkeiten eines Metabolischen Netzwerks zu erforschen und Hypothesen für Erweiterungen des metabolischen Netzwerks zu berechnen. Zu guter Letzt, präsentieren wir die BioASP Softwarebibliothek. Die BioASP-Bibliothek kapselt unsere ASP Lösungen in das imperative Programmierparadigma und vereinfacht eine Integration von ASP Lösungen in heterogene Betriebsumgebungen, wie sie in der System Biologie vorherrschen.
urn:nbn:de:kobv:517-opus-59383
5938
WD 9200, WC 7700
Potsdam, Uni., Diss., 2012
Sven Thiele
deu
uncontrolled
Antwortmengen Programmierung
deu
uncontrolled
System Biologie
deu
uncontrolled
Inkonsistenz
deu
uncontrolled
Unvollständigkeit
deu
uncontrolled
Reparatur
eng
uncontrolled
answer set programming
eng
uncontrolled
systems biology
eng
uncontrolled
inconsistency
eng
uncontrolled
incompleteness
eng
uncontrolled
repair
Datenverarbeitung; Informatik
open_access
Institut für Informatik und Computational Science
Universität Potsdam
Universität Potsdam
https://publishup.uni-potsdam.de/files/5765/thiele_diss.pdf
1134
2007
eng
doctoralthesis
1
2007-01-29
--
2007-01-15
Preferences in answer set programming
Präferenzen in der Antwortmengenprogrammierung
Answer Set Programming (ASP) emerged in the late 1990s as a new logic programming paradigm, having its roots in nonmonotonic reasoning, deductive databases, and logic programming with negation as failure. The basic idea of ASP is to represent a computational problem as a logic program whose answer sets correspond to solutions, and then to use an answer set solver for finding answer sets of the program. ASP is particularly suited for solving NP-complete search problems. Among these, we find applications to product configuration, diagnosis, and graph-theoretical problems, e.g. finding Hamiltonian cycles. On different lines of ASP research, many extensions of the basic formalism have been proposed. The most intensively studied one is the modelling of preferences in ASP. They constitute a natural and effective way of selecting preferred solutions among a plethora of solutions for a problem. For example, preferences have been successfully used for timetabling, auctioning, and product configuration. In this thesis, we concentrate on preferences within answer set programming. Among several formalisms and semantics for preference handling in ASP, we concentrate on ordered logic programs with the underlying D-, W-, and B-semantics. In this setting, preferences are defined among rules of a logic program. They select preferred answer sets among (standard) answer sets of the underlying logic program. Up to now, those preferred answer sets have been computed either via a compilation method or by meta-interpretation. Hence, the question comes up, whether and how preferences can be integrated into an existing ASP solver. To solve this question, we develop an operational graph-based framework for the computation of answer sets of logic programs. Then, we integrate preferences into this operational approach. We empirically observe that our integrative approach performs in most cases better than the compilation method or meta-interpretation. Another research issue in ASP are optimization methods that remove redundancies, as also found in database query optimizers. For these purposes, the rather recently suggested notion of strong equivalence for ASP can be used. If a program is strongly equivalent to a subprogram of itself, then one can always use the subprogram instead of the original program, a technique which serves as an effective optimization method. Up to now, strong equivalence has not been considered for logic programs with preferences. In this thesis, we tackle this issue and generalize the notion of strong equivalence to ordered logic programs. We give necessary and sufficient conditions for the strong equivalence of two ordered logic programs. Furthermore, we provide program transformations for ordered logic programs and show in how far preferences can be simplified. Finally, we present two new applications for preferences within answer set programming. First, we define new procedures for group decision making, which we apply to the problem of scheduling a group meeting. As a second new application, we reconstruct a linguistic problem appearing in German dialects within ASP. Regarding linguistic studies, there is an ongoing debate about how unique the rule systems of language are in human cognition. The reconstruction of grammatical regularities with tools from computer science has consequences for this debate: if grammars can be modelled this way, then they share core properties with other non-linguistic rule systems.
Die Antwortmengenprogrammierung entwickelte sich in den späten 90er Jahren als neues Paradigma der logischen Programmierung und ist in den Gebieten des nicht-monotonen Schließens und der deduktiven Datenbanken verwurzelt. Dabei wird eine Problemstellung als logisches Programm repräsentiert, dessen Lösungen, die so genannten Antwortmengen, genau den Lösungen des ursprünglichen Problems entsprechen. Die Antwortmengenprogrammierung bildet ein geeignetes Fundament zur Repräsentation und zum Lösen von Entscheidungs- und Suchproblemen in der Komplexitätsklasse NP. Anwendungen finden wir unter anderem in der Produktkonfiguration, Diagnose und bei graphen-theoretischen Problemen, z.B. der Suche nach Hamiltonschen Kreisen. In den letzten Jahren wurden viele Erweiterungen der Antwortmengenprogrammierung betrachtet. Die am meisten untersuchte Erweiterung ist die Modellierung von Präferenzen. Diese bilden eine natürliche und effektive Möglichkeit, unter einer Vielzahl von Lösungen eines Problems bevorzugte Lösungen zu selektieren. Präferenzen finden beispielsweise in der Stundenplanung, bei Auktionen und bei Produktkonfigurationen ihre Anwendung. Der Schwerpunkt dieser Arbeit liegt in der Modellierung, Implementierung und Anwendung von Präferenzen in der Antwortmengenprogrammierung. Da es verschiedene Ansätze gibt, um Präferenzen darzustellen, konzentrieren wir uns auf geordnete logische Programme, wobei Präferenzen als partielle Ordnung der Regeln eines logischen Programms ausgedrückt werden. Dabei betrachten wir drei verschiedene Semantiken zur Interpretation dieser Präferenzen. Im Vorfeld wurden für diese Semantiken die bevorzugten Antwortmengen durch einen Compiler oder durch Meta-Interpretation berechnet. Da Präferenzen Lösungen selektieren, stellt sich die Frage, ob es möglich ist, diese direkt in den Berechnungsprozeß von präferenzierten Antwortmengen zu integrieren, so dass die bevorzugten Antwortmengen ohne Zwischenschritte berechnet werden können. Dazu entwickeln wir zuerst ein auf Graphen basierendes Gerüst zur Berechnung von Antwortmengen. Anschließend werden wir darin Präferenzen integrieren, so dass bevorzugte Antwortmengen ohne Compiler oder Meta-Interpretation berechnet werden. Es stellt sich heraus, dass die integrative Methode auf den meisten betrachteten Problemklassen wesentlich leistungsfähiger ist als der Compiler oder Meta-Interpretation. Ein weiterer Schwerpunkt dieser Arbeit liegt in der Frage, inwieweit sich geordnete logische Programme vereinfachen lassen. Dazu steht die Methodik der strengen Äquivalenz von logischen Programmen zur Verfügung. Wenn ein logisches Programm streng äquivalent zu einem seiner Teilprogramme ist, so kann man dieses durch das entsprechende Teilprogramm ersetzen, ohne dass sich die zugrunde liegende Semantik ändert. Bisher wurden strenge Äquivalenzen nicht für logische Programme mit Präferenzen untersucht. In dieser Arbeit definieren wir erstmalig strenge Äquivalenzen für geordnete logische Programme. Wir geben notwendige und hinreichende Bedingungen für die strenge Äquivalenz zweier geordneter logischer Programme an. Des Weiteren werden wir auch die Frage beantworten, inwieweit geordnete logische Programme und deren Präferenzstrukturen vereinfacht werden können. Abschließend präsentieren wir zwei neue Anwendungsbereiche von Präferenzen in der Antwortmengenprogrammierung. Zuerst definieren wir neue Prozeduren zur Entscheidungsfindung innerhalb von Gruppenprozessen. Diese integrieren wir anschließend in das Problem der Planung eines Treffens für eine Gruppe. Als zweite neue Anwendung rekonstruieren wir mit Hilfe der Antwortmengenprogrammierung eine linguistische Problemstellung, die in deutschen Dialekten auftritt. Momentan wird im Bereich der Linguistik darüber diskutiert, ob Regelsysteme von (menschlichen) Sprachen einzigartig sind oder nicht. Die Rekonstruktion von grammatikalischen Regularitäten mit Werkzeugen aus der Informatik erlaubt die Unterstützung der These, dass linguistische Regelsysteme Gemeinsamkeiten zu anderen nicht-linguistischen Regelsystemen besitzen.
urn:nbn:de:kobv:517-opus-12058
1205
ST 230
Kathrin Konczak
deu
uncontrolled
Präferenzen
deu
uncontrolled
Antwortmengenprogrammierung
deu
uncontrolled
logische Programmierung
deu
uncontrolled
Künstliche Intelligenz
eng
uncontrolled
preferences
eng
uncontrolled
priorities
eng
uncontrolled
answer set programming
eng
uncontrolled
logic programming
eng
uncontrolled
artificial intelligence
Datenverarbeitung; Informatik
open_access
Institut für Informatik und Computational Science
Universität Potsdam
Universität Potsdam
https://publishup.uni-potsdam.de/files/1134/konczak_diss.pdf
46968
2019
2020
eng
671
687
19
1060
postprint
1
2020-12-22
2020-12-22
--
Founded (auto)epistemic equilibrium logic satisfies epistemic splitting
In a recent line of research, two familiar concepts from logic programming semantics (unfounded sets and splitting) were extrapolated to the case of epistemic logic programs. The property of epistemic splitting provides a natural and modular way to understand programs without epistemic cycles but, surprisingly, was only fulfilled by Gelfond's original semantics (G91), among the many proposals in the literature. On the other hand, G91 may suffer from a kind of self-supported, unfounded derivations when epistemic cycles come into play. Recently, the absence of these derivations was also formalised as a property of epistemic semantics called foundedness. Moreover, a first semantics proved to satisfy foundedness was also proposed, the so-called Founded Autoepistemic Equilibrium Logic (FAEEL). In this paper, we prove that FAEEL also satisfies the epistemic splitting property something that, together with foundedness, was not fulfilled by any other approach up to date. To prove this result, we provide an alternative characterisation of FAEEL as a combination of G91 with a simpler logic we called Founded Epistemic Equilibrium Logic (FEEL), which is somehow an extrapolation of the stable model semantics to the modal logic S5.
Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe
10.25932/publishup-46968
urn:nbn:de:kobv:517-opus4-469685
1866-8372
online registration
Theory and Practice of Logic Programming 19 (2019) 5–6, 671–687 DOI: 10.1017/S1471068419000127
true
true
CC-BY - Namensnennung 4.0 International
Jorge Fandinno
Zweitveröffentlichungen der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe
1060
eng
uncontrolled
answer set programming
eng
uncontrolled
epistemic specifications
eng
uncontrolled
epistemic logic programs
Datenverarbeitung; Informatik
open_access
Institut für Informatik und Computational Science
Referiert
Cambridge University Press (CUP)
Green Open-Access
Universität Potsdam
https://publishup.uni-potsdam.de/files/46968/pmnr1060.pdf
52627
2018
2018
eng
520
534
15
3-4
18
article
Cambridge Univ. Press
New York
1
--
2018-08-10
--
Routing driverless transport vehicles in car assembly with answer set programming
Automated storage and retrieval systems are principal components of modern production and warehouse facilities. In particular, automated guided vehicles nowadays substitute human-operated pallet trucks in transporting production materials between storage locations and assembly stations. While low-level control systems take care of navigating such driverless vehicles along programmed routes and avoid collisions even under unforeseen circumstances, in the common case of multiple vehicles sharing the same operation area, the problem remains how to set up routes such that a collection of transport tasks is accomplished most effectively. We address this prevalent problem in the context of car assembly at Mercedes-Benz Ludwigsfelde GmbH, a large-scale producer of commercial vehicles, where routes for automated guided vehicles used in the production process have traditionally been hand-coded by human engineers. Such adhoc methods may suffice as long as a running production process remains in place, while any change in the factory layout or production targets necessitates tedious manual reconfiguration, not to mention the missing portability between different production plants. Unlike this, we propose a declarative approach based on Answer Set Programming to optimize the routes taken by automated guided vehicles for accomplishing transport tasks. The advantages include a transparent and executable problem formalization, provable optimality of routes relative to objective criteria, as well as elaboration tolerance towards particular factory layouts and production targets. Moreover, we demonstrate that our approach is efficient enough to deal with the transport tasks evolving in realistic production processes at the car factory of Mercedes-Benz Ludwigsfelde GmbH.
Theory and practice of logic programming
10.1017/S1471068418000182
1471-0684
1475-3081
wos:2018
34th International Conference on Logic Programming (ICLP)
JUL 14-17, 2018
WOS:000441294400015
Oxford, ENGLAND
Gebser, M (reprint author), Univ Potsdam, Potsdam, Germany., gebser@cs.uni-potsdam.de
DFGGerman Research Foundation (DFG) [SCHA 550/9]
2021-11-12T11:45:08+00:00
sword
importub
filename=package.tar
484134d51b944db9d163ccb3132301cd
false
true
Martin Gebser
Philipp Obermeier
Torsten H. Schaub
Michel Ratsch-Heitmann
Mario Runge
eng
uncontrolled
automated guided vehicle routing
eng
uncontrolled
car assembly operations
eng
uncontrolled
answer set programming
Informatik, Informationswissenschaft, allgemeine Werke
Institut für Informatik und Computational Science
Import
49693
2019
2019
eng
477
504
28
3
19
article
Cambridge Univ. Press
New York
1
2019-01-18
2019-01-18
--
plasp 3
We describe the new version of the Planning Domain Definition Language (PDDL)-to-Answer Set Programming (ASP) translator plasp. First, it widens the range of accepted PDDL features. Second, it contains novel planning encodings, some inspired by Satisfiability Testing (SAT) planning and others exploiting ASP features such as well-foundedness. All of them are designed for handling multivalued fluents in order to capture both PDDL as well as SAS planning formats. Third, enabled by multishot ASP solving, it offers advanced planning algorithms also borrowed from SAT planning. As a result, plasp provides us with an ASP-based framework for studying a variety of planning techniques in a uniform setting. Finally, we demonstrate in an empirical analysis that these techniques have a significant impact on the performance of ASP planning.
Theory and practice of logic programming
Towards Effective ASP Planning
10.1017/S1471068418000583
1471-0684
1475-3081
wos:2019
WOS:000462850000004
Dimopoulos, Y (reprint author), Univ Cyprus, Nicosia, Cyprus., yannis@cs.ucy.ac.cy; martin.gebser@aau.at; patrick.luehne@cs.uni-potsdam.de; javier@cs.uni-potsdam.de; torsten@cs.uni-potsdam.de
DFGGerman Research Foundation (DFG) [SCHA 550/9]; KWF [28472]; cms electronics GmbH; FunderMax GmbH; Hirsch Armbander GmbH; IT GmbH; Infineon Technologies Austria AG; Isovolta AG; Kostwein Holding GmbH; Privatstiftung Karntner Sparkasse
2021-03-01T13:01:15+00:00
sword
importub
filename=package.tar
7c91b934ddd8cd90bc4c06c2d33753e3
Dimopoulos, Yannis
false
true
Yannis Dimopoulos
Martin Gebser
Patrick Lühne
Javier Romero Davila
Torsten H. Schaub
eng
uncontrolled
knowledge representation and nonmonotonic reasoning
eng
uncontrolled
technical notes and rapid communications
eng
uncontrolled
answer set programming
eng
uncontrolled
automated planning
eng
uncontrolled
action and change
Datenverarbeitung; Informatik
Institut für Informatik und Computational Science
Referiert
Import
Green Open-Access
50840
2019
2019
eng
83
108
26
1
19
article
Cambridge University Press
New York
1
2018-11-09
2018-11-09
--
Hybrid metabolic network completion
Metabolic networks play a crucial role in biology since they capture all chemical reactions in an organism. While there are networks of high quality for many model organisms, networks for less studied organisms are often of poor quality and suffer from incompleteness. To this end, we introduced in previous work an answer set programming (ASP)-based approach to metabolic network completion. Although this qualitative approach allows for restoring moderately degraded networks, it fails to restore highly degraded ones. This is because it ignores quantitative constraints capturing reaction rates. To address this problem, we propose a hybrid approach to metabolic network completion that integrates our qualitative ASP approach with quantitative means for capturing reaction rates. We begin by formally reconciling existing stoichiometric and topological approaches to network completion in a unified formalism. With it, we develop a hybrid ASP encoding and rely upon the theory reasoning capacities of the ASP system dingo for solving the resulting logic program with linear constraints over reals. We empirically evaluate our approach by means of the metabolic network of Escherichia coli. Our analysis shows that our novel approach yields greatly superior results than obtainable from purely qualitative or quantitative approaches.
Theory and practice of logic programming
10.1017/S1471068418000455
1471-0684
1475-3081
wos:2019
WOS:000454429700003
Frioux, C (reprint author), Univ Rennes, Inria, CNRS, IRISA, F-35000 Rennes, France., clemence.frioux@inria.fr; torsten@cs.uni-potsdam.de; seschell@cs.uni-potsdam.de; anne.siegel@irisa.fr; wanko@cs.uni-potsdam.de
DFGGerman Research Foundation (DFG) [SCHA 550/9, 11]; French Government via the National Research Agency investment expenditure program IDEALG [ANR-10-BTBR-04]
2021-05-28T12:09:24+00:00
sword
importub
filename=package.tar
a37c7f8f2a0a4710be125896fb5b3e40
Frioux, Clémence
Schaub, Torsten
Schellhorn, Sebastian
Siegel, Anne
Wanko, Philipp
false
true
Clémence Frioux
Torsten H. Schaub
Sebastian Schellhorn
Anne Siegel
Philipp Wanko
eng
uncontrolled
answer set programming
eng
uncontrolled
metabolic network
eng
uncontrolled
gap-filling
eng
uncontrolled
linear programming
eng
uncontrolled
hybrid solving
eng
uncontrolled
bioinformatics
Informatik, Informationswissenschaft, allgemeine Werke
Institut für Informatik und Computational Science
Referiert
Import
Green Open-Access
5772
2011
2012
deu
doctoralthesis
1
2012-06-25
--
2012-03-28
Entwurf, Methoden und Werkzeuge für komplexe Bildverarbeitungssysteme auf Rekonfigurierbaren System-on-Chip-Architekturen
Design, methodologies and tools for complex image processing systems on reconfigurable system-on-chip-architectures
Bildverarbeitungsanwendungen stellen besondere Ansprüche an das ausführende Rechensystem. Einerseits ist eine hohe Rechenleistung erforderlich. Andererseits ist eine hohe Flexibilität von Vorteil, da die Entwicklung tendentiell ein experimenteller und interaktiver Prozess ist. Für neue Anwendungen tendieren Entwickler dazu, eine Rechenarchitektur zu wählen, die sie gut kennen, anstatt eine Architektur einzusetzen, die am besten zur Anwendung passt. Bildverarbeitungsalgorithmen sind inhärent parallel, doch herkömmliche bildverarbeitende eingebettete Systeme basieren meist auf sequentiell arbeitenden Prozessoren. Im Gegensatz zu dieser "Unstimmigkeit" können hocheffiziente Systeme aus einer gezielten Synergie aus Software- und Hardwarekomponenten aufgebaut werden. Die Konstruktion solcher System ist jedoch komplex und viele Lösungen, wie zum Beispiel grobgranulare Architekturen oder anwendungsspezifische Programmiersprachen, sind oft zu akademisch für einen Einsatz in der Wirtschaft. Die vorliegende Arbeit soll ein Beitrag dazu leisten, die Komplexität von Hardware-Software-Systemen zu reduzieren und damit die Entwicklung hochperformanter on-Chip-Systeme im Bereich Bildverarbeitung zu vereinfachen und wirtschaftlicher zu machen. Dabei wurde Wert darauf gelegt, den Aufwand für Einarbeitung, Entwicklung als auch Erweiterungen gering zu halten. Es wurde ein Entwurfsfluss konzipiert und umgesetzt, welcher es dem Softwareentwickler ermöglicht, Berechnungen durch Hardwarekomponenten zu beschleunigen und das zu Grunde liegende eingebettete System komplett zu prototypisieren. Hierbei werden komplexe Bildverarbeitungsanwendungen betrachtet, welche ein Betriebssystem erfordern, wie zum Beispiel verteilte Kamerasensornetzwerke. Die eingesetzte Software basiert auf Linux und der Bildverarbeitungsbibliothek OpenCV. Die Verteilung der Berechnungen auf Software- und Hardwarekomponenten und die daraus resultierende Ablaufplanung und Generierung der Rechenarchitektur erfolgt automatisch. Mittels einer auf der Antwortmengenprogrammierung basierten Entwurfsraumexploration ergeben sich Vorteile bei der Modellierung und Erweiterung. Die Systemsoftware wird mit OpenEmbedded/Bitbake synthetisiert und die erzeugten on-Chip-Architekturen auf FPGAs realisiert.
Image processing applications have special requirements to the executing computational system. On the one hand a high computational power is necessary. On the other hand a high flexibility is an advantage because the development tends to be an experimental and interactive process. For new applications the developer tend to choose a computational architecture which they know well instead of using that one which fits best to the application. Image processing algorithms are inherently parallel while common image processing systems are mostly based on sequentially operating processors. In contrast to this "mismatch", highly efficient systems can be setup of a directed synergy of software and hardware components. However, the construction of such systems is complex and lots of solutions, like gross-grained architectures or application specific programming languages, are often too academic for the usage in commerce. The present work should contribute to reduce the complexity of hardware-software-systems and thus increase the economy of and simplify the development of high-performance on-chip systems in the domain of image processing. In doing so, a value was set on keeping the effort low on making familiar to the topic, on development and also extensions. A design flow was developed and implemented which allows the software developer to accelerate calculations with hardware components and to prototype the whole embedded system. Here complex image processing systems, like distributed camera sensor networks, are examined which need an operating system. The used software is based upon Linux and the image processing library OpenCV. The distribution of the calculations to software and hardware components and the resulting scheduling and generation of architectures is done automatically. The design space exploration is based on answer set programming which involves advantages for modelling in terms of simplicity and extensions. The software is synthesized with the help of OpenEmbedded/Bitbake and the generated on-chip architectures are implemented on FPGAs.
urn:nbn:de:kobv:517-opus-59923
5992
ST 150, ST 330
Potsdam, Uni., Diss., 2012
Felix Mühlbauer
deu
uncontrolled
Bildverarbeitung
deu
uncontrolled
FPGA
deu
uncontrolled
on-chip
deu
uncontrolled
Entwurfsraumexploration
deu
uncontrolled
Hardware-Software-Co-Design
deu
uncontrolled
Antwortmengenprogrammierung
eng
uncontrolled
image processing
eng
uncontrolled
FPGA
eng
uncontrolled
on-chip
eng
uncontrolled
design space exploration
eng
uncontrolled
hardware-software-codesign
eng
uncontrolled
answer set programming
Datenverarbeitung; Informatik
LOGIC DESIGN
open_access
Institut für Informatik und Computational Science
Universität Potsdam
Universität Potsdam
https://publishup.uni-potsdam.de/files/5772/muehlbauer_diss.pdf
34884
2013
2013
eng
783
798
16
2
13
article
Cambridge Univ. Press
New York
1
--
--
--
Answer set programming as a modeling language for course timetabling
The course timetabling problem can be generally defined as the task of assigning a number of lectures to a limited set of timeslots and rooms, subject to a given set of hard and soft constraints. The modeling language for course timetabling is required to be expressive enough to specify a wide variety of soft constraints and objective functions. Furthermore, the resulting encoding is required to be extensible for capturing new constraints and for switching them between hard and soft, and to be flexible enough to deal with different formulations. In this paper, we propose to make effective use of ASP as a modeling language for course timetabling. We show that our ASP-based approach can naturally satisfy the above requirements, through an ASP encoding of the curriculum-based course timetabling problem proposed in the third track of the second international timetabling competition (ITC-2007). Our encoding is compact and human-readable, since each constraint is individually expressed by either one or two rules. Each hard constraint is expressed by using integrity constraints and aggregates of ASP. Each soft constraint S is expressed by rules in which the head is the form of penalty (S, V, C), and a violation V and its penalty cost C are detected and calculated respectively in the body. We carried out experiments on four different benchmark sets with five different formulations. We succeeded either in improving the bounds or producing the same bounds for many combinations of problem instances and formulations, compared with the previous best known bounds.
Theory and practice of logic programming
10.1017/S1471068413000495
1471-0684
wos:2011-2013
WOS:000324926400022
Banbara, M (reprint author), Kobe Univ, Nada Ku, 1-1 Rokko Dai, Kobe, Hyogo 6578501, Japan., banbara@kobe-u.ac.jp; soh@lion.kobe-u.ac.jp; tamura@kobe-u.ac.jp; inoue@nii.ac.jp; torsten@cs.uni-potsdam.de
JSPS KAKENHI [24300007]; DFG [SCHA 550/9-1]
<a href="http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-415469">Zweitveröffentlichung in der Schriftenreihe Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe ; 594</a>
Mutsunori Banbara
Takehide Soh
Naoyuki Tamura
Katsumi Inoue
Torsten H. Schaub
eng
uncontrolled
answer set programming
eng
uncontrolled
educational timetabling
eng
uncontrolled
course timetabling
Institut für Informatik und Computational Science
Referiert
Institut für Informatik
36986
2011
2011
eng
323
360
38
5-6
11
article
Cambridge Univ. Press
New York
1
--
--
--
Detecting inconsistencies in large biological networks with answer set programming
We introduce an approach to detecting inconsistencies in large biological networks by using answer set programming. To this end, we build upon a recently proposed notion of consistency between biochemical/genetic reactions and high-throughput profiles of cell activity. We then present an approach based on answer set programming to check the consistency of large-scale data sets. Moreover, we extend this methodology to provide explanations for inconsistencies by determining minimal representations of conflicts. In practice, this can be used to identify unreliable data or to indicate missing reactions.
Theory and practice of logic programming
10.1017/S1471068410000554
1471-0684
wos:2011-2013
24th International Conference on Logic Programming (ICLP)
DEC 09-13, 2008
WOS:000287977500008
Udine, ITALY
Gebser, M (reprint author), Univ Potsdam, Inst Informat, Potsdam, Germany., gebser@cs.uni-potsdam.de; torsten@cs.uni-potsdam.de; sthiele@cs.uni-potsdam.de; philippe.veber@googlemail.com
<a href="http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-412467">Zweitveröffentlichung in der Schriftenreihe Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe ; 561</a>
Martin Gebser
Torsten H. Schaub
Sven Thiele
Philippe Veber
eng
uncontrolled
answer set programming
eng
uncontrolled
bioinformatics
eng
uncontrolled
consistency
eng
uncontrolled
diagnosis
Institut für Informatik und Computational Science
Referiert
Institut für Informatik
39390
2015
2015
eng
117
142
26
15
article
Cambridge Univ. Press
New York
1
--
--
--
aspeed: Solver scheduling via answer set programming
Although Boolean Constraint Technology has made tremendous progress over the last decade, the efficacy of state-of-the-art solvers is known to vary considerably across different types of problem instances, and is known to depend strongly on algorithm parameters. This problem was addressed by means of a simple, yet effective approach using handmade, uniform, and unordered schedules of multiple solvers in ppfolio, which showed very impressive performance in the 2011 Satisfiability Testing (SAT) Competition. Inspired by this, we take advantage of the modeling and solving capacities of Answer Set Programming (ASP) to automatically determine more refined, that is, nonuniform and ordered solver schedules from the existing benchmarking data. We begin by formulating the determination of such schedules as multi-criteria optimization problems and provide corresponding ASP encodings. The resulting encodings are easily customizable for different settings, and the computation of optimum schedules can mostly be done in the blink of an eye, even when dealing with large runtime data sets stemming from many solvers on hundreds to thousands of instances. Also, the fact that our approach can be customized easily enabled us to swiftly adapt it to generate parallel schedules for multi-processor machines.
Theory and practice of logic programming
10.1017/S1471068414000015
1471-0684
1475-3081
wos:2015
WOS:000349668400005
Hoos, H (reprint author), Univ British Columbia, Dept Comp Sci, Vancouver, BC V5Z 1M9, Canada., hoos@cs.ubc.ca; kaminski@cs.uni-potsdam.de; manju@cs.uni-potsdam.de; torsten@cs.uni-potsdam.de
German Science Foundation (DFG) [SCHA 550/8-3]
<a href="http://nbn-resolving.de/urn:nbn:de:kobv:517-opus4-414743">Zweitveröffentlichung in der Schriftenreihe Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe ; 588</a>
Holger Hoos
Roland Kaminski
Marius Lindauer
Torsten H. Schaub
eng
uncontrolled
algorithm schedules
eng
uncontrolled
answer set programming
eng
uncontrolled
portfolio-based solving
Institut für Informatik und Computational Science
Referiert
Institut für Informatik
61011
2020
2015
eng
923
952
30
4
30
article
Oxford Univ. Press
Eynsham, Oxford
1
2020-06-01
2015-09-08
--
Declarative encodings of acyclicity properties
Many knowledge representation tasks involve trees or similar structures as abstract datatypes. However, devising compact and efficient declarative representations of such structural properties is non-obvious and can be challenging indeed. In this article, we take a number of acyclicity properties into consideration and investigate various logic-based approaches to encode them. We use answer set programming as the primary representation language but also consider mappings to related formalisms, such as propositional logic, difference logic and linear programming. We study the compactness of encodings and the resulting computational performance on benchmarks involving acyclic or tree structures.
Journal of logic and computation
10.1093/logcom/exv063
0955-792X
1465-363X
outputup:dataSource:WoS:2020
WOS:000544169100005
Gebser, M (corresponding author), Aalto Univ, Helsinki Inst Informat Technol HIIT, Dept Comp Sci, FI-00076 Aalto, Finland.; Gebser, M (corresponding author), Univ Potsdam, Potsdam, Germany., martin.gebser@aalto.fi; tomi.janhunen@aalto.fi; jussi.rintanen@aalto.fi
Finnish Centre of Excellence in Computational Inference Research (COIN); - Academy of Finland [251170]
Gebser, Martin
2023-10-05T10:44:28+00:00
sword
importub
filename=package.tar
238b9ea95c073f35457c9fa77ae86a72
1470328-2
1041082-X
false
true
Martin Gebser
Tomi Janhunen
Jussi Rintanen
eng
uncontrolled
acyclicity properties
eng
uncontrolled
logic-based modeling
eng
uncontrolled
answer set programming
eng
uncontrolled
satisfiability
Technik, Technologie
Institut für Informatik und Computational Science
Referiert
Import
Green Open-Access
6945
2014
eng
doctoralthesis
1
2014-09-05
--
2014-07-07
Reasoning on the response of logical signaling networks with answer set programming
Modellierung Logischer Signalnetzwerke mittels Antwortmengenprogrammierung
Deciphering the functioning of biological networks is one of the central tasks in systems biology. In particular, signal transduction networks are crucial for the understanding of the cellular response to external and internal perturbations. Importantly, in order to cope with the complexity of these networks, mathematical and computational modeling is required. We propose a computational modeling framework in order to achieve more robust discoveries in the context of logical signaling networks. More precisely, we focus on modeling the response of logical signaling networks by means of automated reasoning using Answer Set Programming (ASP). ASP provides a declarative language for modeling various knowledge representation and reasoning problems. Moreover, available ASP solvers provide several reasoning modes for assessing the multitude of answer sets. Therefore, leveraging its rich modeling language and its highly efficient solving capacities, we use ASP to address three challenging problems in the context of logical signaling networks: learning of (Boolean) logical networks, experimental design, and identification of intervention strategies. Overall, the contribution of this thesis is three-fold. Firstly, we introduce a mathematical framework for characterizing and reasoning on the response of logical signaling networks. Secondly, we contribute to a growing list of successful applications of ASP in systems biology. Thirdly, we present a software providing a complete pipeline for automated reasoning on the response of logical signaling networks.
Deciphering the functioning of biological networks is one of the central tasks in systems biology. In particular, signal transduction networks are crucial for the understanding of the cellular response to external and internal perturbations. Importantly, in order to cope with the complexity of these networks, mathematical and computational modeling is required. We propose a computational modeling framework in order to achieve more robust discoveries in the context of logical signaling networks. More precisely, we focus on modeling the response of logical signaling networks by means of automated reasoning using Answer Set Programming (ASP). ASP provides a declarative language for modeling various knowledge representation and reasoning problems. Moreover, available ASP solvers provide several reasoning modes for assessing the multitude of answer sets. Therefore, leveraging its rich modeling language and its highly efficient solving capacities, we use ASP to address three challenging problems in the context of logical signaling networks: learning of (Boolean) logical networks, experimental design, and identification of intervention strategies. Overall, the contribution of this thesis is three-fold. Firstly, we introduce a mathematical framework for characterizing and reasoning on the response of logical signaling networks. Secondly, we contribute to a growing list of successful applications of ASP in systems biology. Thirdly, we present a software providing a complete pipeline for automated reasoning on the response of logical signaling networks.
urn:nbn:de:kobv:517-opus-71890
7189
Potsdam, Univ., Diss., 2014
ST 304, SD 9200, WC 7700, WE 5320
Keine öffentliche Lizenz: Unter Urheberrechtsschutz
Santiago Videla
deu
uncontrolled
Systembiologie
deu
uncontrolled
logische Signalnetzwerke
deu
uncontrolled
Antwortmengenprogrammierung
eng
uncontrolled
systems biology
eng
uncontrolled
logical signaling networks
eng
uncontrolled
answer set programming
Datenverarbeitung; Informatik
open_access
Institut für Informatik und Computational Science
Extern
Universität Potsdam
Universität Potsdam
https://publishup.uni-potsdam.de/files/6945/videla_diss.pdf