Universität Stuttgart
Permanent URI for this communityhttps://elib.uni-stuttgart.de/handle/11682/1
Browse
13 results
Search Results
Item Open Access XPASCAL - eine Erweiterung der Sprache Pascal mit exakter Arithmetik(1989) Lagally, KlausXPASCAL ist ein experimentelles Programmsystem zur Unterstützung exakter Berechnungen in arithmetischen Zahlkörpern, das derzeit in der Abteilung Betriebssoftware am Institut für Informatik der Universität Stuttgart entwickelt wird. Bisher haben daran neben dem Verfasser die Studenten G. Neusetzer, U. Schoppe, G. Wahl, Th. Schöbel und S. Robitschko mitgearbeitet. Der vorliegende Bericht soll die derzeitigen Zielvorstellungen und den Stand der Realisierung aufzeigen und zu Kommentaren, Änderungswünschen und Verbesserungsvorschlägen einladen.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 Gleichungen mit regulären Randbedingungen über freien Gruppen(2000) Hagenah, Christian; Diekert, Volker (Prof. Dr.)Wir beweisen, daß das Erfüllbarkeitsproblem für Gleichungen mit regulären Randbedingungen über freien Gruppen PSPACE-vollständig ist. Wir zeigen auch, daß eine minimale Lösung einer solchen Gleichung höchstens eine doppelt exponentielle Länge hat und in 2-DEXPTIME berechnet werden kann. Wir reduzieren zuerst das Problem Gleichungen mit regulären Randbedingungen über einer freien Gruppen zu lösen auf das Problem Gleichungen mit regulären Randbedingungen über freien Monoiden mit einer Anti-Involution zu lösen. Anschließend stellen wir einen Algorithmus vor, der in PSPACE entscheidet, ob diese Gleichungen lösbar sind und einen Algorithmus, der in 2-DEXPTIME eine Lösung berechnet, wenn die Gleichung lösbar ist.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 Hierarchische Graphen zur Wegesuche(2000) Buchholz, Friedhelm; Claus, Volker (Prof. Dr.)In dieser Arbeit wird ein Zwei-Phasenmodell zur effizienten Entfernungsberechnung in gewichteten Graphen untersucht. Bekannte Anwendungsgebiete sind Verkehrsinformationssyteme, VLSI Design, Verteiltes Rechnen und geometrische und parallele Algorithmen. In einer Preprocessing-Phase wird zu einem Graphen ein Hierarchischer Graph (HG) konstruiert, der in der Online-Phase zur Entfernungsberechnung eingesetzt wird. Es werden die Laufzeit (T) der Preprocessing-Phase, die Groesse (S) des HG'en und die Laufzeit (Q) der Online-Phase untersucht. Zwei kontraere Modellierungsansaetze werden vorgestellt: Geeignete Knoten und ein rekursives Separationskonzept. Das Konzept mit Geeigneten Knoten wird auf Levelgraphen verallgemeinert und es wird gezeigt, dass die Berechnung einer minimalen Geeigneten Knotenmenge NP-vollstaendig ist. Die Approximation bzgl. der Groesse der Geeigneten Knotenmenge kann bis auf einen logarithmischen Faktor und bezueglich des Umgebungsabstands bis auf einen konstanten Faktor in polynomieller Laufzeit durchgefuehrt werden. Im Falle von planaren Graphen wird mittels eines erweiterten Separationskonzepts (Ideen von Lingas 1990 und von Didjev 1996 werden kombiniert) gezeigt, dass HG'en von fast linearer Groesse genuegen, um Q in O(n {1.5} log 3 n) zu gewaehrleisten. Dieses Resultat ist modulo logarithmischer Faktoren optimal. Ausserdem wird ein neuer Parameter 'Separatorweite' fuer Graphen eingefuehrt und es wird konstruktiv gezeigt, dass die Separatorweite unabhaengig von der Baumweite ist, aber hoechstens um einen logarithmischen Faktor von der Baumweite abweicht. Am Beispiel wird gezeigt, dass eine logarithmische Abweichung auftreten kann.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 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 ArabTeX : a system for typesetting Arabic; user manual version 3.00(1993) Lagally, KlausArabTeX is a package extending the capabilities of TeX/LaTeX to generate the Arabic writing from an ASCII transliteration for texts in several languages using the Arabic script. It consists of a TeX macro package and an Arabic font in several sizes, presently only available in the Naskhi style. ArabTeX will run with Plain TeX and also with LaTeX. It is compatible with NFSS, NFSS2 and the EDMAC package; other additions to TeX have not been tried. ArabTeX is primarily intended for generating the Arabic writing, but the standard scientific transliteration can also be easily produced. For languages other than Arabic that are customarily written in the Arabic script some limited support is available. ArabTeX defines its own input notation which is both machine, and human, readable, and suited for electronic transmission and Email communication. However, texts in some of the Arabic standard encodings can also be processed. ArabTeX is copyrighted, but free use for scientific, experimental and other strictly private, noncommercial purposes is granted. Offprints of publications using ArabTeX are welcome. Using ArabTeX otherwise requires a license agreement. There is no warranty of any kind, either expressed or implied. The entire risk as to the quality and performance rests with the user.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 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.