1. R.S. Bird, G. Jones and O. de Moor. More Haste, Less Speed: Lazy vs Eager Evaluation, Journal of Functional Programming, to appear.
   
   
2. J. Royer, Semantics vs. syntax vs. computations: Machine models for type-2 polynomial-time bounded functionals, J. Comput. and Syst. Science, to appear.
   
   
3. N. D. Jones, Logspace and Ptime Characterized by Programming Languages, Theoretical Computer Science, Elsevier Science B.V. (1998) to appear.
   Note: Logspace = the sets decided by read-only imperative programs, Ptime = the sets decided by read-only recursive programs.
   
   
4. O. de Moor, A generic program for sequential decision processes. In: Hermenegildo, M. and Swierstra, D.S., editors, Programming Languages: Implementations, Logics and Programs, LNCS 982, (1995)1-23
   
   
5. N. D. Jones, Program Speedups in Theory and Practice, IFIP Transactions Technology and Foundations Information Processing '94, Elsevier Science B.V. (1994) 595-602.
   
   
6. N. Andersen and N.D. Jones, Improving Cook's transformation of imperative stack programs, Results and Trends in Theoretical Computer Science Springer LNCS 812 (1994) 1-18.
   Note: Cook's 2DPDA result expressed and generalized in terms of imperative stack programs.
   
   
7. N. D. Jones, Constant time factors do matter, STOC '93. Symposium on Theory of Computing (1993) 602--611.
   Note: Linear time possesses a proper hierarchy based on constant factors, for a language with structured programs and structired data.
   
   
8. R.S. Bird and O. de Moor. Solving optimisation problems with catamorphisms. In R.S. Bird, C.C. Morgan and J.C.P. Woodcock, Mathematics of Program Construction, LNCS 669, (1993) 45-66.
   
   
9. N. D. Jones, Computer implementation and applications of Kleene's s-m-n and recursion theorems, Logic From Computer Science, Springer-Verlag Lecture Notes in Mathematics, (1991) 243-264.
   
   
10. N. D. Jones, Efficient algebraic operations on programs, Machine models for type-2 polynomial-time bounded functionals, AMAST Proceedings, Springer-Verlag Workshops, (1991).
    Note: Investigates symbolic operations (e.g. deforestation = symbolic function composition), and the types of operations on program texts.
    
    
11. N. D. Jones and S. Muchnick, Complexity of flow analysis, inductive assertion synthesis, and a language due to Dijkstra, 21st FOCS Symp. (Found. Comp. Sci.), IEEE vol (1980) 185--190.
    
    
12. N. D. Jones and S. Muchnick, Even simple programs are hard to analyze, Journal of the ACM 24 (1977) 338--350.
    Note: Upper and lower bounds close to linear space for analyzing nonrecursive programs on finite data domains.
    
    
13. N. D. Jones and S. Muchnick, Complexity of finite memory programs with recursion, Journal of the ACM 25 (1978) 312--321.
    Note: Similar, for recursive programs with various parameter passing mechanisms (EXPTIME for many, undecidable for Algol-style call-by-name).
    
    
14. N. D. Jones and A.L. Selman, Turing machines and the spectra of first order formula with equality, Journal of Symbolic Logic 39 (1974) 139--150.
    Note: A set is a spectrum if and only if it is accepted by a nondeterministic exponential-time Turing machine.
    
    

Books by the organizers

1. R. S. Bird and O. de Moor, Algebra of Programming, Prentice Hall, (1996).
   
   
2. N. Jones, Computability and Complexity from a Programming Perspective, MIT Press, (1997) 466 pages.
   Note: Computability and Complexity redone using a language with structured programs and structired data.
   
   
3. N. Jones, C. Gomard, P. Sestoft, Partial Evaluation and Automatic Program Generation, Prentice Hall, (1993) 415 pages.
   Note: Partial Evaluation = practical applications of the Kleene s-m-n theorem.
   
   
4. J. Royer and J. Case, Subrecursive Programming Systems: Complexity & Succinctness, Birkhauser, (1994).
   
   
5. J. Royer, A Connotational Theory of Program Structure, Springer LNCS 273 (1987) 186 pages.

