05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
143 results
Search Results
Item Open Access Das Ordnungsproblem für Automatengruppen und verwandte Fragestellungen(2019) Bühler, AndreasIn dieser Arbeit werden Problemstellungen in der Klasse der Automatenhalbgruppen untersucht. Ein besonderer Augenmerk gilt dabei dem Ordnungsproblem welches im Allgemeinen sowohl für Automatenhalbgruppen als auch für Automatengruppen unentscheidbar ist. Es wird dann für die Klasse der Automatenhalbgruppen mit beschränkter Aktivität ein Algorithmus mit überraschend geringem Platzbedarf vorgestellt. Danach wird ein Entscheidungsalgorithmus für das Mitgliedschaftsproblem in ultimativ periodischen Teilmengen von Automatenhalbgruppen beschränkter Aktivität erarbeitet. Dieses Problem beinhaltet insbesondere das Mitgliedschaftsproblem in monogenen Unterhalbgruppen, welches dadurch ebenfalls in Automatenhalbgruppen beschränkter Aktivität entscheidbar ist.Item Open Access Normalformenberechnung in Graph-Gruppen und Coxeter-Gruppen(2011) Kausch, JonathanIm Rahmen der Diplomarbeit wurde das Normalformenproblem für partiell kommutative Gruppen in logarithmischem Platz untersucht. Diese Gruppen sind in der Mathematik als Graph-Gruppen oder "rechtwinklige Artingruppen" bekannt und werden u.a. in der kombinatorischen Gruppentheorie untersucht. In der Informatik erscheinen sie als natürliche Erweiterung der Spurmonoide, die von Keller und Mazurkiewicz eingeführt wurden und insbesondere für die Untersuchung von Nebenläufigkeit in der Informatik von Bedeutung sind. Zur Analyse der Normalformenproblemberechnung werden die Graph-Gruppen zunächst in rechtwinklige Coxeter-Gruppen eingebettet. Für beliebige Coxeter-Gruppen kann das Alphabet der längenlexikographischen Normalform in logarithmischem Platz bestimmt werden. Darauf aufbauend kann die längenlexikographische Normalform in rechtwinkligen Coxeter-Gruppen berechnet werden. Für allgemeine Coxeter Gruppen wird in "Combinatorics of Coxeter Groups" (Björner, Brenti) ein Algorithmus vorgestellt, der die Normalform mit linear vielen reellen arithmetischen Operationen und Vergleichen bestimmt. Die Berechnung lässt sich allerdings nicht ausschließlich mit ganzen Zahlen durchführen, sondern es werden komplexe Einheitswurzeln benötigt. In dieser Arbeit wird geklärt, wie viele Bits zur Repräsentation notwendig sind. Außerdem wird ein elementarer Beweis angegeben, der zeigt, dass für Coxeter-Gruppen ein präperfektes Ersetzungssystem existiert. Ein präperfektes Ersetzungssystem ist ein Ersetzungssystem, welches nur längenerhaltende und längenreduzierende Regeln besitzt. Coxeter-Gruppen gehören unter anderem zur Klasse der automatischen Gruppen. Für rechtwinklige Coxeter-Gruppen wird in dieser Arbeit ein Beweis angegeben, der zeigt, dass diese automatisch sind.Item Open Access Experimentelle Bestimmung vergleichsoptimaler Sortieralgorithmen(2019) Obst, JulianDie gängigsten Sortierverfahren sortieren Mengen, indem sie zwei Elemente miteinander vergleichen und damit Schritt für Schritt eine Ordnung aufbauen. Es stellt sich die Frage, was die minimale Anzahl an Vergleichen ist, die benötigt wird, um eine beliebige Permutation einer Menge zu sortieren. Das zentrale Ziel dieser Arbeit ist es, die theoretischen Grundlagen zur Bestimmung vergleichsoptimaler Sortieralgorithmen zu erläutern und die Anzahl der Vergleiche von solchen Algorithmen zu bestimmen. Dabei werden auch die praktischen Ansätze besprochen, die benutzt wurden, um einen Algorithmus zu erstellen, der dieses Problem lösen soll. In diesem Zusammenhang werden die Aspekte der Implementierung dieses Algorithmus beleuchtet. Vor allem werden in diesem Punkt aber auch Optimierungen beschrieben, die helfen sollen, die Laufzeit zu verkürzen. Für n = 12, 13 konnten bekannte Ergebnisse bestätigt werden.Item Open Access Kürzeste Wege im Wikipedia-Linkgraph(2013) Kara, FerdiDiese Arbeit beschäftigt sich mit unterschiedlichen Beschleunigungstechniken zur Suche kürzester Pfade in einem Graph. Im Gegensatz zu klassischen Weganfragen wird jedoch kein geographischer Graph als Datenquelle genutzt, sondern der manuell extrahierte Wikipedia-Linkgraph. Um eine Vergleichsgrundlage für Beschleunigungsalgorithmen zu erhalten, wird eine Auswertung der Breitensuche als Basis geschaffen. Zur optimalen Auswahl eines Beschleunigungsalgorithmus ist es unabdingbar, ein grundlegendes Verständnis über die Struktur des Graphen zu erhalten. In Folge dieser Untersuchung und einer Vorstellung unterschiedlicher Beschleunigungsalgorithmen wird das Transitknotenkonzept, welches in der Arbeit von Bast u.a. [BFM+07] vorgestellt wurde, auf den Wikipedia-Linkgraph angewandt. Um das Konzept auf einen nicht geographischen Graph anwenden zu können, wird nach der Arbeit von Eisner/Funke [EF12] die Suche nach einer passenden Transitknotenmenge als Hitting-Set-Problem formuliert. Die Qualität der ausgewählten Transitknoten wird mit unterschiedlichen Konstruktionen zur Transitknotenbestimmung verglichen und die verschiedenen Lösungen werden anhand der vorhergehenden Untersuchung der Graphstruktur erklärt. Schlussendlich wird gezeigt, warum die verschiedenen Konstruktionen der Transitknotenmenge schlechte Ergebnisse liefern, wodurch das Transitknotenkonzept angewandt auf den Wikipedia-Linkgraph fehlschlägt.Item Open Access Fragments of first-order logic over infinite words(2009) Diekert, Volker; Kufleitner, ManfredWe give topological and algebraic characterizations as well as language theoretic descriptions of the following subclasses of first-order logic for omega-languages: Sigma2, FO2, the intersection of FO2 and Sigma2, and Delta2 (and by duality Pi2 and the intersection of FO2 and Pi2). These descriptions extend the respective results for finite words. In particular, we relate the above fragments to language classes of certain (unambiguous) polynomials. An immediate consequence is the decidability of the membership problem of these classes, but this was shown before by Wilke and Bojanczyk and is therefore not our main focus. The paper is about the interplay of algebraic, topological, and language theoretic properties.Item Open Access Reachability analysis of multithreaded software with asynchronous communication(2005) Bouajjani, Ahmed; Esparza, Javier; Schwoon, Stefan; Strejcek, JanWe introduce asynchronous dynamic pushdown networks (ADPN), a new model for multithreaded programs in which pushdown systems communicate via shared memory. ADPN generalizes both CPS (concurrent pushdown systems) and DPN (dynamic pushdown networks). We show that ADPN exhibit several advantages as a program model. Since the reachability problem for ADPN is undecidable even in the case without dynamic creation of processes, we address the bounded reachability problem, which considers only those computation sequences where the (index of the) thread accessing the shared memory is changed at most a fixed given number of times. We provide efficient algorithms for both forward and backward reachability analysis. The algorithms are based on automata techniques for symbolic representation of sets of configurations.Item Open Access Neue Bedienkonzepte für mobile Routenplaner(2014) Bahle, StefanieBei Routenplanern werden Start und Ziel typischerweise über eine Display-Tastatur eingegeben, was insbesondere bei Smartphones mit kleinem Display mühsam sein kann. Vor allem unter erschwerten Bedingungen, wie während der Fahrt auf dem Fahrrad oder mit Handschuhen, ist eine Eingabe über die Display-Tastatur kaum möglich. Aus diesem Grund wurden in dieser Arbeit Bedienmethoden entwickelt, welche die Bedienung unter erschwerten Bedingungen erleichtern sollen. Die Ansätze sind verschiedene Suchen mit zwei, drei oder vier Buttons zur Auswahl des Zielortes sowie eine Methode die die Lautstärketasten des Smartphones nutzt. Hierbei muss der gesuchte Ort alphabetisch eingeordnet werden und der entsprechende Button ausgewählt. Diese Bedienmethoden wurden in einer Benutzerstudie mit bekannten Eingabemethoden verglichen um festzustellen, ob die neuen Methoden eine bessere Alternative darstellen. Dies konnte zwar nicht bestätigt werden, dennoch sollte ein Weiterverfolgen der zugrunde liegenden Idee nicht ausgeschlossen werden.Item Open Access Multimodale Bereichsanfragen im Kontext von Routenplanern(2012) Bahrdt, DanielUm eine Route zu planen, müssen Start, Ziel und eventuelle Zwischenpunkte bekannt sein. Sind deren Koordinaten nicht bekannt, jedoch andere Informationen, so könnten die Routenpunkte mit Hilfe dieser Informationen gefunden werden. OpenStreetMap bietet hierfür eine interessante Datenbasis, da Geo-Objekte oftmals nicht nur durch Text sondern auch durch strukturierte Informationen beschrieben werden. Ein Supermarkt besitzt dabei neben den Koordinaten noch den Namen, den Typ des Supermarktes sowie eventuell Öffnungszeiten, Internetadressen und mehr. Diese Informationen sollen in dieser Arbeit durch eine Suchmaschinen-ähnliche Texteingabe zugänglich gemacht werden. Die Suche nach textuellen Informationen soll hierbei unter anderem eine Suche nach Teilzeichenketten ermöglichen. Die Ergebnisse der Suche können durch einfache Mengenoperationen miteinander in Verbindung gebracht werden, sodass eine einfache relationale Abfragesprache entsteht. Hauptanwendungsgebiet soll hierbei die Suche auf mobilen Geräten sein. Zu Vergleichszwecken wurde auch ein Programm zur Suche auf einem normalen Desktoprechner entwickelt.Item Open Access Experimental analysis of randomized calculations of average rankings(2016) Zeiß, TimListing a set of points, such that a point gets a higher rank, if none of its coordinates is smaller, creates a partial order. It is possible to get a ranking without randomly favoring certain points, by averaging all valid rankings. However, this brute force algorithm is too slow for more than ten points. To handle more points, we will give a randomized, approximative approach to solve this problem and analyze the convergence rates of different strategies.Item Open Access Das Geographiespiel in der Theorie und seine Realisierung als App(2013) Steinhart, DavidDas sogenannte "Geographiespiel" ist ein simples Spiel, welches dem Leser eventuell in einer Variante bekannt ist. Dabei nennen zwei Spieler abwechselnd Städtenamen, wobei diese jeweils mit dem Endbuchstaben der vorherigen Stadt beginnen müssen. Nennt Spieler A beispielsweise "Stuttgart", so kann Spieler B "Tübingen" als Antwort geben. Daraufhin wären "Nürnberg" oder "New York" mögliche Antworten. Das Ende des Spieles ist erreicht, wenn einem der beiden Spieler keine weitere Stadt einfällt und er somit das Spiel verliert. Bereits genannte Städte dürfen nicht erneut verwendet werden. Denkbar wäre auch eine Variante, in der Personen oder Automarken genannt werden. Beim Geographiespiel wird untersucht, welcher Spieler bei einer festgelegten Städteliste und optimaler Spielweise gewinnen wird. Das Spiel wird dahingehend erweitert, dass die Anzahl der Anfangs- und Endbuchstaben nun nicht mehr auf 26 festgelegt ist. Das Auswerten einer erweiterten Version des Spieles, die eine unbegrenzte Anzahl an Buchstaben zulässt, liegt in P-SPACE. Gibt es dagegen nur endlich vielen Buchstaben, liegt das Problem in P. Zudem ist es für sehr kleine Instanzen (nur 1 bzw. 2 Buchstaben) möglich, diese in logarithmischem Platz zu lösen. Ziel dieser Arbeit ist es, Instanzen mit endlich vielen Buchstaben genauer zu untersuchen. Einerseits wird der Fall mit 3 bzw. 4 Buchstaben betrachtet. Andererseits wird die Möglichkeit untersucht, das Auswertungsproblem für Schaltkreise auf das Geographiespiel mit endlich vielen Buchstaben zu reduzieren und so die P-Vollständig zu zeigen. Als praktischer Teil der Arbeit wurde das Geographiespiel als App implementiert. Dies dient der Untersuchung, mit welchem Aufwand und bis zu welchen Grad die Umsetzung realisierbar ist.