Programmiersprachen und Compiler

(Formale Sprachen und Automatentheorie)

Aktuelle Forschungsprojekte

Beschreibungskomplexität von Grammatiksystemen

Ein Grammatiksystem ist ein verteiltes System bestehend aus mehreren Grammatiken, die auf verschiedene Art und Weise miteinander kooperieren. Die einzelnen Modelle unterscheiden sich hauptsächlich durch die Art der Grammatik, parallele bzw. sequentielle Kooperation und verschiedene Kontrollmechanismen. Ziel des Projekts ist festzustellen, welchen Einfluß das Zulassen mehrerer Komponenten und das Zulassen von Kontrollstrukturen auf die Beschreibungskomplexität von Grammatiksystemen hat. Außerdem wird nach geeigneten Automatenmodellen gesucht, die die von Grammatiksystemen erzeugten Sprachklassen akzeptieren.Über Grammatiksysteme mit sequentieller Kooperation lassen sich vor allen Dingen Aussagen über die minimale Anzahl von Komponenten, Nichtterminalen bzw. Produktionen in einer Komponente treffen, die man zur Erzeugung von bestimmten Sprachklassen braucht. Mit der Betrachtung eingeschränkter Modelle sollen auch genauere Aussagen über den trade-off zwischen den Maßen getroffen werden.

Beschreibungskomplexität von Zellularautomaten

Ein Zellularautomat besteht aus vielen einzelnen identischen deterministischen endlichen Automaten (Zellen), die gleichzeitig gemäß einer gemeinsamen Regel schalten. Diese Regel verarbeitet Informationen der Zelle und einer beschränkten Anzahl von Nachbarzellen. Die von Zellularautomaten akzeptierte Sprachklasse liegt jenseits der kontextfreien Sprachen. In diesem Projekt werden Zellularautomaten hinsichtlich ihrer Beschreibungskomplexität untersucht. Es zeigt sich, daß Zellularautomaten im Vergleich zu anderen Automatenklassen wie endlichen Automaten und Kellerautomaten nichtrekursiv beschränkte Größeneinsparungen liefern können. In dem Projekt wird untersucht, wie sich die Beschränkung bestimmter Parameter auf die Beschreibungskomplexität auswirken kann. Beispielsweise beschränkt man die zur Verfügung stehende Zeit, die Anzahl der Nachbarzellen, die Anzahl der zur Verfügung stehenden Zellen oder die Form der Eingabe.

Effiziente Sprachdarstellungen durch DFA mit verschiedenem Zuverlässigkeitsgrad

Ziel ist es, qualitative Maße für die Zuverlässigkeit von Sprachdarstellungen durch endliche Automaten zu entwickeln und entsprechende Relationen unter diesen Maßen aufzuzeigen. Darüber hinaus untersuchen wir die Tradeoffs, die zwischen den unterschiedlichen Maßen bestehen. Wir können zeigen, daß die Einsparungen bezüglich der Anzahl der Zustände zwischen Darstellungen, die verschiedenen qualitativen Kriterien genügen, durch keine Funktion beschränkt werden. Diese Ergebnisse sind für jeden beliebigen vorgegeben quantitativen Zuverlässigkeitsgrad gültig.

Komplexität von Systemverifikationen

Wir betrachten Spezifikationen von Systemen, die speziellen Korrektheitsanforderungen genügen sollen. Bei der Verifikation solcher Systeme suchen wir nach Fehlern, die verhindern, daß das betrachtete System korrekt gemäß den speziellen Anforderungen ist. Ein großes Problem beim Einsatz automatisierter Verifikationstechniken liegt in der Komplexität der zur Verfügung stehenden Verifikationsalgorithmen. Im Rahmen dieses Projektes werden Klassen von Systemeigenschaften untersucht, für die eine effiziente automatisierte Verifikation realisierbar ist.

Mehrdeutigkeit und Nichtdeterminismus bei Büchi Automaten

