The complexity of monadic recursion schemes: executability problems, nesting depth, and applications (Q792758)

Die Arbeit befaßt sich mit der Komplexität des executability- Problems von Rekursionsschemata. Die erforderlichen Definitionen des ''monadic recursion scheme'' einschließlich der Interpretation, bzw. der Herbrand-Interpretation, der ''configuration'' und ''computation'' finden sich im zweiten Abschnitt ebenso wie eine Zusammenstellung von damit zusammenhängenden Entscheidungsproblemen (executability, totality, divergence, computational identity (weak/strong) equivalence (weak/strong), isomorphic). Im dritten Abschnitt werden mögliche Reduktionen solcher Entscheidungsprobleme aufeinander, insbesondere das executability-Problem, behandelt, sofern sie in Polynomzeit möglich sind, und zwar für verschiedene Arten des Rekursionsschemas (allgemein, total, linear). So ist z.B. das executability-Problem auf das non- divergence-Problem zurückführbar. In diesem Abschnitt werden 11 Sätze zur Reduktion der Probleme zusammengestellt. Im vierten Abschnitt werden drei Maße (ND-, EP-, Max-nesting depth) für die Tiefe (nesting depth) eingeführt und worst-case-Betrachtungen angestellt, deren Ergebnisse in Tabelle 1 zusammengestellt sind. Dabei ergeben sich für das allgemeine Schema exponentielle Schranken (EP, Max), für das totale bzw. lineare Schema Polynomschranken. Theorem 4 z.B. sagt aus, daß die ND-nesting depth größer ist als \(2^{cn}\) mit n als Länge des Schemas und \(c>0\), Theorem 11, daß für ein totales Schema die EP-nesting depth größer ist als \(cn^ 2\) mit \(c>0\), in beiden Fällen für unendlich viele n. Im Abschnitt 5 werden die Ergebnisse der Abschnitte 3 und 4 benutzt, um Aussagen über Entscheidungsprobleme zu machen und entsprechende Algorithmen beispielhaft zu entwickeln. In Theorem 5.2. wird angegeben, für welche ''monadic recursion scheme'' (allgemein, linear, total) es ''nondeterministic polynomially time-bounded'' Algorithmen gibt, um die angeführten Entscheidungsprobleme zu lösen, und zwar für 12 Fälle, basierend auf den Komplexitätsüberlegungen.