LICS-97 Tutorial: Inference Rules and Complexity
This tutorial draws on material in the following sources:
- Inferring Recursive Types by David McAllester, Unpublished, 1996.
- On The Complexity of Set Based Analysis by Nevin Heintze and David McAllester, ICFP, 1997.
- Automatic
Recognition of Tractability in Inference Relations by David McAllester, JACM, vol. 40, no. 2, April, 1993, pages
284-303.
- New Results on Local Inference Relations by Robert Givan and David McAllester,
KR93, pages 403-412.
- Automated Complexity Analysis Based on Ordered Resolution by David Basin and Herald Ganzinger,
LICS-96, pages 456-465.
long version.
- Descriptive Complexity Theory and Programming Language Design.
Slides from a talk given by David McAllester at UMass Amherst in the spring of 1995.
Additional references provided by several
people after the tutorial.