Nichtdeterminismus und Mehrdeutigkeit eines Automaten können als konsumierbare Resourcen interpretiert werden. Für endliche Automaten wurde dieser Ansatz bereits von Goldstine, Kintala und Wotschke verfolgt. Ziel des Projektes ist es, entsprechende Untersuchungen auch für Büchi Automaten durchzuführen. Wir klassifizieren die Automaten gemäß dem Grad an Mehrdeutigeit bzw. Nichtdeterminismus, der notwendig ist um bestimmte reguläre omega-Sprachen zu akzeptieren. Es ist bekannt, daß die deterministischen regulären omega-Sprachen eine echte Teilmenge der regulären omega-Sprachen bilden. Wir wollen daher die kleinste "Menge" an Nichtdeterminismus und Mehrdeutigkeit bestimmen, die zur Akzeptanz einer nichtdeterministischen regulären omega-Sprache nötig ist. Zusätzlich sollen mögliche Abhängigkeiten zwischen den beiden Maßen offengelegt werden.

Minimierung von endlichen Automaten

Das Minimierungsproblem eines endlichen Automaten besteht darin, zu einem gegebenen Automaten einen äquivalenten Automaten mit einer minimalen Anzahl von Zuständen algorithmisch zu konstruieren. Das Problem ist für deterministische endliche Automaten in polynomieller Zeit lösbar. Für nichtdeterministische endliche Automaten ist das Problem PSPACE-vollständig. Für eindeutige, nichtdeterministische endliche Automaten ist das Problem NP-vollständig. In diesem Projekt wird untersucht, wie sich die Berechnungskomplexität des Minimierungsproblems verhält, wenn der Grad des Nichtdeterminismus im zugrundeliegenden Automaten beschränkt wird. Es zeigt sich, daß bereits ein beliebiger, aber fest vorgegebener konstanter Nichtdeterminismusgrad ausreicht, um das Minimierungsproblem NP-vollständig zu machen. In einer weiteren Einschränkung werden deterministische Automaten mit einer festen Anzahl von Startzuständen betrachtet. Auch hier erweist sich das Minimierungsproblem als NP-vollständig. Im weiteren Verlauf des Projekts soll die Berechnungskomplexität des Minimierungsproblems für eindeutige, nichtdeterministische endliche Automaten mit einem fixen, konstanten Nichtdeterminismusgrad untersucht werden. Weiterhin sollen strukturelle Anforderungen an endliche Automaten formuliert werden, die ein effizientes Minimieren ermöglichen. Projektleitung: Prof. Dr. Detlef Wotschke Beteiligte: Andreas Malcher Stichwörter: Endliche Automaten, Minimierung, Berechnungskomplexität Laufzeit: 1.9.2002 - 31.8.2004 Mitwirkende Institutionen: New Mexico State University, Las Cruces, New Mexico, USA

Alternative Grammatikmodelle für natüliche Sprachen

Die bisherigen Grammatiken für natürliche Sprachen sind aufgrund von zu großer oder kleiner generativer Kapazität oder anderer fehlender Eigenschaften nur eingeschränkt in der Lage, natürliche Sprachen zu beschreiben. Ziel des Projekts ist es, ein alternatives formales Grammatikmodell für natürliche Sprache zu finden. Ein solches Modell könnte neben der prinzipiellen Einsicht in den Aufbau der natürlichen Sprache auch Anwendung in der computergestützten Übersetzung, dem Entwurf neuer natürlicher Programmiersprachen etc. Anwendung finden.

Beschreibungskomplexität und zuverlässige Software

Es soll ein wissenschaftliches Fundament für die Verbindung zwischen Beschreibungskomplexität und Zuverlässigkeit von Software geschaffen werden. Dazu soll die Beschreibungskomplexität an theoretischen Modellen untersucht werden, die einen starken konzeptionellen Bezug zu Software haben, also an verschiedenen Modellen von endlichen Automaten, Kellerautomaten, kontextfreien Sprachen usw. Bei der Auswahl der entsprechenden Modelle und Fragen werden weitgehend Erfahrungen aus dem praktischen Bereich berücksichtigt.

Beschreibungskomplexität von endlichen Automaten mit mehreren Startzuständen

Ziel des Projekts war es, festzustellen, welchen Einfluß das Zulassen mehrerer Startzustände in endlichen Automaten hinsichtlich der Beschreibungskomplexität hat. Dabei wurde im Rahmen eines mathematisch-formalen Modells bewiesen, daß sich bei deterministischen endlichen Automaten durch das Zulassen mehrerer Startzustände exponentielle Größeneinsparungen ergeben können und durch eine einfache Veränderung des Akzeptierungsbegriffs exponentielle Einsparungen gegenüber nichtdeterministischen endlichen Automaten möglich sind. Endliche Automaten besitzen in der Informatik vielfältige Anwendungsgebiete, und die hier untersuchten Automaten sind leicht zu implementieren. Daher sind die bewiesenen Größeneinsparungen in der Praxis, etwa bei Schaltkreisentwurf, Compilerbau oder Kommunikationsprotokollen, direkt umsetzbar.