1. S. Bellantoni and S. Cook, A new recursion-theoretic characterization of the polytime functions, Computational Complexity 2 (1992) 97-110.
   
   
2. Bloom, B. and Paige, R., Transformational Design and Implementation Of A New Efficient Solution To The Ready Simulation Problem, Science of Computer Programming 24(3) (1995) 189-220.
   
   
3. R. Constable, Type two computational complexity, in Proc. of the Fifth Ann. ACM Symp. on Theory of Computing (1973) 108-121.
   Note: This seems to be the first paper to consider the question of the computational complexity of functionals and operators (as opposed to using functionals and operators as tools).
   
   
4. S. Cook and B. Kapron, Characterizations of the basic feasible functions of finite type, in Feasible Mathematics: A Mathematical Sciences Institute Workshop, (S. Buss and P. Scott, eds.), Birkhauser (1990) 71-95.
   
   
5. S. Cook, Computability and complexity of higher type functions, in Logic from Computer Science (Y.N. Moschovakis, ed.), Springer-Verlag (1991) 51-72.
   Note: A useful survey of higher-type computing and complexity.
   
   
6. S. Cook and A. Urquhart, Functional Interpretations of Feasibly Constructive Arithmetic, Annals of Pure and Applied Logic 63 (1993) 103-200.
   
   
7. S. Debray, R. Muth, On the Complexity of Function Pointer May-Alias Analysis, Proc. Seventh International Joint Conference on Theory and Practice of Sofware Development (TAPSOFT), Springer LNCS 63 (1997) 381-392.
   
   
8. S. Debray, On the Complexity of Dataflow Analysis of Logic Programs, ACM Transactions on Programming Languages and Systems 17 no. 2 (1995) 331-365.
   
   
9. R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, SIAM-AMS Proceedings 7 (1974) 43-74.
   
   
10. R. Gandy and J. Hyland, Computable and recursively countable functions of higher type, in Logic Colloquium 76, North-Holland, (1977) 407-438.
    Note: A useful survey on higher-type computability.
    
    
11. J.-Y. Girard and A. Scedrov and P.J. Scott, Bounded Linear Logic: A Modular Approach to Polynomial Time Computability, Theoretical Computer Science 97 (1992) 1-66.
    
    
12. J.-Y. Girard, Light Linear Logic, Manuscript, 1996.
    
    
13. Goyal, D. and Paige, R., The Formal Reconstruction and Improvement Of The Linear Time Fragment Of Willard's Relational Calculus Subse, Proc. IFIP TC2 Working Conf. on Algorithmic Languages and Calculi (1997) 189-220.
    
    
14. D. Gurr, Semantic Frameworks for Complexity, Ph.D. Thesis, University of Edinburgh, 1990.
    
    
15. Y. Gurevich, Algebras of feasible functions, Foundations of Computer Science, IEEE Press, (1983) 210-214.
    
    
16. G. Hillebrand, On the expressive power of simply typed and let-polymorphic lambda calculi, Logic in Computer Science, IEEE Press, (1996) 253-263.
    
    
17. Immerman, N., Languages that capture complexity classes, SIAM Journal on Computing 16 no. 4 (1987) 760-778.
    
    
18. B. Kapron and S. Cook, A new characterization of type 2 feasibility, SIAM Journal on Computing 25 (1996) 117-132.
    Note: This contains the machine characterization of the type-2 Basic Feasible Functionals.
    
    
19. B. Kapron, Feasible Functionals and Reducibilities, in Logical Methods in Mathematics and Computer Science: A Symposium in Honor of Anil Nerode on the Occasion of His Sixtieth Birthday, Workshop on Feasible Mathematics, Birkaueser (1993) 154-159.
    
    
20. B. Kapron, Feasible Computation in Higher Types, Ph.D. Thesis, Department of Computer Science, University of Toronto, 1991.
    
    
21. D. Leivant, Ramified Recurrence and Computational Complexity I: Word Recurrence and Poly-time, in Feasible Mathematics II, (P. Clote and J. Remmel, eds.) Birkhauser (1995) 320-343.
    
    
22. D. Leivant, Predicative Recurrence in Finite Types, Lecture Notes in Computer Science, 813 (1994) 227-239.
    
    
23. J. L. Lawall and H. Mairson, Optimality and inefficiency: what isn't a cost model of the lambda calculus? ICFP'96 International Conference on Functional Programming 103 (1996) 92--101.
    
    
24. K. Mehlhorn, Polynomial and Abstract Subrecursive Classes, Journal of Computer and Systems Sciences 12 (1976) 147-178.
    Note: This was a follow up of some of the questions posed by the 1973 Constable paper.
    
    
