Dokument-ID Dokumenttyp Verfasser/Autoren Herausgeber Haupttitel Abstract Auflage Verlagsort Verlag Erscheinungsjahr Seitenzahl Schriftenreihe Titel Schriftenreihe Bandzahl ISBN Quelle der Hochschulschrift Konferenzname Quelle:Titel Quelle:Jahrgang Quelle:Heftnummer Quelle:Erste Seite Quelle:Letzte Seite URN DOI Abteilungen OPUS4-41449 misc Fichte, Johannes Klaus; Truszczynski, Miroslaw; Woltran, Stefan Dual-normal logic programs Disjunctive Answer Set Programming is a powerful declarative programming paradigm with complexity beyond NP. Identifying classes of programs for which the consistency problem is in NP is of interest from the theoretical standpoint and can potentially lead to improvements in the design of answer set programming solvers. One of such classes consists of dual-normal programs, where the number of positive body atoms in proper rules is at most one. Unlike other classes of programs, dual-normal programs have received little attention so far. In this paper we study this class. We relate dual-normal programs to propositional theories and to normal programs by presenting several inter-translations. With the translation from dual-normal to normal programs at hand, we introduce the novel class of body-cycle free programs, which are in many respects dual to head-cycle free programs. We establish the expressive power of dual-normal programs in terms of SE- and UE-models, and compare them to normal programs. We also discuss the complexity of deciding whether dual-normal programs are strongly and uniformly equivalent. 2015 16 Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe 585 urn:nbn:de:kobv:517-opus4-414490 10.25932/publishup-41449 Mathematisch-Naturwissenschaftliche Fakultät OPUS4-41474 misc Hoos, Holger; Kaminski, Roland; Lindauer, Marius; Schaub, Torsten H. aspeed 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. 2015 26 Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe 588 urn:nbn:de:kobv:517-opus4-414743 10.25932/publishup-41474 Mathematisch-Naturwissenschaftliche Fakultät OPUS4-41546 misc Banbara, Mutsunori; Soh, Takehide; Tamura, Naoyuki; Inoue, Katsumi; Schaub, Torsten H. 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. 2013 16 Postprints der Universität Potsdam : Mathematisch Naturwissenschaftliche Reihe 594 783 798 urn:nbn:de:kobv:517-opus4-415469 10.25932/publishup-41546 Mathematisch-Naturwissenschaftliche Fakultät OPUS4-41243 misc Gebser, Martin; Kaminski, Roland; Schaub, Torsten H. Complex optimization in answer set programming Preference handling and optimization are indispensable means for addressing nontrivial applications in Answer Set Programming (ASP). However, their implementation becomes difficult whenever they bring about a significant increase in computational complexity. As a consequence, existing ASP systems do not offer complex optimization capacities, supporting, for instance, inclusion-based minimization or Pareto efficiency. Rather, such complex criteria are typically addressed by resorting to dedicated modeling techniques, like saturation. Unlike the ease of common ASP modeling, however, these techniques are rather involved and hardly usable by ASP laymen. We address this problem by developing a general implementation technique by means of meta-prpogramming, thus reusing existing ASP systems to capture various forms of qualitative preferences among answer sets. In this way, complex preferences and optimization capacities become readily available for ASP applications. 2011 19 Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe 554 urn:nbn:de:kobv:517-opus4-412436 10.25932/publishup-41243 Mathematisch-Naturwissenschaftliche Fakultät OPUS4-41246 misc Gebser, Martin; Schaub, Torsten H.; Thiele, Sven; Veber, Philippe 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. 2011 38 Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe 561 urn:nbn:de:kobv:517-opus4-412467 10.25932/publishup-41246 Mathematisch-Naturwissenschaftliche Fakultät OPUS4-42984 misc Dworschak, Steve; Grell, Susanne; Nikiforova, Victoria J.; Schaub, Torsten H.; Selbig, Joachim Modeling biological networks by action languages via answer set programming We describe an approach to modeling biological networks by action languages via answer set programming. To this end, we propose an action language for modeling biological networks, building on previous work by Baral et al. We introduce its syntax and semantics along with a translation into answer set programming, an efficient Boolean Constraint Programming Paradigm. Finally, we describe one of its applications, namely, the sulfur starvation response-pathway of the model plant Arabidopsis thaliana and sketch the functionality of our system and its usage. 2008 47 Postprints der Universität Potsdam : Mathematisch Naturwissenschaftliche Reihe 843 urn:nbn:de:kobv:517-opus4-429846 10.25932/publishup-42984 Mathematisch-Naturwissenschaftliche Fakultät