05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
8 results
Search Results
Item Open Access Makanin's algorithm for solving word equations with regular constraints(1998) Diekert, VolkerWe give a self-contained proof of a fundamental result of Makanin (1977), which solves the satisfiability problem of equations with constants over free monoids. Our presentation of Makanin's algorithm is borrows Schulz (1992a), where Makanin's result is extended to the case where solutions are restricted by imposing regular constraints on the variables. This report appears (with minor modifications) as a chapter of the new book of M. Lothaire Algebraic Combinatorics on Words.Item Open Access Endbericht der Projektgruppe Transportoptimierung(1998) Fleischmann, Jörg; Hermes, Lars; Spribille, TobiasDieses Dokument ist die Fortsetzung des Zwischenberichts der Projektgruppe Transportoptimierung (TR-1996-06). Beide Berichte zusammen ergeben einen kontinuierlichen Überblick über die Arbeit der Projektgruppe von Oktober 1997 bis September 1998. Im Rahmen der Projektgruppe soll das Programm TROSS (TRansport-Organisation für Soziale Serviceanbieter) zur Verwaltung und Optimierung von sozialen Fahrdiensten entwickelt werden, das dann beim DRK in Stuttgart eingesetzt wird. Der Endbericht setzt dort an, wo der Zwischenbericht endet: Beim Entwurf. Teile des Entwurfs, die erst nach dem Zwischenbericht fertiggestellt wurden, oder deren Notwendigkeit sich gar erst während der Implementierungsphase ergab, sind hier festgehalten. Danach folgt der Bericht über die wichtigsten Aspekte der Projektphasen Implementierung und Test. Eine Übersicht über das entstandene Programm aus Programmierersicht sowie eine Bedienungsanleitung beendet die Beschreibung des entstandenen Systems. Abschließend wird der Ablauf des Projekts diskutiert und Anregungen für zukünftige Projektgruppen werden gegeben.Item Open Access Workshop on Formal Languages, Automata and Petri Nets(1998) Petersen, HolgerThis report contains abstracts of the lectures presented at the workshop 'Formal Languages, Automata and Petri-Nets' held at the University of Stuttgart on January 16-17, 1998. The workshop brought together partners of the German-Hungarian project No. 233.6, Forschungszentrum Karlsruhe, Germany, and No. D/102, TeT Foundation, Budapest, Hungary. It provided an opportunity to present work supported by this project as well as related topics.Item Open Access 7-bit meta-transliterations for 8-bit romanizations(1997) Lagally, KlausWe propose a general strategy for deriving 7-bit encodings for texts in languages which use an alphabetic non-Roman script, like Arabic, Persian, Sanskrit and many other Indic scripts, and for which there is some transliteration convention using Roman letters with additional diacritical marks. These schemes, which we will call 'meta-transliterations', are based on using single ASCII letters for representing Roman letters, and digraphs consisting of a suitable punctuation character and an ASCII letter for representing letters with diacritics. A meta-transliteration is required to be uniquely reversible, human readable, and close to the intended transliteration. We present an example of a scheme that has been in use for several years to transliterate texts in Arabic, Persian, Urdu, Sindhi, and Biblical Hebrew.Item Open Access Endbericht der Projektgruppe Fahrgemeinschaften(1998) Heid, Herbert; Nicklas, Daniela; Porrmann, Alexander; Schäffer, Thomas; Scholz, VolkerDas Studium der Informatik vermittelt dem Studierenden zwar einen grossen Teil des noetigen Fachwissens, jedoch stellt das Berufsleben noch weitere Anforderungen an Informatikerinnen und Informatiker. Teamfaehigkeit und Erfahrung spielen gerade bei der Mitarbeit an grossen Software-Projekten eine wichtige Rolle. Hier verfolgt die Idee der Projektgruppe folgende Ausbildungsziele: - Arbeiten im Team - Analyse von Problemen, Strukturierung von Loesungen und gemeinsamer Entwurf geeigneter Systeme - Selbstaendige Erarbeitung von Loeosungsvorschlaagen und deren Vorstellung und Verteidigung in einer Gruppe -Uebernahme von Verantwortung fuer die Loesung von Teilaufgaben und die Erstellung von Modulen - Mitwirkung an einer umfassenden Dokumentation - Erstellen eines Software-Produktes, das ein Einzelner innerhalb des vorgegebenen Zeitraumes unmoeglich bewaeltigen kann - Projekt-Planung und Kosten/Nutzen-Analyse - Einsatz von Werkzeugen – Persoenlichkeitsbildung (Uebernahme von Verantwortung, Selbstvertrauen, Verlaesslichkeit, Ruecksichtnahme, Durchsetzungsfaehigkeit usw.) Als wir Studenten uns im September 1996 zur ersten Vorbesprechung der Projektgruppe Fahrgemeinschaften trafen, wusste noch keiner von uns, was genau auf ihn zukommen wuerde. Gemein war uns das Interesse, in einer groesseren Gruppe (einem Team) an einem Thema zu arbeiten. Eine Moeglichkeit, die das Studium der Informatik an der Universitaet Stuttgart sonst nicht bietet. Die einzigen Lehrveranstaltungen, bei denen eine Zusammenarbeit mehrerer Studenten vorgesehen ist, naemlich Software-Praktikum und Fachpraktikum, haben eine Gruppengroesse von zwei, maximal drei Studenten. Dieser Bericht ist nicht nur die Dokumentation der nach einem Jahr Projektarbeit erzielten Ergebnisse, sondern schildert das Vorgehen der Projektgruppe Fahrgemeinschaften ueber verschiedene Zwischenergebnisse bis zum endgueltigen Produkt MOBI (Mobil durch intelligentes computerunterstuetztes Kombinieren).Item Open Access Zwischenbericht der Projektgruppe Transportoptimierung(1998) Fleischmann, Jörg; Hermes, Lars; Spribille, Tobias; Wagner, FrankIm vorliegenden Zwischenbericht der Projektgruppe 'Transportoptimierung' wird die Entwicklung des Projekts von der Anforderungsanalyse bis zum Entwurf dokumentiert. Im Rahmen der Projektgruppe soll das Programm TROSS (TRansport-Optimierung für Soziale Serviceanbieter) zur Verwaltung und Optimierung von sozialen Fahrdiensten entwickelt werden, das dann beim DRK in Stuttgart eingesetzt wird. Das Programm soll alle für das DRK in Zusammenhang mit seinen Fahrdiensten wichtigen Daten erfassen und verwalten. Die momentan manuell durchgeführte Planung soll in Zukunft computergestützt ablaufen können, was den Planern beim DRK einen besseren Überblick über die Dienste und Einsatz von Mitarbeitern und Fahrzeugen liefern soll. Außerdem ist vorgesehen, die Optimierung von Fahrdiensten auch automatisch auszuführen, um aufwendige Handarbeit einzusparen oder gar bessere Ergebnisse zu bekommen.Item Open Access Abschlußbericht der Projektgruppe Evolutionäre Algorithmen(1997) Großmann, Matthias; Leonhardi, Alexander; Schmidt, ThomasViele in der Praxis interessante Optimierungsrobleme sind NP-hart. Da kein Algorithmus bekannt ist, der ein Optimum für solche Probleme mit geringerem als exponentiellem Aufwand findet, sucht man, ein Optimum mit Heuristiken möglicht gut anzunähern. Zu diesen gehören auch die Evolutionären Algorithmen. Ziel der Projektgruppe EVA war die Entwicklung einer Experimentierplattform für Evolutionäre Algorithmen, die die Implementierung und empirische Untersuchung dieser Algorithmen erleichtert. Besonderer Wert wurde daher auf möglichst große Unabhängigkeit der Algorithmen vom Problem gelegt. Der Endbericht der Projektgruppe enthält nach einer Einführung den Entwurf von GENOM, die Beschreibung der Implementierung sowie Hinweise zur Bedienung und zu Erweiterungsmöglichkeiten.Item Open Access Complexity results for confluence problems(1999) Lohrey, MarkusWe study the complexity of the confluence problem for restricted kinds of semi-Thue systems, vector replacement systems and general trace rewriting systems. We prove that confluence for length-reducing semi-Thue systems is P-complete and that this complexity reduces to AC 1 in the monadic case (where all right-hand sides consist of at most one symbol). For length-reducing vector replacement systems we prove that the confluence problem is PSPACE-complete and that the complexity reduces to NP and P, respectively, for monadic vector replacement systems and special vector replacement systems (where all right-hand sides are empty), respectively. Finally we prove that for special trace rewriting systems, confluence can be decided in polynomial time and that the extended word problem for special trace rewriting systems is undecidable.