25. C. Okasaki, Catenable double-ended queues, International Conference on Functional Programming, ACM Press (1997) ??-??.
    
    
26. Paige, R., Real-Time Simulation of A Set Machine on a RAM, ICCI 89, in Computing and Information, eds. R. Janicki and W. Koczkodaj, Canadian Scholars Press Vol. II (1989) 69-73.
    Note: All of the above available on http://cs.nyu.edu/cs/faculty/paige/research.html
    
    
27. N. Pippenger, Pure versus Impure Lisp Principles of Programming Languages (1996) 104-109.
    
    
28. H. Schwichtenberg, Functions definable in the simply-typed lambda calculus, Arch. Math Logik 17 (1976) 113-114.
    
    
29. D. Sands, Proving the Correctness of Recursion-Based Automatic Program Transformations. Sixth International Joint Conference on Theory and Practice of Software Development (TAPSOFT) ( P Mosses, M Nielsen, and M Schwartzbach, eds.), 915 Lecture Notes in Computer Science, Springer-Verlag (1995) 681-695.
    Note: This paper shows how the Improvement Theorem--a semantic condition for the total correctness of program transformation on higher-order functional programs--has practical value in proving the correctness of automatic techniques, including deforestation and supercompilation.
    
    
30. D. Sands. Total Correctness by Local Improvement in Program Transformation. Proceedings of the 22nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL),ACM Press. (1995) 221-232.
    Note: This paper presents a condition for the total correctness of transformations on recursive programs which deals with higher-order functional languages (both strict and non-strict) including lazy data structures.
    
    
31. H. Schwichtenberg, Density and choice for total continuous functionals, in Kreiseliana (P. Odifreddi, ed.), A.K. Peters (1996) 335-362.
    
    
32. H. Schwichtenberg, Type Theory, lecture notes from a course given at UniversitSt MÙnchen, 1994.
    
    
33. A. Seth, There is No Recursive Axiomatization for Feasible Functionals of Type 2, Seventh Annual IEEE Symposium on Logic in Computer Science (1992) 286-295.
    
    
34. A. Seth, Some Desirable Conditions for Feasible Functions of Type 2, Eighth Annual IEEE Symposium on Logic in Computer Science (1993) 320-331.
    
    
35. A. Seth, Turing Machine Characterizations of Feasible Functionals of All Finite Types, in Feasible Mathematics II, Birkhauser (1995) 407-428.
    Note: This contains an extension of the Kapron-Cook type-2 machine characterization to all simple types.
    
    
36. A. Seth, Complexity Theory of Higher Type Functionals, Ph.D. Thesis, University of Bombay, 1994.
    Note: This contains the matterial of the previous three papers and more.
    
    
37. Suciu, D. and Tannen, V., A Query language for NC, ACM Symposium on Principles of Database Systems 13 (1994) 167-178.
    
    
38. M. Townsend, Complexity for Type-2 Relations, Nortre Dame Journal of Formal Logic 31 (1990) 241-262.
    
    
39. Jerzy Tiuryn, Higher-order arrays and stacks in programming. An application of complexity theory to logics of programs, Mathematical Foundations of Computer science, Gruska, J. (et al.), editors LNCS 233 (1986) 177-198.
    
    
40. T. Yamakami, Feasible Computability and Resource Bounded Topology, Information and Computation 116 (1995) 214-230.
    
    

Also of Interest

• DIMACS Workshop on Computational Complexity and Programming Languages, 1996. See the Workshop Report.

• B. Pehrson and I. Simon, editors, Information Processing '94 Volume 1, Information Based Complexity and Program Speedups in Theory and Practice, miniworkshop (1994). 579-628

• B. Kapron, H. Mairson editors, Special Issue on Functional Programming and Computational Complexity, Journal of Functional Programming, Cambridge University Press (expected 1998).

To the Home page for Dagstuhl meeting 9823:
Programs: Improvements, Complexity, and Meanings

To the Home page for Schloß Dagstuhl