TY - JOUR A1 - Rabenalt, Thomas A1 - Richter, Michael A1 - Pöhl, Frank A1 - Gössel, Michael T1 - Highly efficient test response compaction using a hierarchical x-masking technique JF - IEEE transactions on computer-aided design of integrated circuits and systems N2 - This paper presents a highly effective compactor architecture for processing test responses with a high percentage of x-values. The key component is a hierarchical configurable masking register, which allows the compactor to dynamically adapt to and provide excellent performance over a wide range of x-densities. A major contribution of this paper is a technique that enables the efficient loading of the x-masking data into the masking logic in a parallel fashion using the scan chains. A method for eliminating the requirement for dedicated mask control signals using automated test equipment timing flexibility is also presented. The proposed compactor is especially suited to multisite testing. Experiments with industrial designs show that the proposed compactor enables compaction ratios exceeding 200x. KW - Design for testability (DFT) KW - test response compaction KW - X-masking KW - X-values Y1 - 2012 U6 - https://doi.org/10.1109/TCAD.2011.2181847 SN - 0278-0070 VL - 31 IS - 6 SP - 950 EP - 957 PB - Inst. of Electr. and Electronics Engineers CY - Piscataway ER - TY - THES A1 - Brückner, Michael T1 - Prediction games : machine learning in the presence of an adversary T1 - Prädiktionsspiele : maschinelles Lernen in Anwesenheit eines Gegners N2 - In many applications one is faced with the problem of inferring some functional relation between input and output variables from given data. Consider, for instance, the task of email spam filtering where one seeks to find a model which automatically assigns new, previously unseen emails to class spam or non-spam. Building such a predictive model based on observed training inputs (e.g., emails) with corresponding outputs (e.g., spam labels) is a major goal of machine learning. Many learning methods assume that these training data are governed by the same distribution as the test data which the predictive model will be exposed to at application time. That assumption is violated when the test data are generated in response to the presence of a predictive model. This becomes apparent, for instance, in the above example of email spam filtering. Here, email service providers employ spam filters and spam senders engineer campaign templates such as to achieve a high rate of successful deliveries despite any filters. Most of the existing work casts such situations as learning robust models which are unsusceptible against small changes of the data generation process. The models are constructed under the worst-case assumption that these changes are performed such to produce the highest possible adverse effect on the performance of the predictive model. However, this approach is not capable to realistically model the true dependency between the model-building process and the process of generating future data. We therefore establish the concept of prediction games: We model the interaction between a learner, who builds the predictive model, and a data generator, who controls the process of data generation, as an one-shot game. The game-theoretic framework enables us to explicitly model the players' interests, their possible actions, their level of knowledge about each other, and the order at which they decide for an action. We model the players' interests as minimizing their own cost function which both depend on both players' actions. The learner's action is to choose the model parameters and the data generator's action is to perturbate the training data which reflects the modification of the data generation process with respect to the past data. We extensively study three instances of prediction games which differ regarding the order in which the players decide for their action. We first assume that both player choose their actions simultaneously, that is, without the knowledge of their opponent's decision. We identify conditions under which this Nash prediction game has a meaningful solution, that is, a unique Nash equilibrium, and derive algorithms that find the equilibrial prediction model. As a second case, we consider a data generator who is potentially fully informed about the move of the learner. This setting establishes a Stackelberg competition. We derive a relaxed optimization criterion to determine the solution of this game and show that this Stackelberg prediction game generalizes existing prediction models. Finally, we study the setting where the learner observes the data generator's action, that is, the (unlabeled) test data, before building the predictive model. As the test data and the training data may be governed by differing probability distributions, this scenario reduces to learning under covariate shift. We derive a new integrated as well as a two-stage method to account for this data set shift. In case studies on email spam filtering we empirically explore properties of all derived models as well as several existing baseline methods. We show that spam filters resulting from the Nash prediction game as well as the Stackelberg prediction game in the majority of cases outperform other existing baseline methods. N2 - Eine der Aufgabenstellungen des Maschinellen Lernens ist die Konstruktion von Vorhersagemodellen basierend auf gegebenen Trainingsdaten. Ein solches Modell beschreibt den Zusammenhang zwischen einem Eingabedatum, wie beispielsweise einer E-Mail, und einer Zielgröße; zum Beispiel, ob die E-Mail durch den Empfänger als erwünscht oder unerwünscht empfunden wird. Dabei ist entscheidend, dass ein gelerntes Vorhersagemodell auch die Zielgrößen zuvor unbeobachteter Testdaten korrekt vorhersagt. Die Mehrzahl existierender Lernverfahren wurde unter der Annahme entwickelt, dass Trainings- und Testdaten derselben Wahrscheinlichkeitsverteilung unterliegen. Insbesondere in Fällen in welchen zukünftige Daten von der Wahl des Vorhersagemodells abhängen, ist diese Annahme jedoch verletzt. Ein Beispiel hierfür ist das automatische Filtern von Spam-E-Mails durch E-Mail-Anbieter. Diese konstruieren Spam-Filter basierend auf zuvor empfangenen E-Mails. Die Spam-Sender verändern daraufhin den Inhalt und die Gestaltung der zukünftigen Spam-E-Mails mit dem Ziel, dass diese durch die Filter möglichst nicht erkannt werden. Bisherige Arbeiten zu diesem Thema beschränken sich auf das Lernen robuster Vorhersagemodelle welche unempfindlich gegenüber geringen Veränderungen des datengenerierenden Prozesses sind. Die Modelle werden dabei unter der Worst-Case-Annahme konstruiert, dass diese Veränderungen einen maximal negativen Effekt auf die Vorhersagequalität des Modells haben. Diese Modellierung beschreibt die tatsächliche Wechselwirkung zwischen der Modellbildung und der Generierung zukünftiger Daten nur ungenügend. Aus diesem Grund führen wir in dieser Arbeit das Konzept der Prädiktionsspiele ein. Die Modellbildung wird dabei als mathematisches Spiel zwischen einer lernenden und einer datengenerierenden Instanz beschrieben. Die spieltheoretische Modellierung ermöglicht es uns, die Interaktion der beiden Parteien exakt zu beschreiben. Dies umfasst die jeweils verfolgten Ziele, ihre Handlungsmöglichkeiten, ihr Wissen übereinander und die zeitliche Reihenfolge, in der sie agieren. Insbesondere die Reihenfolge der Spielzüge hat einen entscheidenden Einfluss auf die spieltheoretisch optimale Lösung. Wir betrachten zunächst den Fall gleichzeitig agierender Spieler, in welchem sowohl der Lerner als auch der Datengenerierer keine Kenntnis über die Aktion des jeweils anderen Spielers haben. Wir leiten hinreichende Bedingungen her, unter welchen dieses Spiel eine Lösung in Form eines eindeutigen Nash-Gleichgewichts besitzt. Im Anschluss diskutieren wir zwei verschiedene Verfahren zur effizienten Berechnung dieses Gleichgewichts. Als zweites betrachten wir den Fall eines Stackelberg-Duopols. In diesem Prädiktionsspiel wählt der Lerner zunächst das Vorhersagemodell, woraufhin der Datengenerierer in voller Kenntnis des Modells reagiert. Wir leiten ein relaxiertes Optimierungsproblem zur Bestimmung des Stackelberg-Gleichgewichts her und stellen ein mögliches Lösungsverfahren vor. Darüber hinaus diskutieren wir, inwieweit das Stackelberg-Modell bestehende robuste Lernverfahren verallgemeinert. Abschließend untersuchen wir einen Lerner, der auf die Aktion des Datengenerierers, d.h. der Wahl der Testdaten, reagiert. In diesem Fall sind die Testdaten dem Lerner zum Zeitpunkt der Modellbildung bekannt und können in den Lernprozess einfließen. Allerdings unterliegen die Trainings- und Testdaten nicht notwendigerweise der gleichen Verteilung. Wir leiten daher ein neues integriertes sowie ein zweistufiges Lernverfahren her, welche diese Verteilungsverschiebung bei der Modellbildung berücksichtigen. In mehreren Fallstudien zur Klassifikation von Spam-E-Mails untersuchen wir alle hergeleiteten, sowie existierende Verfahren empirisch. Wir zeigen, dass die hergeleiteten spieltheoretisch-motivierten Lernverfahren in Summe signifikant bessere Spam-Filter erzeugen als alle betrachteten Referenzverfahren. KW - Prädiktionsspiel KW - Adversarial Learning KW - Angewandte Spieltheorie KW - Maschinelles Lernen KW - Spam-Filter KW - Prediction Game KW - Adversarial Learning KW - Applied Game Theory KW - Machine Learning KW - Spam Filtering Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-60375 SN - 978-3-86956-203-2 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - THES A1 - Sawade, Christoph T1 - Active evaluation of predictive models T1 - Aktive Evaluierung von Vorhersagemodellen N2 - The field of machine learning studies algorithms that infer predictive models from data. Predictive models are applicable for many practical tasks such as spam filtering, face and handwritten digit recognition, and personalized product recommendation. In general, they are used to predict a target label for a given data instance. In order to make an informed decision about the deployment of a predictive model, it is crucial to know the model’s approximate performance. To evaluate performance, a set of labeled test instances is required that is drawn from the distribution the model will be exposed to at application time. In many practical scenarios, unlabeled test instances are readily available, but the process of labeling them can be a time- and cost-intensive task and may involve a human expert. This thesis addresses the problem of evaluating a given predictive model accurately with minimal labeling effort. We study an active model evaluation process that selects certain instances of the data according to an instrumental sampling distribution and queries their labels. We derive sampling distributions that minimize estimation error with respect to different performance measures such as error rate, mean squared error, and F-measures. An analysis of the distribution that governs the estimator leads to confidence intervals, which indicate how precise the error estimation is. Labeling costs may vary across different instances depending on certain characteristics of the data. For instance, documents differ in their length, comprehensibility, and technical requirements; these attributes affect the time a human labeler needs to judge relevance or to assign topics. To address this, the sampling distribution is extended to incorporate instance-specific costs. We empirically study conditions under which the active evaluation processes are more accurate than a standard estimate that draws equally many instances from the test distribution. We also address the problem of comparing the risks of two predictive models. The standard approach would be to draw instances according to the test distribution, label the selected instances, and apply statistical tests to identify significant differences. Drawing instances according to an instrumental distribution affects the power of a statistical test. We derive a sampling procedure that maximizes test power when used to select instances, and thereby minimizes the likelihood of choosing the inferior model. Furthermore, we investigate the task of comparing several alternative models; the objective of an evaluation could be to rank the models according to the risk that they incur or to identify the model with lowest risk. An experimental study shows that the active procedure leads to higher test power than the standard test in many application domains. Finally, we study the problem of evaluating the performance of ranking functions, which are used for example for web search. In practice, ranking performance is estimated by applying a given ranking model to a representative set of test queries and manually assessing the relevance of all retrieved items for each query. We apply the concepts of active evaluation and active comparison to ranking functions and derive optimal sampling distributions for the commonly used performance measures Discounted Cumulative Gain and Expected Reciprocal Rank. Experiments on web search engine data illustrate significant reductions in labeling costs. N2 - Maschinelles Lernen befasst sich mit Algorithmen zur Inferenz von Vorhersagemodelle aus komplexen Daten. Vorhersagemodelle sind Funktionen, die einer Eingabe – wie zum Beispiel dem Text einer E-Mail – ein anwendungsspezifisches Zielattribut – wie „Spam“ oder „Nicht-Spam“ – zuweisen. Sie finden Anwendung beim Filtern von Spam-Nachrichten, bei der Text- und Gesichtserkennung oder auch bei der personalisierten Empfehlung von Produkten. Um ein Modell in der Praxis einzusetzen, ist es notwendig, die Vorhersagequalität bezüglich der zukünftigen Anwendung zu schätzen. Für diese Evaluierung werden Instanzen des Eingaberaums benötigt, für die das zugehörige Zielattribut bekannt ist. Instanzen, wie E-Mails, Bilder oder das protokollierte Nutzerverhalten von Kunden, stehen häufig in großem Umfang zur Verfügung. Die Bestimmung der zugehörigen Zielattribute ist jedoch ein manueller Prozess, der kosten- und zeitaufwendig sein kann und mitunter spezielles Fachwissen erfordert. Ziel dieser Arbeit ist die genaue Schätzung der Vorhersagequalität eines gegebenen Modells mit einer minimalen Anzahl von Testinstanzen. Wir untersuchen aktive Evaluierungsprozesse, die mit Hilfe einer Wahrscheinlichkeitsverteilung Instanzen auswählen, für die das Zielattribut bestimmt wird. Die Vorhersagequalität kann anhand verschiedener Kriterien, wie der Fehlerrate, des mittleren quadratischen Verlusts oder des F-measures, bemessen werden. Wir leiten die Wahrscheinlichkeitsverteilungen her, die den Schätzfehler bezüglich eines gegebenen Maßes minimieren. Der verbleibende Schätzfehler lässt sich anhand von Konfidenzintervallen quantifizieren, die sich aus der Verteilung des Schätzers ergeben. In vielen Anwendungen bestimmen individuelle Eigenschaften der Instanzen die Kosten, die für die Bestimmung des Zielattributs anfallen. So unterscheiden sich Dokumente beispielsweise in der Textlänge und dem technischen Anspruch. Diese Eigenschaften beeinflussen die Zeit, die benötigt wird, mögliche Zielattribute wie das Thema oder die Relevanz zuzuweisen. Wir leiten unter Beachtung dieser instanzspezifischen Unterschiede die optimale Verteilung her. Die entwickelten Evaluierungsmethoden werden auf verschiedenen Datensätzen untersucht. Wir analysieren in diesem Zusammenhang Bedingungen, unter denen die aktive Evaluierung genauere Schätzungen liefert als der Standardansatz, bei dem Instanzen zufällig aus der Testverteilung gezogen werden. Eine verwandte Problemstellung ist der Vergleich von zwei Modellen. Um festzustellen, welches Modell in der Praxis eine höhere Vorhersagequalität aufweist, wird eine Menge von Testinstanzen ausgewählt und das zugehörige Zielattribut bestimmt. Ein anschließender statistischer Test erlaubt Aussagen über die Signifikanz der beobachteten Unterschiede. Die Teststärke hängt von der Verteilung ab, nach der die Instanzen ausgewählt wurden. Wir bestimmen die Verteilung, die die Teststärke maximiert und damit die Wahrscheinlichkeit minimiert, sich für das schlechtere Modell zu entscheiden. Des Weiteren geben wir eine Möglichkeit an, den entwickelten Ansatz für den Vergleich von mehreren Modellen zu verwenden. Wir zeigen empirisch, dass die aktive Evaluierungsmethode im Vergleich zur zufälligen Auswahl von Testinstanzen in vielen Anwendungen eine höhere Teststärke aufweist. Im letzten Teil der Arbeit werden das Konzept der aktiven Evaluierung und das des aktiven Modellvergleichs auf Rankingprobleme angewendet. Wir leiten die optimalen Verteilungen für das Schätzen der Qualitätsmaße Discounted Cumulative Gain und Expected Reciprocal Rank her. Eine empirische Studie zur Evaluierung von Suchmaschinen zeigt, dass die neu entwickelten Verfahren signifikant genauere Schätzungen der Rankingqualität liefern als die untersuchten Referenzverfahren. KW - Aktive Evaluierung KW - Vorhersagemodelle KW - Maschinelles Lernen KW - Fehlerschätzung KW - Statistische Tests KW - Active Evaluation KW - Predictive Models KW - Machine Learning KW - Error Estimation KW - Statistical Tests Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-65583 SN - 978-3-86956-255-1 PB - Universitätsverlag Potsdam CY - Potsdam ER - TY - JOUR A1 - Frank, Mario T1 - Axiom relevance decision engine : technical report N2 - This document presents an axiom selection technique for classic first order theorem proving based on the relevance of axioms for the proof of a conjecture. It is based on unifiability of predicates and does not need statistical information like symbol frequency. The scope of the technique is the reduction of the set of axioms and the increase of the amount of provable conjectures in a given time. Since the technique generates a subset of the axiom set, it can be used as a preprocessor for automated theorem proving. This technical report describes the conception, implementation and evaluation of ARDE. The selection method, which is based on a breadth-first graph search by unifiability of predicates, is a weakened form of the connection calculus and uses specialised variants or unifiability to speed up the selection. The implementation of the concept is evaluated with comparison to the results of the world championship of theorem provers of the year 2012 (CASC J6). It is shown that both the theorem prover leanCoP which uses the connection calculus and E which uses equality reasoning, can benefit from the selection approach. Also, the evaluation shows that the concept is applyable for theorem proving problems with thousands of formulae and that the selection is independent from the calculus used by the theorem prover. N2 - Dieser technische Report beschreibt die Konzeption, Implementierung und Evaluation eines Verfahrens zur Auswahl von logischen Formeln bezüglich derer Relevanz für den Beweis einer logischen Formel. Das Verfahren wird ausschließlich für die Prädikatenlogik erster Ordnung angewandt, wenngleich es auch für höherstufige Prädikatenlogiken geeignet ist. Das Verfahren nutzt eine unifikationsbasierte Breitensuche im Graphen wobei jeder Knoten im Graphen ein Prädikat und jede existierende Kante eine Unifizierbarkeitsrelation ist. Ziel des Verfahrens ist die Reduktion einer gegebenen Menge von Formeln auf eine für aktuelle Theorembeweiser handhabbare Größe. Daher ist das Verfahren als Präprozess-Schritt für das automatische Theorembeweisen geeignet. Zur Beschleunigung der Suche wird neben der Standard-Unifikation eine abgeschwächte Unifikation verwendet. Das System wurde während der Weltmeisterschaft der Theorembeweiser im Jahre 2014 (CASC J6) in Manchester zusammen mit dem Theorembeweiser leanCoP eingereicht und konnte leanCoP dabei unterstützen, Probleme zu lösen, die leanCoP alleine nicht handhaben kann. Die Tests mit leanCoP und dem Theorembeweiser E im Nachgang zu der Weltmeisterschaft zeigen, dass das Verfahren unabhängig von dem verwendeten Kalkül ist und bei beiden Theorembeweisern positive Auswirkungen auf die Beweisbarkeit von Problemen mit großen Formelmengen hat. KW - Relevanz KW - Graphensuche KW - Theorembeweisen KW - Preprocessing KW - Unifikation KW - relevance KW - graph-search KW - preprocessing KW - unification KW - theorem Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-72128 ER - TY - JOUR A1 - Paredes, E. G. A1 - Boo, M. A1 - Amor, M. A1 - Bruguera, J. D. A1 - Döllner, Jürgen Roland Friedrich T1 - Extended hybrid meshing algorithm for multiresolution terrain models JF - International journal of geographical information science N2 - Hybrid terrains are a convenient approach for the representation of digital terrain models, integrating heterogeneous data from different sources. In this article, we present a general, efficient scheme for achieving interactive level-of-detail rendering of hybrid terrain models, without the need for a costly preprocessing or resampling of the original data. The presented method works with hybrid digital terrains combining regular grid data and local high-resolution triangulated irregular networks. Since grid and triangulated irregular network data may belong to different datasets, a straightforward combination of both geometries would lead to meshes with holes and overlapping triangles. Our method generates a single multiresolution model integrating the different parts in a coherent way, by performing an adaptive tessellation of the region between their boundaries. Hence, our solution is one of the few existing approaches for integrating different multiresolution algorithms within the same terrain model, achieving a simple interactive rendering of complex hybrid terrains. KW - 3D modeling KW - 3D visualization KW - geovisualization KW - triangulated irregular networks Y1 - 2012 U6 - https://doi.org/10.1080/13658816.2011.615317 SN - 1365-8816 VL - 26 IS - 5 SP - 771 EP - 793 PB - Routledge, Taylor & Francis Group CY - Abingdon ER - TY - GEN A1 - Ebert, Birgitta E. A1 - Lamprecht, Anna-Lena A1 - Steffen, Bernhard A1 - Blank, Lars M. T1 - Flux-P BT - automating metabolic flux analysis T2 - Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe N2 - Quantitative knowledge of intracellular fluxes in metabolic networks is invaluable for inferring metabolic system behavior and the design principles of biological systems. However, intracellular reaction rates can not often be calculated directly but have to be estimated; for instance, via 13C-based metabolic flux analysis, a model-based interpretation of stable carbon isotope patterns in intermediates of metabolism. Existing software such as FiatFlux, OpenFLUX or 13CFLUX supports experts in this complex analysis, but requires several steps that have to be carried out manually, hence restricting the use of this software for data interpretation to a rather small number of experiments. In this paper, we present Flux-P as an approach to automate and standardize 13C-based metabolic flux analysis, using the Bio-jETI workflow framework. Exemplarily based on the FiatFlux software, it demonstrates how services can be created that carry out the different analysis steps autonomously and how these can subsequently be assembled into software workflows that perform automated, high-throughput intracellular flux analysis of high quality and reproducibility. Besides significant acceleration and standardization of the data analysis, the agile workflow-based realization supports flexible changes of the analysis workflows on the user level, making it easy to perform custom analyses. T3 - Zweitveröffentlichungen der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe - 1054 KW - 13C metabolic flux analysis KW - MFA KW - high-throughput analysis KW - scientific workflows KW - workflow management KW - Bio-jETI Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-476696 SN - 1866-8372 IS - 1054 SP - 872 EP - 890 ER - TY - THES A1 - Bog, Anja T1 - Benchmarking composite transaction and analytical processing systems : the creation of a mixed workload benchmark and its application in evaluating the impact of database schema optimizations in mixed workload scenarios Y1 - 2012 CY - Potsdam ER - TY - THES A1 - Panchenko, Oleksandr T1 - In-Memory database support for source code querying and analytics Y1 - 2012 CY - Potsdam ER - TY - THES A1 - Grund, Martin T1 - Hyrise : a main memory hybrid database storage engine Y1 - 2012 CY - Potsdam ER - TY - THES A1 - Appeltauer, Malte T1 - Extending Context-oriented Programming to New Application Domains: Run-time Adaptation Support for Java Y1 - 2012 CY - Potsdam ER - TY - THES A1 - Broß, Justus F. M. T1 - Understanding and leveraging the social physics of the blogosphere Y1 - 2012 CY - Potsdam ER - TY - THES A1 - Zarezadeh, Aliakbar T1 - Distributed smart cameras : architecture and communication protocols Y1 - 2012 CY - Potsdam ER - TY - THES A1 - Müller, Jürgen J. T1 - A real-time in-memory discovery service Y1 - 2012 CY - Potsdam ER - TY - JOUR A1 - Luebbe, Alexander A1 - Weske, Mathias T1 - Determining the effect of tangible business process modeling Y1 - 2012 ER - TY - JOUR A1 - Steinert, Bastian A1 - Hirschfeld, Robert T1 - Applying design knowledge to programming Y1 - 2012 ER - TY - JOUR A1 - Gabrysiak, Gregor A1 - Giese, Holger A1 - Seibel, Andreas T1 - Towards next-generation design thinking II : virtual muti-user software prototypes Y1 - 2012 ER - TY - JOUR A1 - Kowark, Thomas A1 - Uflacker, Matthias A1 - Zeier, Alexander T1 - Towards a shared platform for virtual collaboration monotoring in design research Y1 - 2012 ER - TY - BOOK A1 - Lerch, Alexander T1 - An introduction to audio content analysis : applications in signal processing and music informatics Y1 - 2012 SN - 978-1-118-26682-3 U6 - https://doi.org/10.1002/9781118393550 PB - Wiley CY - Hoboken, N.J ER - TY - THES A1 - Scherfenberg, Ivonne T1 - A logic-based Framwork to enable Attribute Assurance for Digital Identities in Service-oriented Architectures and the Web Y1 - 2012 CY - Potsdam ER - TY - JOUR A1 - Bordihn, Henning A1 - Kutrib, Martin A1 - Malcher, Andreas T1 - On the computational capacity of parallel communicating finite automata JF - International journal of foundations of computer science N2 - Systems of parallel finite automata communicating by states are investigated. We consider deterministic and nondeterministic devices and distinguish four working modes. It is known that systems in the most general mode are as powerful as one-way multi-head finite automata. Here we solve some open problems on the computational capacity of systems working in the remaining modes. In particular, it is shown that deterministic returning and non-returning devices are equivalent, and that there are languages which are accepted by deterministic returning and centralized systems but cannot be accepted by deterministic non-returning centralized systems. Furthermore, we show that nondeterministic systems are strictly more powerful than their deterministic variants in all the four working modes. Finally, incomparability with the classes of (deterministic) (linear) context-free languages as well as the Church-Rosser languages is derived. KW - Automata systems KW - cooperating systems KW - formal languages KW - theory of computation Y1 - 2012 U6 - https://doi.org/10.1142/S0129054112500062 SN - 0129-0541 VL - 23 IS - 3 SP - 713 EP - 732 PB - World Scientific CY - Singapore ER - TY - JOUR A1 - Gebser, Martin A1 - Kaufmann, Benjamin A1 - Schaub, Torsten H. T1 - Conflict-driven answer set solving: From theory to practice JF - Artificial intelligence N2 - We introduce an approach to computing answer sets of logic programs, based on concepts successfully applied in Satisfiability (SAT) checking. The idea is to view inferences in Answer Set Programming (ASP) as unit propagation on nogoods. This provides us with a uniform constraint-based framework capturing diverse inferences encountered in ASP solving. Moreover, our approach allows us to apply advanced solving techniques from the area of SAT. As a result, we present the first full-fledged algorithmic framework for native conflict-driven ASP solving. Our approach is implemented in the ASP solver clasp that has demonstrated its competitiveness and versatility by winning first places at various solver contests. KW - Answer set programming KW - Logic programming KW - Nonmonotonic reasoning Y1 - 2012 U6 - https://doi.org/10.1016/j.artint.2012.04.001 SN - 0004-3702 VL - 187 IS - 8 SP - 52 EP - 89 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Ostrowski, Max A1 - Schaub, Torsten H. T1 - ASP modulo CSP The clingcon system JF - Theory and practice of logic programming N2 - We present the hybrid ASP solver clingcon, combining the simple modeling language and the high performance Boolean solving capacities of Answer Set Programming (ASP) with techniques for using non-Boolean constraints from the area of Constraint Programming (CP). The new clingcon system features an extended syntax supporting global constraints and optimize statements for constraint variables. The major technical innovation improves the interaction between ASP and CP solver through elaborated learning techniques based on irreducible inconsistent sets. A broad empirical evaluation shows that these techniques yield a performance improvement of an order of magnitude. Y1 - 2012 U6 - https://doi.org/10.1017/S1471068412000142 SN - 1471-0684 VL - 12 SP - 485 EP - 503 PB - Cambridge Univ. Press CY - New York ER - TY - JOUR A1 - Gebser, Martin A1 - Kaufmann, Benjamin A1 - Schaub, Torsten H. T1 - Multi-threaded ASP solving with clasp JF - Theory and practice of logic programming N2 - We present the new multi-threaded version of the state-of-the-art answer set solver clasp. We detail its component and communication architecture and illustrate how they support the principal functionalities of clasp. Also, we provide some insights into the data representation used for different constraint types handled by clasp. All this is accompanied by an extensive experimental analysis of the major features related to multi-threading in clasp. Y1 - 2012 U6 - https://doi.org/10.1017/S1471068412000166 SN - 1471-0684 VL - 12 IS - 8 SP - 525 EP - 545 PB - Cambridge Univ. Press CY - New York ER - TY - JOUR A1 - Fabian, Benjamin A1 - Kunz, Steffen A1 - Konnegen, Marcel A1 - Müller, Sebastian A1 - Günther, Oliver T1 - Access control for semantic data federations in industrial product-lifecycle management JF - Computers in industry : an international, application oriented research journal N2 - Information integration across company borders becomes increasingly important for the success of product lifecycle management in industry and complex supply chains. Semantic technologies are about to play a crucial role in this integrative process. However, cross-company data exchange requires mechanisms to enable fine-grained access control definition and enforcement, preventing unauthorized leakage of confidential data across company borders. Currently available semantic repositories are not sufficiently equipped to satisfy this important requirement. This paper presents an infrastructure for controlled sharing of semantic data between cooperating business partners. First, we motivate the need for access control in semantic data federations by a case study in the industrial service sector. Furthermore, we present an architecture for controlling access to semantic repositories that is based on our newly developed SemForce security service. Finally, we show the practical feasibility of this architecture by an implementation and several performance experiments. KW - Access control KW - Data federation KW - Information integration KW - Product lifecycle management KW - Semantic data Y1 - 2012 U6 - https://doi.org/10.1016/j.compind.2012.08.015 SN - 0166-3615 VL - 63 IS - 9 SP - 930 EP - 940 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Brückner, Michael A1 - Kanzow, Christian A1 - Scheffer, Tobias T1 - Static prediction games for adversarial learning problems JF - Journal of machine learning research N2 - The standard assumption of identically distributed training and test data is violated when the test data are generated in response to the presence of a predictive model. This becomes apparent, for example, in the context of email spam filtering. Here, email service providers employ spam filters, and spam senders engineer campaign templates to achieve a high rate of successful deliveries despite the filters. We model the interaction between the learner and the data generator as a static game in which the cost functions of the learner and the data generator are not necessarily antagonistic. We identify conditions under which this prediction game has a unique Nash equilibrium and derive algorithms that find the equilibrial prediction model. We derive two instances, the Nash logistic regression and the Nash support vector machine, and empirically explore their properties in a case study on email spam filtering. KW - static prediction games KW - adversarial classification KW - Nash equilibrium Y1 - 2012 SN - 1532-4435 VL - 13 SP - 2617 EP - 2654 PB - Microtome Publishing CY - Cambridge, Mass. ER - TY - JOUR A1 - Srinivasan, K. A1 - Senthilkumar, D. V. A1 - Mohamed, I. Raja A1 - Murali, K. A1 - Lakshmanan, M. A1 - Kurths, Jürgen T1 - Anticipating, complete and lag synchronizations in RC phase-shift network based coupled Chua's circuits without delay JF - Chaos : an interdisciplinary journal of nonlinear science N2 - We construct a new RC phase shift network based Chua's circuit, which exhibits a period-doubling bifurcation route to chaos. Using coupled versions of such a phase-shift network based Chua's oscillators, we describe a new method for achieving complete synchronization (CS), approximate lag synchronization (LS), and approximate anticipating synchronization (AS) without delay or parameter mismatch. Employing the Pecora and Carroll approach, chaos synchronization is achieved in coupled chaotic oscillators, where the drive system variables control the response system. As a result, AS or LS or CS is demonstrated without using a variable delay line both experimentally and numerically. Y1 - 2012 U6 - https://doi.org/10.1063/1.4711375 SN - 1054-1500 VL - 22 IS - 2 PB - American Institute of Physics CY - Melville ER - TY - THES A1 - Mahr, Philipp T1 - Resource efficient communication in network-based reconfigurable on-chip systems T1 - Ressourcen-effiziente Kommunikation in netzwerk-basierten, rekonfigurierbaren Systemen auf einem Chip N2 - The constantly growing capacity of reconfigurable devices allows simultaneous execution of complex applications on those devices. The mere diversity of applications deems it impossible to design an interconnection network matching the requirements of every possible application perfectly, leading to suboptimal performance in many cases. However, the architecture of the interconnection network is not the only aspect affecting performance of communication. The resource manager places applications on the device and therefore influences latency between communicating partners and overall network load. Communication protocols affect performance by introducing data and processing overhead putting higher load on the network and increasing resource demand. Approaching communication holistically not only considers the architecture of the interconnect, but communication-aware resource management, communication protocols and resource usage just as well. Incorporation of different parts of a reconfigurable system during design- and runtime and optimizing them with respect to communication demand results in more resource efficient communication. Extensive evaluation shows enhanced performance and flexibility, if communication on reconfigurable devices is regarded in a holistic fashion. N2 - Die Leistungsfähigkeit rekonfigurierbarer Rechensysteme steigt kontinuierlich und ermöglicht damit die parallele Ausführung von immer mehr und immer größeren Anwendungen. Die Vielfalt an Anwendungen macht es allerdings unmöglich ein optimales Kommunikationsnetzwerk zu entwickeln, welches die Anforderung jeder denkbaren Anwendung berücksichtigt. Die Performanz des rekonfigurierbaren Rechensystems sinkt. Das Kommunikationsnetzwerk ist jedoch nicht der einzige Teil des Systems, der Einfluss auf die Kommunikation- sperformanz nimmt. Die Ressourcenverwaltung des Systems beeinflusst durch die Platzierung der Anwendungen die Latenz zwischen Kommunikationspartnern und die Kommunikationslast im Netzwerk. Kommunikationsprotokolle beeinträchtigen die Performanz der Kommunikation durch Daten und Rechen- overhead, die ebenso zu erhöhter Netzwerklast sowie Ressourcenanforderungen führen. In einem ganzheitlichen Kommunikationsansatz wird nicht nur das Kommunikationsnetzwerk berücksichtigt, sondern außerdem Ressourcenverwaltung, Kommunikationsprotokolle und die anderweitige Verwendung vorhandener, temporär ungenutzter Kommunikationsressourcen. Durch Einbeziehung dieser Aspekte während Entwurfs- und Laufzeit und durch Optimierung unter Berücksichtigung der Kommunikationsanforderungen, wird eine ressourceneneffizien tere Kommunikation erreicht. Ausführliche Evaluationen zeigen, dass eine ganzheitliche Betrachtung von Kommunikationsfaktoren, Verbesserungen von Performanz und Flexibilität erzielt. KW - Rekonfiguration KW - Platzierung KW - Netzwerke KW - Kommunikation KW - reconfiguration KW - networks-on-chip KW - communication KW - placement KW - scheduling Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-59914 ER - TY - JOUR A1 - Jobst, Birgit A1 - Köppen, Eva A1 - Lindberg, Tilmann A1 - Moritz, Josephine A1 - Rhinow, Holger A1 - Meinel, Christoph T1 - The faith-factor in design thinking : creative confidence through education at the design thinking schools Potsdam and Standford? Y1 - 2012 SN - 978-3-642-31990-7 ER - TY - JOUR A1 - Noweski, Christine A1 - Scheer, Andrea A1 - Büttner, Nadja A1 - von Thienen, Julia A1 - Erdmann, Johannes A1 - Meinel, Christoph T1 - Towards a paradigm shift in education practice : developing twenty-first century skills with design thinking Y1 - 2012 SN - 978-3-642-31990-7 ER - TY - JOUR A1 - von Thienen, Julia A1 - Noweski, Christine A1 - Meinel, Christoph A1 - Lang, Sabine A1 - Nicolai, Claudia A1 - Bartz, Andreas T1 - What can design thinking learn from behavior group theraphy? Y1 - 2012 SN - 978-3-642-31990-7 ER - TY - JOUR A1 - Gumienny, Raja A1 - Gericke, Lutz A1 - Wenzel, Matthias A1 - Meinel, Christoph T1 - Tele-board in use : applying aq digital whiteboard system in different situations and setups Y1 - 2012 SN - 978-3-642-31990-7 ER - TY - JOUR A1 - Von Thienen, Julia A1 - Noweski, Christine A1 - Rauth, Ingo A1 - Meinel, Christoph A1 - Lange, Sabine T1 - If you want to know who are, tell me where you are : the importance of places Y1 - 2012 ER - TY - JOUR A1 - Meinel, Christoph A1 - Leifer, Larry T1 - Design thinking research Y1 - 2012 SN - 978-3-642-31990-7 ER - TY - JOUR A1 - Lindberg, Tilmann A1 - Köppen, Eva A1 - Rauth, Ingo A1 - Meinel, Christoph T1 - On the perection, adoption and Implementation of design thinking in the IT industry Y1 - 2012 ER - TY - JOUR A1 - Gericke, Lutz A1 - Gumienny, Raja A1 - Meinel, Christoph T1 - Tele-board : folow the traces of your design process history Y1 - 2012 ER - TY - JOUR A1 - Meinel, Christoph A1 - Leifer, Larry T1 - Design thinking research Y1 - 2012 ER - TY - BOOK ED - Plattner, Hasso ED - Meinel, Christoph ED - Leifer, Larry T1 - Dsign thinking research : studying co-creation in practice Y1 - 2012 SN - 978-3-642-21642-8 U6 - https://doi.org/10.1007/978-3-642-21643-5 PB - Springer Berlin Heidelberg CY - Berlin, Heidelberg ER - TY - THES A1 - Glander, Tassilo T1 - Multi-scale representations of virtual 3D city models T1 - Maßstabsabhängige Repräsentationen virtueller 3D-Stadtmodelle N2 - Virtual 3D city and landscape models are the main subject investigated in this thesis. They digitally represent urban space and have many applications in different domains, e.g., simulation, cadastral management, and city planning. Visualization is an elementary component of these applications. Photo-realistic visualization with an increasingly high degree of detail leads to fundamental problems for comprehensible visualization. A large number of highly detailed and textured objects within a virtual 3D city model may create visual noise and overload the users with information. Objects are subject to perspective foreshortening and may be occluded or not displayed in a meaningful way, as they are too small. In this thesis we present abstraction techniques that automatically process virtual 3D city and landscape models to derive abstracted representations. These have a reduced degree of detail, while essential characteristics are preserved. After introducing definitions for model, scale, and multi-scale representations, we discuss the fundamentals of map generalization as well as techniques for 3D generalization. The first presented technique is a cell-based generalization of virtual 3D city models. It creates abstract representations that have a highly reduced level of detail while maintaining essential structures, e.g., the infrastructure network, landmark buildings, and free spaces. The technique automatically partitions the input virtual 3D city model into cells based on the infrastructure network. The single building models contained in each cell are aggregated to abstracted cell blocks. Using weighted infrastructure elements, cell blocks can be computed on different hierarchical levels, storing the hierarchy relation between the cell blocks. Furthermore, we identify initial landmark buildings within a cell by comparing the properties of individual buildings with the aggregated properties of the cell. For each block, the identified landmark building models are subtracted using Boolean operations and integrated in a photo-realistic way. Finally, for the interactive 3D visualization we discuss the creation of the virtual 3D geometry and their appearance styling through colors, labeling, and transparency. We demonstrate the technique with example data sets. Additionally, we discuss applications of generalization lenses and transitions between abstract representations. The second technique is a real-time-rendering technique for geometric enhancement of landmark objects within a virtual 3D city model. Depending on the virtual camera distance, landmark objects are scaled to ensure their visibility within a specific distance interval while deforming their environment. First, in a preprocessing step a landmark hierarchy is computed, this is then used to derive distance intervals for the interactive rendering. At runtime, using the virtual camera distance, a scaling factor is computed and applied to each landmark. The scaling factor is interpolated smoothly at the interval boundaries using cubic Bézier splines. Non-landmark geometry that is near landmark objects is deformed with respect to a limited number of landmarks. We demonstrate the technique by applying it to a highly detailed virtual 3D city model and a generalized 3D city model. In addition we discuss an adaptation of the technique for non-linear projections and mobile devices. The third technique is a real-time rendering technique to create abstract 3D isocontour visualization of virtual 3D terrain models. The virtual 3D terrain model is visualized as a layered or stepped relief. The technique works without preprocessing and, as it is implemented using programmable graphics hardware, can be integrated with minimal changes into common terrain rendering techniques. Consequently, the computation is done in the rendering pipeline for each vertex, primitive, i.e., triangle, and fragment. For each vertex, the height is quantized to the nearest isovalue. For each triangle, the vertex configuration with respect to their isovalues is determined first. Using the configuration, the triangle is then subdivided. The subdivision forms a partial step geometry aligned with the triangle. For each fragment, the surface appearance is determined, e.g., depending on the surface texture, shading, and height-color-mapping. Flexible usage of the technique is demonstrated with applications from focus+context visualization, out-of-core terrain rendering, and information visualization. This thesis presents components for the creation of abstract representations of virtual 3D city and landscape models. Re-using visual language from cartography, the techniques enable users to build on their experience with maps when interpreting these representations. Simultaneously, characteristics of 3D geovirtual environments are taken into account by addressing and discussing, e.g., continuous scale, interaction, and perspective. N2 - Gegenstand der Arbeit sind virtuelle 3D-Stadt- und Landschaftsmodelle, die den städtischen Raum in digitalen Repräsentationen abbilden. Sie werden in vielfältigen Anwendungen und zu unterschiedlichen Zwecken eingesetzt. Dabei ist die Visualisierung ein elementarer Bestandteil dieser Anwendungen. Durch realitätsnahe Darstellung und hohen Detailgrad entstehen jedoch zunehmend fundamentale Probleme für eine verständliche Visualisierung. So führt beispielsweise die hohe Anzahl von detailliert ausmodellierten und texturierten Objekten eines virtuellen 3D-Stadtmodells zu Informationsüberflutung beim Betrachter. In dieser Arbeit werden Abstraktionsverfahren vorgestellt, die diese Probleme behandeln. Ziel der Verfahren ist die automatische Transformation virtueller 3D-Stadt- und Landschaftsmodelle in abstrakte Repräsentationen, die bei reduziertem Detailgrad wichtige Charakteristika erhalten. Nach der Einführung von Grundbegriffen zu Modell, Maßstab und Mehrfachrepräsentationen werden theoretische Grundlagen zur Generalisierung von Karten sowie Verfahren zur 3D-Generalisierung betrachtet. Das erste vorgestellte Verfahren beschreibt die zellbasierte Generalisierung von virtuellen 3DStadtmodellen. Es erzeugt abstrakte Repräsentationen, die drastisch im Detailgrad reduziert sind, erhält dabei jedoch die wichtigsten Strukturen, z.B. das Infrastrukturnetz, Landmarkengebäude und Freiflächen. Dazu wird in einem vollautomatischen Verfahren das Eingabestadtmodell mithilfe des Infrastrukturnetzes in Zellen zerlegt. Pro Zelle wird abstrakte Gebäudegeometrie erzeugt, indem die enthaltenen Einzelgebäude mit ihren Eigenschaften aggregiert werden. Durch Berücksichtigung gewichteter Elemente des Infrastrukturnetzes können Zellblöcke auf verschiedenen Hierarchieebenen berechnet werden. Weiterhin werden Landmarken gesondert berücksichtigt: Anhand statistischer Abweichungen der Eigenschaften der Einzelgebäudes von den aggregierten Eigenschaften der Zelle werden Gebäude gegebenenfalls als initiale Landmarken identifiziert. Schließlich werden die Landmarkengebäude aus den generalisierten Blöcken mit Booleschen Operationen ausgeschnitten und realitätsnah dargestellt. Die Ergebnisse des Verfahrens lassen sich in interaktiver 3D-Darstellung einsetzen. Das Verfahren wird beispielhaft an verschiedenen Datensätzen demonstriert und bezüglich der Erweiterbarkeit diskutiert. Das zweite vorgestellte Verfahren ist ein Echtzeit-Rendering-Verfahren für geometrische Hervorhebung von Landmarken innerhalb eines virtuellen 3D-Stadtmodells: Landmarkenmodelle werden abhängig von der virtuellen Kameradistanz vergrößert, so dass sie innerhalb eines spezifischen Entfernungsintervalls sichtbar bleiben; dabei wird ihre Umgebung deformiert. In einem Vorverarbeitungsschritt wird eine Landmarkenhierarchie bestimmt, aus der die Entfernungsintervalle für die interaktive Darstellung abgeleitet werden. Zur Laufzeit wird anhand der virtuellen Kameraentfernung je Landmarke ein dynamischer Skalierungsfaktor bestimmt, der das Landmarkenmodell auf eine sichtbare Größe skaliert. Dabei wird der Skalierungsfaktor an den Intervallgrenzen durch kubisch interpoliert. Für Nicht-Landmarkengeometrie in der Umgebung wird die Deformation bezüglich einer begrenzten Menge von Landmarken berechnet. Die Eignung des Verfahrens wird beispielhaft anhand verschiedener Datensätze demonstriert und bezüglich der Erweiterbarkeit diskutiert. Das dritte vorgestellte Verfahren ist ein Echtzeit-Rendering-Verfahren, das eine abstrakte 3D-Isokonturen-Darstellung von virtuellen 3D-Geländemodellen erzeugt. Für das Geländemodell wird eine Stufenreliefdarstellung für eine Menge von nutzergewählten Höhenwerten erzeugt. Das Verfahren arbeitet ohne Vorverarbeitung auf Basis programmierbarer Grafikkarten-Hardware. Entsprechend erfolgt die Verarbeitung in der Prozesskette pro Geometrieknoten, pro Dreieck, und pro Bildfragment. Pro Geometrieknoten wird zunächst die Höhe auf den nächstliegenden Isowert quantisiert. Pro Dreieck wird dann die Konfiguration bezüglich der Isowerte der drei Geometrieknoten bestimmt. Anhand der Konfiguration wird eine geometrische Unterteilung vorgenommen, so dass ein Stufenausschnitt entsteht, der dem aktuellen Dreieck entspricht. Pro Bildfragment wird schließlich die finale Erscheinung definiert, z.B. anhand von Oberflächentextur, durch Schattierung und Höheneinfärbung. Die vielfältigen Einsatzmöglichkeiten werden mit verschiedenen Anwendungen demonstriert. Die Arbeit stellt Bausteine für die Erzeugung abstrakter Darstellungen von virtuellen 3D-Stadt und Landschaftsmodellen vor. Durch die Orientierung an kartographischer Bildsprache können die Nutzer auf bestehende Erfahrungen bei der Interpretation zurückgreifen. Dabei werden die charakteristischen Eigenschaften 3D geovirtueller Umgebungen berücksichtigt, indem z.B. kontinuierlicher Maßstab, Interaktion und Perspektive behandelt und diskutiert werden. KW - Generalisierung KW - virtuelle 3D-Stadtmodelle KW - Gebäudemodelle KW - Landmarken KW - Geländemodelle KW - generalization KW - virtual 3D city models KW - building models KW - landmarks KW - terrain models Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-64117 ER - TY - THES A1 - Seibel, Andreas T1 - Traceability and model management with executable and dynamic hierarchical megamodels T1 - Traceability und Modell Management mit ausführbaren und dynamischen Megamodellen N2 - Nowadays, model-driven engineering (MDE) promises to ease software development by decreasing the inherent complexity of classical software development. In order to deliver on this promise, MDE increases the level of abstraction and automation, through a consideration of domain-specific models (DSMs) and model operations (e.g. model transformations or code generations). DSMs conform to domain-specific modeling languages (DSMLs), which increase the level of abstraction, and model operations are first-class entities of software development because they increase the level of automation. Nevertheless, MDE has to deal with at least two new dimensions of complexity, which are basically caused by the increased linguistic and technological heterogeneity. The first dimension of complexity is setting up an MDE environment, an activity comprised of the implementation or selection of DSMLs and model operations. Setting up an MDE environment is both time-consuming and error-prone because of the implementation or adaptation of model operations. The second dimension of complexity is concerned with applying MDE for actual software development. Applying MDE is challenging because a collection of DSMs, which conform to potentially heterogeneous DSMLs, are required to completely specify a complex software system. A single DSML can only be used to describe a specific aspect of a software system at a certain level of abstraction and from a certain perspective. Additionally, DSMs are usually not independent but instead have inherent interdependencies, reflecting (partial) similar aspects of a software system at different levels of abstraction or from different perspectives. A subset of these dependencies are applications of various model operations, which are necessary to keep the degree of automation high. This becomes even worse when addressing the first dimension of complexity. Due to continuous changes, all kinds of dependencies, including the applications of model operations, must also be managed continuously. This comprises maintaining the existence of these dependencies and the appropriate (re-)application of model operations. The contribution of this thesis is an approach that combines traceability and model management to address the aforementioned challenges of configuring and applying MDE for software development. The approach is considered as a traceability approach because it supports capturing and automatically maintaining dependencies between DSMs. The approach is considered as a model management approach because it supports managing the automated (re-)application of heterogeneous model operations. In addition, the approach is considered as a comprehensive model management. Since the decomposition of model operations is encouraged to alleviate the first dimension of complexity, the subsequent composition of model operations is required to counteract their fragmentation. A significant portion of this thesis concerns itself with providing a method for the specification of decoupled yet still highly cohesive complex compositions of heterogeneous model operations. The approach supports two different kinds of compositions - data-flow compositions and context compositions. Data-flow composition is used to define a network of heterogeneous model operations coupled by sharing input and output DSMs alone. Context composition is related to a concept used in declarative model transformation approaches to compose individual model transformation rules (units) at any level of detail. In this thesis, context composition provides the ability to use a collection of dependencies as context for the composition of other dependencies, including model operations. In addition, the actual implementation of model operations, which are going to be composed, do not need to implement any composition concerns. The approach is realized by means of a formalism called an executable and dynamic hierarchical megamodel, based on the original idea of megamodels. This formalism supports specifying compositions of dependencies (traceability and model operations). On top of this formalism, traceability is realized by means of a localization concept, and model management by means of an execution concept. N2 - Die modellgetriebene Softwareentwicklung (MDE) verspricht heutzutage, durch das Verringern der inhärenten Komplexität der klassischen Softwareentwicklung, das Entwickeln von Software zu vereinfachen. Um dies zu erreichen, erhöht MDE das Abstraktions- und Automationsniveau durch die Einbindung domänenspezifischer Modelle (DSMs) und Modelloperationen (z.B. Modelltransformationen oder Codegenerierungen). DSMs sind konform zu domänenspezifischen Modellierungssprachen (DSMLs), die dazu dienen das Abstraktionsniveau der Softwareentwicklung zu erhöhen. Modelloperationen sind essentiell für die Softwareentwicklung da diese den Grad der Automatisierung erhöhen. Dennoch muss MDE mit Komplexitätsdimensionen umgehen die sich grundsätzlich aus der erhöhten sprachlichen und technologischen Heterogenität ergeben. Die erste Komplexitätsdimension ist das Konfigurieren einer Umgebung für MDE. Diese Aktivität setzt sich aus der Implementierung und Selektion von DSMLs sowie Modelloperationen zusammen. Eine solche Aktivität ist gerade durch die Implementierung und Anpassung von Modelloperationen zeitintensiv sowie fehleranfällig. Die zweite Komplexitätsdimension hängt mit der Anwendung von MDE für die eigentliche Softwareentwicklung zusammen. Das Anwenden von MDE ist eine Herausforderung weil eine Menge von heterogenen DSMs, die unterschiedlichen DSMLs unterliegen, erforderlich sind um ein komplexes Softwaresystem zu spezifizieren. Individuelle DSMLs werden verwendet um spezifische Aspekte eines Softwaresystems auf bestimmten Abstraktionsniveaus und aus bestimmten Perspektiven zu beschreiben. Hinzu kommt, dass DSMs sowie DSMLs grundsätzlich nicht unabhängig sind, sondern inhärente Abhängigkeiten besitzen. Diese Abhängigkeiten reflektieren äquivalente Aspekte eines Softwaresystems. Eine Teilmenge dieser Abhängigkeiten reflektieren Anwendungen diverser Modelloperationen, die notwendig sind um den Grad der Automatisierung hoch zu halten. Dies wird erschwert wenn man die erste Komplexitätsdimension hinzuzieht. Aufgrund kontinuierlicher Änderungen der DSMs, müssen alle Arten von Abhängigkeiten, inklusive die Anwendung von Modelloperationen, kontinuierlich verwaltet werden. Dies beinhaltet die Wartung dieser Abhängigkeiten und das sachgerechte (wiederholte) Anwenden von Modelloperationen. Der Beitrag dieser Arbeit ist ein Ansatz, der die Bereiche Traceability und Model Management vereint. Das Erfassen und die automatische Verwaltung von Abhängigkeiten zwischen DSMs unterstützt Traceability, während das (automatische) wiederholte Anwenden von heterogenen Modelloperationen Model Management ermöglicht. Dadurch werden die zuvor erwähnten Herausforderungen der Konfiguration und Anwendung von MDE überwunden. Die negativen Auswirkungen der ersten Komplexitätsdimension können gelindert werden indem Modelloperationen in atomare Einheiten zerlegt werden. Um der implizierten Fragmentierung entgegenzuwirken, erfordert dies allerdings eine nachfolgende Komposition der Modelloperationen. Der Ansatz wird als erweitertes Model Management betrachtet, da ein signifikanter Anteil dieser Arbeit die Kompositionen von heterogenen Modelloperationen behandelt. Unterstützt werden zwei unterschiedliche Arten von Kompositionen. Datenfluss-Kompositionen werden verwendet, um Netzwerke von heterogenen Modelloperationen zu beschreiben, die nur durch das Teilen von Ein- und Ausgabe DSMs komponiert werden. Kontext-Kompositionen bedienen sich eines Konzepts, das von deklarativen Modelltransformationen bekannt ist. Dies ermöglicht die Komposition von unabhängigen Transformationsregeln auf unterschiedlichsten Detailebenen. Die in dieser Arbeit eingeführten Kontext-Kompositionen bieten die Möglichkeit eine Menge von unterschiedlichsten Abhängigkeiten als Kontext für eine Komposition zu verwenden -- unabhängig davon ob diese Abhängigkeit eine Modelloperation repräsentiert. Zusätzlich müssen die Modelloperationen, die komponiert werden, selber keine Kompositionsaspekte implementieren, was deren Wiederverwendbarkeit erhöht. Realisiert wird dieser Ansatz durch einen Formalismus der Executable and Dynamic Hierarchical Megamodel genannt wird und auf der originalen Idee der Megamodelle basiert. Auf Basis dieses Formalismus' sind die Konzepte Traceability (hier Localization) und Model Management (hier Execution) umgesetzt. KW - Traceability KW - Modell Management KW - Megamodell KW - Modellgetriebene Entwicklung KW - Komposition KW - Traceability KW - Model Management KW - Megamodel KW - Model-Driven Engineering KW - Composition Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-64222 ER - TY - THES A1 - Polyvyanyy, Artem T1 - Structuring process models T1 - Strukturierung von Prozessmodellen N2 - One can fairly adopt the ideas of Donald E. Knuth to conclude that process modeling is both a science and an art. Process modeling does have an aesthetic sense. Similar to composing an opera or writing a novel, process modeling is carried out by humans who undergo creative practices when engineering a process model. Therefore, the very same process can be modeled in a myriad number of ways. Once modeled, processes can be analyzed by employing scientific methods. Usually, process models are formalized as directed graphs, with nodes representing tasks and decisions, and directed arcs describing temporal constraints between the nodes. Common process definition languages, such as Business Process Model and Notation (BPMN) and Event-driven Process Chain (EPC) allow process analysts to define models with arbitrary complex topologies. The absence of structural constraints supports creativity and productivity, as there is no need to force ideas into a limited amount of available structural patterns. Nevertheless, it is often preferable that models follow certain structural rules. A well-known structural property of process models is (well-)structuredness. A process model is (well-)structured if and only if every node with multiple outgoing arcs (a split) has a corresponding node with multiple incoming arcs (a join), and vice versa, such that the set of nodes between the split and the join induces a single-entry-single-exit (SESE) region; otherwise the process model is unstructured. The motivations for well-structured process models are manifold: (i) Well-structured process models are easier to layout for visual representation as their formalizations are planar graphs. (ii) Well-structured process models are easier to comprehend by humans. (iii) Well-structured process models tend to have fewer errors than unstructured ones and it is less probable to introduce new errors when modifying a well-structured process model. (iv) Well-structured process models are better suited for analysis with many existing formal techniques applicable only for well-structured process models. (v) Well-structured process models are better suited for efficient execution and optimization, e.g., when discovering independent regions of a process model that can be executed concurrently. Consequently, there are process modeling languages that encourage well-structured modeling, e.g., Business Process Execution Language (BPEL) and ADEPT. However, the well-structured process modeling implies some limitations: (i) There exist processes that cannot be formalized as well-structured process models. (ii) There exist processes that when formalized as well-structured process models require a considerable duplication of modeling constructs. Rather than expecting well-structured modeling from start, we advocate for the absence of structural constraints when modeling. Afterwards, automated methods can suggest, upon request and whenever possible, alternative formalizations that are "better" structured, preferably well-structured. In this thesis, we study the problem of automatically transforming process models into equivalent well-structured models. The developed transformations are performed under a strong notion of behavioral equivalence which preserves concurrency. The findings are implemented in a tool, which is publicly available. N2 - Im Sinne der Ideen von Donald E. Knuth ist die Prozessmodellierung sowohl Wissenschaft als auch Kunst. Prozessmodellierung hat immer auch eine ästhetische Dimension. Wie das Komponieren einer Oper oder das Schreiben eines Romans, so stellt auch die Prozessmodellierung einen kreativen Akt eines Individuums dar. Somit kann ein Prozess auf unterschiedlichste Weise modelliert werden. Prozessmodelle können anschließend mit wissenschaftlichen Methoden untersucht werden. Prozessmodelle liegen im Regelfall als gerichtete Graphen vor. Knoten stellen Aktivitäten und Entscheidungspunkte dar, während gerichtete Kanten die temporalen Abhängigkeiten zwischen den Knoten beschreiben. Gängige Prozessmodellierungssprachen, zum Beispiel die Business Process Model and Notation (BPMN) und Ereignisgesteuerte Prozessketten (EPK), ermöglichen die Erstellung von Modellen mit einer beliebig komplexen Topologie. Es gibt keine strukturellen Einschränkungen, welche die Kreativität oder Produktivität durch eine begrenzte Anzahl von Modellierungsalternativen einschränken würden. Nichtsdestotrotz ist es oft wünschenswert, dass Modelle bestimmte strukturelle Eigenschaften haben. Ein bekanntes strukturelles Merkmal für Prozessmodelle ist Wohlstrukturiertheit. Ein Prozessmodell ist wohlstrukturiert genau dann, wenn jeder Knoten mit mehreren ausgehenden Kanten (ein Split) einen entsprechenden Knoten mit mehreren eingehenden Kanten (einen Join) hat, und umgekehrt, so dass die Knoten welche zwischen dem Split und dem Join liegen eine single-entry-single-exit (SESE) Region bilden. Ist dies nicht der Fall, so ist das Modell unstrukturiert. Wohlstrukturiertheit ist aufgrund einer Vielzahl von Gründen wünschenswert: (i) Wohlstrukturierte Modelle sind einfacher auszurichten, wenn sie visualisiert werden, da sie planaren Graphen entsprechen. (ii) Wohlstrukturierte Modelle zeichnen sich durch eine höhere Verständlichkeit aus. (iii) Wohlstrukturierte Modelle haben oft weniger Fehler als unstrukturierte Modelle. Auch ist die Wahrscheinlichkeit fehlerhafter Änderungen größer, wenn Modelle unstrukturiert sind. (iv) Wohlstrukturierte Modelle eignen sich besser für die formale Analyse, da viele Techniken nur für wohlstrukturierte Modelle anwendbar sind. (v) Wohlstrukturierte Modelle sind eher für die effiziente Ausführung und Optimierung geeignet, z.B. wenn unabhängige Regionen eines Prozesses für die parallele Ausführung identifiziert werden. Folglich gibt es eine Reihe von Prozessmodellierungssprachen, z.B. die Business Process Execution Language (BPEL) und ADEPT, welche den Modellierer anhalten nur wohlstrukturierte Modelle zu erstellen. Solch wohlstrukturiertes Modellieren impliziert jedoch gewisse Einschränkungen: (i) Es gibt Prozesse, welche nicht mittels wohlstrukturierten Prozessmodellen dargestellt werden können. (ii) Es gibt Prozesse, für welche die wohlstrukturierte Modellierung mit einer erheblichen Vervielfältigung von Modellierungs-konstrukten einhergeht. Aus diesem Grund vertritt diese Arbeit den Standpunkt, dass ohne strukturelle Einschränkungen modelliert werden sollte, anstatt Wohlstrukturiertheit von Beginn an zu verlangen. Anschließend können, sofern gewünscht und wo immer es möglich ist, automatische Methoden Modellierungsalternativen vorschlagen, welche "besser" strukturiert sind, im Idealfall sogar wohlstrukturiert. Die vorliegende Arbeit widmet sich dem Problem der automatischen Transformation von Prozessmodellen in verhaltensäquivalente wohlstrukturierte Prozessmodelle. Die vorgestellten Transformationen erhalten ein strenges Verhaltensequivalenzkriterium, welches die Parallelität wahrt. Die Resultate sind in einem frei verfügbaren Forschungsprototyp implementiert worden. KW - Strukturierung KW - Wohlstrukturiertheit KW - Prozesse KW - Verhalten KW - Modellierung KW - Structuring KW - Well-structuredness KW - Process KW - Behavior KW - Modeling Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-59024 ER - TY - THES A1 - Schapranow, Matthieu-Patrick T1 - Real-time security extensions for EPCglobal networks Y1 - 2012 CY - Potsdam ER -