Logische Definierbarkeit von NP-Optimierungsproblemen
Laufzeit: 01.01.1991 - 31.12.1992
Kurzfassung
Fagins Charakterisierung von NP als Klasse der Mengen endlicher Modelle von sum-Sätzen läßt sich übertragen auf NP-Optimierungsprobleme. Damit ergibt sich auch hier eine Feinstruktur durch syntaktische Einschränkungen. Ziel des Projekts war es, nachzuweisen, daß Einschränkungen an die Stelligkeit der quantifizierten Prädikate nicht mehr alle NP-Optimierungsmodelle darzustellen gestatten.
Veröffentlichungen
- Lautemann, Clemens; Schwentick, Thomas; Thérien, Denis
- Logics For Context-Free Languages
- Habel, A.; Kreowski, H.-J.; Lautemann, C.
- A comparison of compatible, finite, and inductive graph properties
- Hertrampf, Ulrich; Lautemann, Clemens
- On the power of polynomial bit-reductions
- Drewes, Frank; Lautemann, Clemens
- Incremental termination proofs and the lenght of derivations
- Lautemann, Clemens
- Tree automata, tree decomposition and hyperedge replacement
- Buntrock, Gerhard; Lautemann, Clemens
- Some modifications of auxiliary pushdown automata
