Erol, K., Hendler, J. A., & Nau, D. S. (1996). Complexity results for hierarchical task-network planning. *Annals of Mathematics and Artificial Intelligence*, 18, 69–93.

Fikes, R. E., & Nilsson, N. (1971). STRIPS: A new approach to the application of theorem proving to problem solving. *Artificial Intelligence,* 2, 189–208.

Furst, M., Saxe, J. B., & Sipser, M. (1984). Parity, circuits, and the polynomial-time hierarchy.

Mathematical Systems Theory, 17(1), 13–27.

Garey, M. R., & Johnson, D. S. (1979). *Computers and Intractability—A Guide to the Theory of* NP-Completeness. Freeman, San Francisco, CA.

Gazen, B. C., & Knoblock, C. (1997). Combining the expressiveness of UCPOP with the efficiency of Graphplan. In Steel, S., & Alami, R. (Eds.), *Recent Advances in AI Planning. 4th European* Conference on Planning (ECP'97), Vol. 1348 of *Lecture Notes in Artificial Intelligence*, pp.

221–233 Toulouse, France. Springer-Verlag.

Gogic, G., Kautz, H. A., Papadimitriou, C. H., & Selman, B. (1995). The comparative linguistics of knowledge representation. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI-95), pp. 862–869 Montreal, Canada. Morgan Kaufmann.

Kambhampati, S., Parker, E., & Lambrecht, E. (1997). Understanding and extending Graphplan.

In Steel, S., & Alami, R. (Eds.), Recent Advances in AI Planning. 4th European Conference on Planning (ECP'97), Vol. 1348 of *Lecture Notes in Artificial Intelligence*, pp. 260–272 Toulouse, France. Springer-Verlag.

Karp, R. M., & Lipton, R. J. (1982). Turing machines that take advice. L' Ensignement Mathematique ´ , 28, 191–210.

Kautz, H. A., McAllester, D. A., & Selman, B. (1996). Encoding plans in propositional logic. In Aiello, L. C., Doyle, J., & Shapiro, S. (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the 5th International Conference (KR-96), pp. 374–385 Cambridge, MA. Morgan Kaufmann.

Kautz, H. A., & Selman, B. (1992). Forming concepts for fast inference.. In *Proceedings of the* 10th National Conference of the American Association for Artificial Intelligence (AAAI-92),
pp. 786–793 San Jose, CA. MIT Press.

Kautz, H. A., & Selman, B. (1996). Pushing the envelope: Planning, propositional logic, and stochastic search. In Proceedings of the 13th National Conference of the American *Association for Artificial Intelligence (AAAI-96)*, pp. 1194–1201. MIT Press.

Kautz, H. A., & Selman, B. (1998). BLACKBOX: A new approach to the application of theorem proving to problem solving. In Working notes of the AIPS'98 Workshop on Planning as Combinatorial Search Pittsburgh, PA.

Koehler, J., Nebel, B., Hoffmann, J., & Dimopoulos, Y. (1997). Extending planning graphs to an ADL subset. In Steel, S., & Alami, R. (Eds.), *Recent Advances in AI Planning. 4th European* Conference on Planning (ECP'97), Vol. 1348 of *Lecture Notes in Artificial Intelligence*, pp. 273–285 Toulouse, France. Springer-Verlag.