05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
Search Results
Item Open Access Rankers over infinite words(2010) Dartois, Luc; Kufleitner, Manfred; Lauser, AlexanderWe consider the fragments FO2, the intersection of Sigma2 and FO2, the intersection of Pi2 and FO2, and Delta2 of first-order logic FO[<] over finite and infinite words. For all four fragments, we give characterizations in terms of rankers. In particular, we generalize the notion of a ranker to infinite words in two possible ways. Both extensions are natural in the sense that over finite words, they coincide with classical rankers and over infinite words, they both have the full expressive power of FO2. Moreover, the first extension of rankers admits a characterization of the intersection of Sigma2 and FO2 while the other leads to a characterization of the intersection of Pi2 and FO2. Both versions of rankers yield characterizations of the fragment Delta2. As a byproduct, we also obtain characterizations based on unambiguous temporal logic and unambiguous interval temporal logic.Item Open Access Methods for coreference visualization and annotation(2010) Burkovski, Andre; Heidemann, Gunther; Kobdani, Hamidreza; Schütze, HinrichIn this report we present methods for visualization of coreferences. We use Self Organizing Maps, graph-based models, and text-based techniques to visualize coreference information from a pair-wise model and offer an interactive presentation of the feature space. We introduce our software system and several visualizations of the Self Organizing Map. The visualizations enable the user to explore the feature space, provide insights for feature engineering and allow a fast annotation of data with coreference information.Item Open Access Efficient programmable deterministic self-test(2010) Hakmi, Abdul-Wahid; Wunderlich, Hans-Joachim (Prof. Dr. habil.)In modern times, integrated circuits (ICs) are used in almost all electronic equipment ranging from household appliances to space shuttles and have revolutionized the world of electronics. Continuous reductions in the manufacturing costs as well as the size of this technology have allowed the development of very sophisticated ICs for common use. Post fabrication testing is necessary for each IC in order to ensure the quality and the safety of human life. The improvement in technology as well as economies of scale are continuously reducing fabrication costs. On the other hand, the increasing complexity of circuits is leading to higher test costs. These increasing test costs affect the market price of a chip. A test set is a set of binary patterns that are applied on the circuit inputs to detect the potential faults. Only a small number of bits in a test set are specified to 0 or 1 called care bits while other bits called don't care bits may assume random values. Test sets volume is characterized by the number of patterns as well as the size of each pattern in a test set. The increasing number of gates in nanometer ICs has resulted in an explosive increase in test sets volume. This increase in test sets volume is the major cause for rapidly growing test costs. An IC is tested either by using an automatic test equipment (ATE) or with the help of special hardware added on-chip that performs a self-test. These two approaches as well as their hybrid derivatives offer various trade-offs in test costs, quality, reliability and test time. In ATE testing high test sets volume leads to the requirement of expensive testers with large storage capacity while in self-test it results in significant hardware overhead. A test set is highly compressible due to the presence of a large number of don't care bits. The Test data compression techniques are used to limit test sets volume and hence the involved test cost. These compressed test sets are applicable to both ATE and Self-test methodologies. Compression of a test set depends on its statistical attributes such as the percentage and the distribution of care bits. The available test compression schemes assume that all the test sets have similar statistical attributes which is not always true. These attributes vary considerably among various test sets depending on the circuit structure and the targeted trade-offs. To get optimized reduction in test sets volume, test sets with different statistical attributes have to be addressed separately. In this work we analyze various test sets of industrial circuits and categorize them into three classes based on their statistical attributes. By examining each class differently, three novel compression methods and decompression architectures are proposed. The proposed test compression methods are equally adaptable in ATE testing and self-test. Three low cost programmable self-test schemes offering various trade-offs in testing are developed by applying these methods. The experimental results obtained with the test sets of large industrial circuits show that the proposed compression methods reduce storage requirements by more than half compared to the most efficient available methods. First time in literature the total number of bits in a compressed test set are lesser than the number of care bits in the original test set. The additional advantages of proposed methods include guaranteed encoding, significant reduction in decompression time overhead and programmability of decompression hardware.Item Open Access First-order fragments with successor over infinite words(2010) Kallas, Jakub; Kufleitner, Manfred; Lauser, AlexanderWe consider fragments of first-order logic and as models we allow finite andinfinite words simultaneously. The only binary relations apart from equalityare order comparison < and the successor predicate +1. We givecharacterizations of the fragments Sigma2 = Sigma2[<,+1] and FO2 = FO2[<,+1] interms of algebraic and topological properties. To this end we introduce thefactor topology over infinite words. It turns out that a language L is in theintersection of FO2 and Sigma2 if and only if L is the interior of an FO2language. Symmetrically, a language is in the intersection of FO2 and Pi2 ifand only if it is the topological closure of an FO2 language. The fragmentDelta2, which by definition is the intersection Sigma2 and Pi2 contains exactlythe clopen languages in FO2. In particular, over infinite words Delta2 is astrict subclass of FO2. Our characterizations yield decidability of themembership problem for all these fragments over finite and infinite words; andas a corollary we also obtain decidability for infinite words. Moreover, wegive a new decidable algebraic characterization of dot-depth 3/2 over finitewords. Decidability of dot-depth 3/2 over finite words was first shown by Glaßer andSchmitz in STACS 2000, and decidability of the membership problem for FO2 overinfinite words was shown 1998 by Wilke in his habilitation thesis whereasdecidability of Sigma2 over infinite words was not known before.Item Open Access On the iterated hairpin completion(2010) Kopecki, SteffenThe hairpin completion is a natural operation on formal languages which has been inspired by biochemistry and DNA-computing. In this paper we solve two problems which were posed first in 2008 and 2009, respectively, and still left open: 1.) It is known that the iterated hairpin completion of a regular language is not context-free in general, but it was open whether the iterated hairpin completion of a singleton or finite language is regular or at least context-free. We will show that it can be non-context-free. (It is of course context-sensitive.) 2.) A restricted but also very natural variant of the hairpin completion is the bounded hairpin completion. It was unknown whether the iterated bounded hairpin completion of a regular language remains regular. We prove that this is indeed the case. Actually we derive a more general result. We will present a general representation of the iterated bounded hairpin completion for any language using basic operations. Thus, each language class closed under these basic operations is also closed under iterated bounded hairpin completion.Item Open Access Similarity search with set intersection as a distance measure(2010) Hoffmann, Benjamin Sascha; Diekert, Volker (Prof. Dr.)This thesis deals with a fundamental algorithmic problem. Given a database of sets and a query set, we want to determine a set from the database that has a maximal intersection with the query set. It is allowed to preprocess the database so that queries can be answered efficiently. We solve the approximate version of this problem. We investigate two randomized input models which are derived from real inputs. We present a deterministic algorithm for each of them. Under the assumption that the database and the query set follow one of these models, the corresponding algorithm determines with high probability a set from the database that has no maximal intersection with the query set, but an intersection that achieves a large proportion of the maximal size. Depending on the model, the query time is either quasi-linear in the sum of the database size and the number of different elements from all sets, or it is polylogarithmic in the database size. Thus, both algorithms are significantly faster than a naive algorithm intersecting the query set with each single database set.Item Open Access Shortest paths and negative cycle detection in graphs with negative weights. I, The Bellman-Ford-Moore algorithm revisited(2010) Lewandowski, StefanSince the mid 1950's when Bellman, Ford, and Moore developped their shortest path algorithm various attempts were made to beat the O(nm) barrier without success. For the special case of integer weights Goldberg's algorithm gave a theoretical improvement, but the algorithm isn't competative in praxis. This technical report is part one of a summary of existing n-pass algorithms and some new variations. In this part we consider the classical algorithm and variations that differ only in the data structure used to maintain the set of nodes to be scanned in the current and following pass. We unify notation and give some experimental results for the average case on various graph classes.Item Open Access Partially ordered two-way Büchi automata(2010) Kufleitner, Manfred; Lauser, AlexanderWe introduce partially ordered two-way Büchi automata over infinite words. As for finite words, the nondeterministic variant recognizes the fragment Sigma2 of first-order logic FO[<] and the deterministic version yields the Delta2-definable omega-languages. As a byproduct of our results, we show that deterministic partially ordered two-way Büchi automata are effectively closed under Boolean operations. In addition, we have coNP-completeness results for the emptiness problem and the inclusion problem over deterministic partially ordered two-way Büchi automata.Item Open Access Ausführbare Integrationsmuster(2010) Scheibler, Thorsten; Leymann, Frank (Prof. Dr.)Die Integration von großen IT Anwendungen ist für viele Firmen eine der bedeutendsten IT Herausforderungen, um die Geschäftsprozesse innerhalb eines Unternehmens effizient durchführen zu können. Zum einen gab es kein standardisiertes Vorgehen, wie man Integrationslandschaften konzipieren und spezifizieren konnte. Zum anderen bestand keine durchgängige Methode, die resultierenden zumeist abstrakten Architekturen in ausführbare Systeme zu überführen. Mit der Einführung von Integrationsmustern wurde ein großer Beitrag geleistet, um Integrationslandschaften einheitlich und technologieunabhängig darstellen zu können. Jedoch klaffte immer noch eine große Lücke zwischen der Modellierung und der Implementierung dieser Landschaften. Die tatsächliche Realisierung wurde durch Entwickler geleistet, indem die Landschaften interpretiert und entsprechend ausführbare Integrationslogik erstellt wurde. Diese Kluft muss geschlossen werden, damit Architekten und Entwickler besser miteinander kommunizieren und ausführbare Integrationslösungen effizienter realisiert werden können. Diese Dissertation leistet einen Beitrag, um diese Lücke zu schließen. Im Rahmen dieser Arbeit wird eine Methode entwickelt, mit der ausgehend von Integrationsmustern automatisiert ausführbare Integrationslösungen erzeugt werden können. Es wird eigens ein Lebenszyklus konzipiert, der die unterschiedlichen Phasen der Erstellung von ausführbaren Integrationslösungen beschreibt. Die Methode basiert auf der Modell-getriebenen Entwicklung. Die vormals visuellen und textuellen Repräsentationen der Integrationsmuster werden dazu in ein formales Modell überführt. Parametrisierbare Integrationsmuster dienen fortan als Grundlage der Methode. Durch die Parameter jedes einzelnen Musters kann das erwartete Verhalten eines Muster technologieunabhängig spezifiziert werden. Außerdem beschreibt das Modell die Zusammenhänge der einzelnen Muster und wie sie miteinander kommunizieren. Das Modell der parametrisierbaren Integrationsmuster wird von einem Generierungsalgorithmus verwendet, um automatisiert ausführbare Integrationslösungen zu erstellen. Der Algorithmus fügt dazu plattformspezifische Informationen hinzu, so dass eine Integrationslösung auf einer bestimmten Zielinfrastruktur ausgeführt werden kann. Ein Modell kann dabei von verschiedenen Algorithmen verwendet werden und daher in verschiedene Ausführungsumgebungen übersetzt werden. Diese Methode ist daher nicht auf bestimmte Zielinfrastrukturen beschränkt. Im Verlauf der Arbeit werden parametrisierbare Integrationsmuster auf drei sehr unterschiedlichen Infrastrukturen abgebildet und ausgeführt. Dies verdeutlicht die Allgemeinheit der Methode und die leichte Erweiterbarkeit auf neue Technologien und veränderte Anforderungen. Zur Unterstützung der Methode wird außerdem eine Werkzeugkette erstellt, die es Systemarchitekten erlaubt, eine Integrationslösung grafisch zu konzipieren. Das Werkzeug GENIUS umfasst eine graphische Modellierungsoberfläche, mit der parametrisierbare Integrationsmuster zu einer Integrationslösung zusammengefasst werden können. Außerdem werden zwei Algorithmen integriert, die ausführbare Integrationslösungen für zwei unterschiedliche Zielinfrastrukturen erzeugen. Diese Dissertation schließt somit die Lücke zwischen Architektur und Entwicklung, indem eine auf der Modell-getriebenen Entwicklung basierenden Methode entwickelt wird, mit deren Hilfe parametrisierbare Integrationsmuster als direkte Spezifikation für ausführbare Systeme dienen und automatisiert in diese Systeme überführt werden.Item Open Access A viable architecture for autonomic management of distributed software components(2010) Stoyanov, Emil; Roller, Dieter (Prof.Dr.)Autonomic Computing is a brand of system design approaches which enable IT systems with self-management capabilities such as self-configuration, self-healing, self-protection and self-optimization. Although the field of distributed system management has achieved considerable advances, building autonomic management solutions for heterogeneous component-based systems presents five major challenges. First, component deployment and its management gets difficult with the growth of the system, because of the variety of component models with their own specifics. Second, each component framework provides its own way and interface for management creating redundancy and variety of management routines. Third, software components evolve separately which introduces problems with compatibility upon system upgrade. Forth, there are remote dependencies which are difficult to tack and this may cause unpredicted inconsistency of the system after component update. Finally, the integration of a management sub-system influences the overall system complexity by making it dependent on interfaces and functionality of the management module. This thesis introduces an architectural approach which addresses these challenges. An organizational meta-model represents the architectural constraints for encapsulation of software components and defines requirements for feedback loops adapted from the Viable System Model for software components. It enables modeling of viable organization and communication management on the levels of component deployment and runtime operations. The autonomic management architecture consists of modules that facilitate monitoring component states, an operation manager that allows inspection of distributed dependencies by utilizing the notion of the managed communication channel. Its design conforms with the recommendations of the proposed organizational model. A channel management middleware implements the necessary functionality for establishing communication channels and provides interfaces for integration of autonomic managers which follow the requirements of the organizational and communication model. A prototype of the middleware has been developed to implement the architectural approach for real-world scenarios in two separate domains - Smart Home and Distributed Product Development Support Systems. It has demonstrated the usability of the architecture by satisfying the management requirements of these domains and addressing the management challenges.
- «
- 1 (current)
- 2
- 3
- »