Mostrar que A ≤ PB y B ∈ PSPACE implica A ∈ PSPACE.
Mostrar que si A ≤ LB y B ≤ LC entonces A ≤ LC.
Sipser 8.18: "Let B be the language of properly nested parentheses and brackets. For example, ([()()]()[]) is in B but ([)] is not. Show that B is in L."
Sipser 8.23: "Define UCYCLE == {(G) | G is an undirected graph that contains a simple cycle}. Show that UCYCLE is in L. (Note: G may be a graph that is not connected.)"
Leer en Sipser pp 313-320, las secciones "Winning Strategies for Games" y Generalized Geography. Consideremos el lenguaje uGG, el juego Generalized Geography en grafos no dirigidos (o simétricos). ¿Qué tendríamos que modificar en la demostración del Teorema 8.14 si quisieramos demostrar que uGG es PSPACE-completo?