Die Zeitkomplexität des Normalisierungsproblems bei kontextsensitiven Grammatiken
Tóm tắt
Sei G eine kontextsensitive Grammatik. Gc∫ bezeichne den kontextfreien Kern von G. In dieser Arbeit wird die Zeitkomplexität des folgenden Problems untersucht. Das Normalisierungsproblem Sei τ ein Ableitungsbaum bezüglich Gc∫; ist τ auch ein Ableitungsbaum bezüglich G? Es wird gezeigt, daß im allgemeinen das Normalisierungs-problem NP-vollständig ist. Andererseits gibt es zu jeder kontextsensitiven Sprache L eine kontextsensitive Grammatik G, für welche das Normalisierungsproblem in Polynomzeit lösbar ist.
Tài liệu tham khảo
Aho, A.V., Hopcroft, E.H., Ullman, J.D.: The design and analysis of computer algorithms. Reading (Mass.): Addison-Wesley 1974
Hotz, G., Claus, V.: Automatentheorie und formale Sprachen. III. Formale Sprachen. Mannheim: BI 1972
Hopcroft, E.H., Ullman, J.D.: Formal languages and their relation to automata. Reading (Mass.): Addison-Wesley 1969
Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of computer computations (R.E. Miller, J.W. Thatcher, eds.). New York: Plenum Press 1972
Penttonen, M.: One-sided and two-sided context in formal grammars. Information and Control 25, 371–392 (1974)
Stadel, M.: Das Normalisierungsproblem und der Zusammenhang mit der Zeitkomplexität der kontextsensitiven Analyse. Dissertation, Saarbrücken, 1976