TY - JOUR A1 - Gerbser, Martin A1 - Lee, Joohyung A1 - Lierler, Yuliya T1 - Elementary sets for logic programs Y1 - 2006 SN - 978-1-57735-281-5 ER - TY - JOUR A1 - Konczak, Kathrin T1 - Weak order equivalence for Logic Programs with Prefernces Y1 - 2006 ER - TY - BOOK A1 - Hüttenrauch, Stefan A1 - Kylau, Uwe A1 - Grund, Martin A1 - Queck, Tobias A1 - Ploskonos, Anna A1 - Schreiter, Torben A1 - Breest, Martin A1 - Haubrock, Sören A1 - Bouche, Paul T1 - Fundamentals of Service-Oriented Engineering BT - Proceedings of the Fall 2006 Workshop of the HPI Research School on Service-Oriented Systems Engineering T3 - Technische Berichte des Hasso-Plattner-Instituts für Softwaresystemtechnik an der Universität Potsdam Y1 - 2006 SN - 3-939469-35-1 SN - 1613-5652 VL - 18 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - BOOK A1 - Kuropka, Dominik A1 - Meyer, Harald T1 - Survey on service composition T3 - Technische Berichte des Hasso-Plattner-Instituts für Softwaresystemtechnik an der Universität Potsda Y1 - 2005 SN - 3-937786-78-3 SN - 1613-5652 VL - 10 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Konczak, Kathrin A1 - Vogel, Ralf T1 - Abduction and Preferences in Linguistics Y1 - 2005 UR - http://www.cs.uni-potsdam.de/~konczak/Papers/konvog05a.pdf ER - TY - JOUR A1 - Calude, C. S. A1 - Jurgensen, Helmut T1 - Is complexity a source of incompleteness? N2 - In this paper we prove Chaitin's "heuristic principle," the theorems of a finitely-specified theory cannot be significantly more complex than the theory itself, for an appropriate measure of complexity. We show that the measure is invariant under the change of the Godel numbering. For this measure, the theorems of a finitely-specified, sound, consistent theory strong enough to formalize arithmetic which is arithmetically sound (like Zermelo-Fraenkel set theory with choice or Peano Arithmetic) have bounded complexity, hence every sentence of the theory which is significantly more complex than the theory is unprovable. Previous results showing that incompleteness is not accidental, but ubiquitous are here reinforced in probabilistic terms: the probability that a true sentence of length n is provable in the theory tends to zero when n tends to infinity, while the probability that a sentence of length n is true is strictly positive. (c) 2004 Elsevier Inc. All rights reserved Y1 - 2005 SN - 0196-8858 ER - TY - JOUR A1 - Bordihn, Henning T1 - On the number of components in cooperating distributed grammar systems N2 - It is proved that the number of components in context-free cooperating distributed (CD) grammar systems can be reduced to 3 when they are working in the so-called sf-mode of derivation, which is the cooperation protocol which has been considered first for CD grammar systems. In this derivation mode, a component continues the derivation until and unless there is a nonterminal in the sentential form which cannot be rewritten according to that component. Moreover, it is shown that CD grammar systems in sf-mode with only one component can generate only the context-free languages but they can generate non-context-free languages if two components are used. The sf-mode of derivation is compared with other well-known cooperation protocols with respect to the hierarchies induced by the number of components. (C) 2004 Elsevier B.V. All rights reserved Y1 - 2005 SN - 0304-3975 ER - TY - JOUR A1 - Beerenwinkel, Niko A1 - Sing, Tobias A1 - Lengauer, Thomas A1 - Rahnenfuhrer, Joerg A1 - Roomp, Kirsten A1 - Savenkov, Igor A1 - Fischer, Roman A1 - Hoffmann, Daniel A1 - Selbig, Joachim A1 - Korn, Klaus A1 - Walter, Hauke A1 - Berg, Thomas A1 - Braun, Patrick A1 - Faetkenheuer, Gerd A1 - Oette, Mark A1 - Rockstroh, Juergen A1 - Kupfer, Bernd A1 - Kaiser, Rolf A1 - Daeumer, Martin T1 - Computational methods for the design of effective therapies against drug resistant HIV strains N2 - The development of drug resistance is a major obstacle to successful treatment of HIV infection. The extraordinary replication dynamics of HIV facilitates its escape from selective pressure exerted by the human immune system and by combination drug therapy. We have developed several computational methods whose combined use can support the design of optimal antiretroviral therapies based on viral genomic data Y1 - 2005 ER - TY - JOUR A1 - Brzozowski, J. A. A1 - Jürgensen, Helmut T1 - Representation of semiautomata by canonical words and equivalences N2 - We study a novel representation of semiautomata, which is motivated by the method of trace-assertion specifications of software modules. Each state of the semiautomaton is represented by an arbitrary word leading to that state, the canonical word. The transitions of the semiautomaton give rise to a right congruence, the state-equivalence, on the set of input words of the semiautomaton: two words are state-equivalent if and only if they lead to the same state. We present a simple algorithm for finding a set of generators for state-equivalence. Directly from this set of generators, we construct a confluent prefix-rewriting system which permits us to transform any word to its canonical representative. In general, the rewriting system may allow infinite derivations. To address this issue, we impose the condition of prefix-continuity on the set of canonical words. A set is prefix-continuous if, whenever a word w and a prefix u of w axe in the set, then all the prefixes of w longer than u are also in the set. Prefix-continuous sets include prefix-free and prefix-closed sets as special cases. We prove that the rewriting system is Noetherian if and only if the set of canonical words is prefix-continuous. Furthermore, if the set of canonical words is prefix- continuous, then the set of rewriting rules is irredundant. We show that each prefix-continuous canonical set corresponds to a spanning forest of the semiautomaton Y1 - 2005 SN - 0129-0541 ER - TY - JOUR A1 - Bordihn, Henning A1 - Holzer, Markus A1 - Kutrib, Martin T1 - Unsolvability levels of operation problems for subclasses of context-free languages N2 - We investigate the operation problem for linear and deterministic context-free languages: Fix an operation on formal languages. Given linear (deterministic, respectively) context-free languages, is the application of this operation to the given languages still a linear (deterministic, respectively) context-free language? Besides the classical operations, for which the linear and deterministic context-free languages are not closed, we also consider the recently introduced root and power operation. We show non-semidecidability, to be more precise, we show completeness for the second level of the arithmetic hierarchy for all of the aforementioned operations, except for the power operation, if the underlying alphabet contains at least two letters. The result for the power opera, tion solves an open problem stated in Theoret. Comput. Sci. 314 (2004) 445-449 Y1 - 2005 SN - 0129-0541 ER -