Forschungsschwerpunkt: |
Lehrstuhl für Informatik IV
Institut für Informatik, Am Hubland, 97074 Würzburg Mail: wagner@informatik.uni-wuerzburg.de Url: http://www-info4.informatik.uni-wuerzburg.de/ |
Wissenschaftliche Mitglieder:
Professoren:
Forschungsschwerpunkte (und Projekte auf Basis der Grundausstattung):
Komplexität von Exponentierung von Sprachen
Ergebnisse:
Wir charakterisieren die Exponentierung von Sprachen durch andere Sprachoperationen: Stehen einige "schwache" Operationen zur Verfügung, so ist Exponentierung genauso mächtig wie das Komplement und Epsilon-freie Morphismen. Diese Charakterisierung impliziert unter anderem, dass eine Semi-AFL abgeschlossen unter Komplement ist, genau dann wenn sie abgeschlossen unter Exponentierung ist. Als Anwendung Charakterisieren wir den Exponentierungsabschluss von kontextfreien Sprachen. Weiterhin ist P unter Exponentierung abgeschlossen genau dann wenn P=NP, und NP ist abgeschlossen unter Exponentierung genau dann wenn NP=coNP.