tr-announce

Download

tr-announce@lists.rwth-aachen.de

March 2010

1 participants
2 discussions

2010-07: A New Intersection Model for Multitolerance Graphs, Hierarchy, and Efficient Algorithms
by Carsten Fuhs 27 Mar '10

27 Mar '10

The following technical report is available from http://aib.informatik.rwth-aachen.de: A New Intersection Model for Multitolerance Graphs, Hierarchy, and Efficient Algorithms George B. Mertzios AIB 2010-07 Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs has attracted many research efforts, mainly due to its interesting structure and its numerous applications, while a number of variations of this model has appeared. In particular, one of the most natural generalizations of tolerance graphs, namely \emph{multitolerance} graphs, has been introduced in 1998 \cite{Parra98}, where two tolerances are allowed for each interval. These two tolerances - one from the left and one from the right side of the interval - define an infinite number of the so called \emph{tolerance-intervals}, which make the multitolerance model inconvenient to cope with. The main subclass of multitolerance graphs, namely bounded multitolerance graphs, coincide with the widely known class of trapezoid graphs that has been extensively studied. In this article we introduce the first non-trivial intersection model for general multitolerance graphs, given by objects in the three-dimensional space called \emph{trapezoepipeds}, which unifies in a simple and intuitive way the trapezoid representation for bounded multitolerance graphs and the recently introduced parallelepiped representation for tolerance graphs \cite{MSZ-Model-SIDMA-09}. Apart from being important on its own, this new intersection model proves to be a powerful tool for designing efficient algorithms. Given a multitolerance graph with $n$ vertices and $m$ edges, we present three new algorithms that compute a minimum coloring and a maximum clique in optimal $O(n\log n)$ time, and a maximum weight independent set in $O(m + n\log n)$ time - this algorithm also improves the best known running time of $O(n^{2})$ for the same problem on tolerance graphs \cite{MSZ-Model-SIDMA-09}. Moreover, we prove several structural results on the class of multitolerance graphs, complementing thus the hierarchy of perfect graphs given in \cite{GolTol04}. The resulting hierarchy of classes of perfect graphs is \emph{complete}, i.e. all inclusions are strict.

1 0

2010-03: MontiCore: Agile Entwicklung von domänenspezifischen Sprachen im Software-Engineering
by Carsten Fuhs 27 Mar '10

27 Mar '10

The following technical report is available from http://aib.informatik.rwth-aachen.de: MontiCore: Agile Entwicklung von domänenspezifischen Sprachen im Software-Engineering Holger Krahn AIB 2010-03 Domänenspezifische Sprachen (engl. domain specific language - DSL) sind Sprachen der Informatik, mit denen kompakte Problemlösungen aus eng umrissenen fachlichen oder technischen Anwendungsgebieten formuliert werden können. Durch die Nutzung einer fachspezifischen Notation gelingt die Integration von Experten einfacher als bei einer herkömmlichen Softwareentwicklung, weil die Modelle von ihnen besser verstanden werden. Die automatische Erzeugung von Produktivcode aus domänenspezifischen Modellen ist eine effektive Form der modellgetriebenen Entwicklung. Die derzeitige DSL-Entwicklung erschwert aufgrund der fehlenden zentralen Sprachreferenz, die die abstrakte und konkrete Syntax umfasst, und der unzureichenden Modularisierung eine agile und effiziente Vorgehensweise. Es mangelt an Methoden und Referenzarchitekturen, um komplexe modellbasierte Werkzeuge strukturiert entwerfen und in der Softwareentwicklung einsetzen zu können. In dieser Arbeit wird daher die DSL-Entwicklung mit dem MontiCore-Framework beschrieben, das die modulare Entwicklung von textuellen DSLs und darauf basierten Werkzeugen erlaubt. Die wichtigsten wissenschaftlichen Beiträge lassen sich wie folgt zusammenfassen: * Die Definition von textuellen domänenspezifischen Sprachen wird durch ein kompaktes grammatikbasiertes Format ermöglicht, das sowohl die abstrakte als auch die konkrete Syntax einer Sprache definiert und so als zentrale Dokumentation für die Entwickler und Nutzer einer DSL fungiert. Die entstehende abstrakte Syntax entspricht etablierten Metamodellierungs-Technologien und erweitert übliche grammatikbasierte Ansätze. * Die Wiederverwendung von Teilsprachen innerhalb der modellgetriebenen Entwicklung wird durch zwei Modularitätsmechanismen vereinfacht, da so existierende Artefakte auf eine strukturierte Art und Weise in neuen Sprachdefinitionen eingesetzt werden können. Grammatikvererbung erlaubt die Spezialisierung und Erweiterung von Sprachen. Einbettung ermöglicht die flexible Kombination mehrerer Sprachen, die sich auch in ihrer lexikalischen Struktur grundlegend unterscheiden können. * Das MontiCore-Grammatikformat ist modular erweiterbar, so dass zusätzliche Informationen als so genannte Konzepte spezifiziert werden können und darauf aufbauend weitere Infrastruktur aus der Sprachdefinition generiert werden kann. Die Erweiterungsfähigkeit wird durch Konzepte zur deklarativen Spezifikation von Links in der abstrakten Syntax und durch ein Attributgrammatiksystem demonstriert. * Die Entwicklung von Codegeneratoren und Analysewerkzeugen für DSLs wird durch die Bereitstellung einer Referenzarchitektur entscheidend vereinfacht, so dass bewährte Lösungen ohne zusätzlichen Entwicklungsaufwand genutzt werden können. Die Qualität der entstehenden Werkzeuge wird damit im Vergleich zu existierenden Ansätzen gehoben. * Es wird demonstriert, wie compilierbare Templates ein integriertes Refactoring der Templates und einer Laufzeitumgebung ermöglichen. Darauf aufbauend wird eine Methodik definiert, die aus exemplarischem Quellcode schrittweise einen Generator entwickelt, dessen Datenmodell automatisiert abgeleitet werden kann. Die beschriebenen Sprachen und Methoden sind innerhalb des Frameworks MontiCore implementiert. Ihre Anwendbarkeit wird durch die Entwicklung des MontiCore-Frameworks im Bootstrapping-Verfahren und durch zwei weitere Fallstudien demonstriert.

1 0