
## References

B¨ackstr¨om, C., & Klein, I. (1991a). Parallel non-binary planning in polynomial time. In Proceedings of Twelfth International Joint Conference on Artificial Intelligence**, pp.** 268–273, Sydney, Australia. Morgan Kaufmann Publishers.

B¨ackstr¨om, C., & Klein, I. (1991b). Planning in polynomial time: The SAS-PUBS class.

Computational Intelligence, 7**(3), 181–197.**
B¨ackstr¨om, C., & Nebel, B. (1995). Complexity results for SAS+ planning. **Computational**
Intelligence, 11**(4), 625–655.**
Boutilier, C., Brafman, R., Hoos, H., & Poole, D. (1999). Reasoning with conditional **ceteris**
paribus preference statements. In **Proceedings of the Fifteenth Annual Conference on**
Uncertainty in Artificial Intelligence**, pp. 71–80. Morgan Kaufmann Publishers.**
Bylander, T. (1992). Complexity results for serial decomposability. In **Proceedings of the**
Tenth National Conference on Artificial Intelligence**, pp. 729–734, San Jose, CL. AAAI**
Press.

Bylander, T. (1994). The computational complexity of propositional STRIPS planning.

Artificial Intelligence, 69**(1-2), 165–204.**
Chalasani, P., Etzioni, O., & Mount, J. (1991). Integrating **efficient model-learning and**
problem-solving algorithms in permutation environments. In **Proceedings of the Second** International Conference on Principles of Knowledge Representation and Reasoning, pp. 89–98, Cambridge, MA. Morgan Kaufmann Publishers.

Chapman, D. (1987). Planning for conjunctive goals. Artificial Intelligence, 32**(3), 333–377.**
Domshlak, C., & Dinitz, Y. (2001). Multi-agent off-line coordination: Structure and complexity. In Proceedings of Sixth European Conference on Planning**, Toledo, Spain.**
Domshlak, C., & Shimony, S. E. (2003). Efficient probabilistic reasoning in Bayes nets with mutual exclusion and context specific independence. In Proceedings of the Sixteenth International FLAIRS Conference, Special Track on Uncertain Reasoning**, St.**
Augustine, FL. AAAI Press. to appear.

Erol, K., Nau, D. S., & Subrahmanian, V. S. (1995). Complexity, decidability and undecidability results for domain-independent planning. **Artificial Intelligence, Special Issue**
on Planning, 76**(1–2), 75–88.**
Etzioni, O. (1993). Acquiring search-control knowledge via static analysis. Artificial Intelligence, 62**(2), 255–301.**
Jonsson, P., & B¨ackstr¨om, C. (1998a). State-variable planning under structural restrictions:
Algorithms and complexity. Artificial Intelligence, 100**(1–2), 125–176.**
Jonsson, P., & B¨ackstr¨om, C. (1998b). Tractable plan existence does not imply tractable plan generation. Annals of Mathematics and Artificial Intelligence, 22**(3-4), 281–296.**
Kambhampati, S. (1995). Admissible pruning strategies based on plan minimality for planspace planning. In **Proceedings of the Fourteenth International Joint Conference on**
Artificial Intelligence**, pp. 1627–1635, Montreal, Canada.**