Dynamische Konfliktbeseitigung in deterministischen "Top Down"-Parsern

LL(k)-Grammatiken stellen ein allgemein anerkanntes Modell zur Beschreibung der Syntax von Programmiersprachen dar. Ihre generative Mächtigkeit reicht allerdings für die in der Praxis benutzten Sprachen selten aus. Die in der Vergangenheit vorgeschlagenen Methoden zur Erweiterung dieser Grammatikklasse sind aus theoretischer Sicht weitgehend unerforscht bzw. nicht handhabbar. Im Verlauf dieses Projekts wird die Frage untersucht, inwieweit sich diese Schwächen durch das Konzept der dynamischen Konfliktauflösung beheben lassen. Theoretische Untermauerung von im Compilerbau seit längerem mit Erfolg eingesetzten Verfahren.

Kellerautomaten und Aspekte ihrer Beschreibungskomplexität

Es wird untersucht, um wieviel die Anzahl der Zustände vergrößert werden muß, wenn man die Anzahl der Kellersymbole reduzieren möchte. Dabei werden eine deterministische sowie eine nichtdeterministische Simulation untersucht. Kellerautomaten und Fragen nach ihrer Beschreibungskomplexität tauchen in vielen Anwendungsbereichen der Informatik auf, z. B. Syntaxanalyse.

Lookahead-Spektren von LL(k)-Grammatiken und Beschreibungskomplexität

In Abhängigkeit von dem Lookahead muß sich in vielen Fällen die Größe der entsprechenden LL(k)-Grammatiken verändern. LL(k)-Grammatiken sind eine der am häufigsten verwendeten Beschreibungsformen von Programmiersprachen. Die Relation zwischen Lookahead und Größe der Grammatik spielt eine wichtige Rolle beim Entwurf solcher Grammatiken.

Maße für den Nichtdeterminismus bei Pushdown-Automaten

Es wird untersucht, welche Wachstumsraten der Nichtdeterminismus bei Pushdown-Automaten annehmen kann und in manchen Fällen annehmen muß. Pushdown-Automaten und Kenntnisse über die Wachstumsrate ihres Nichtdeterminismus liefern ein besseres Verständnis für den praktischen Entwurf PDA-basierter Systeme.

Nichtdeterminismus und Mehrdeutigkeit in Pushdown-Automaten

Pushdown-Automaten spielen eine wichtige Rolle bei der formalen Spezifikation und dem Parsing von typischen Programmiersprachen. Im Rahmen des Projekts werden Pushdown-Automaten betrachtet, in denen der erlaubte Grad von Nichtdeterminismus und von Mehrdeutigkeit schrittweise bis hin zum vollständigen Verbot beschränkt wird. Es wird dann untersucht, wie sich diese Beschränkung auf die Beschreibungsmächtigkeit und Beschreibungskomplexität und auf die Komplexität von bekannten Parsing- Algorithmen auswirkt. Neben grundlegenden Erkenntnissen über die Rolle des Nichtdeterminismus in der Theorie der formalen Sprachen wurde gezeigt, daß für bestimmte Klassen von Sprachen mit beschränktem Nichtdeterminismus oder beschränkter Mehrdeutigkeit effizientere Parsing-Algorithmen existieren als bisher bekannt.

Stochastische Endliche Automaten und ihre Beschreibungskomplexität

Es werden die Einsparungen in der Beschreibungskomplexität untersucht, die bei der Beschreibung regulärer Sprachen durch die Verwendung nichtdeterministischer und stochastischer Automaten erzielt werden können. Reguläre Sprachen bzw. Reguläre Ausdrücke tauchen in fast allen Anwendungsbereichen der Informatik auf, z. B. Compiler-Bau, Chip-Entwurf.

Verzögerung der Fehlererkennung bei Parsern und Beschreibungskomplexität

In Abhängigkeit von der zeitlichen Verzögerung bei der Fehlererkennung kann für die Beschreibungskomplexität der entsprechenden Parser eine unendliche Hierarchie existieren. Die Frage der verzögerten Fehlererkennung steht in enger Beziehung zu der Größe von Compilern.

geändert am 27. Oktober 2007  E-Mail: Webmasterwaschbue@em.uni-frankfurt.de