Path measures of turing machine computations

1. D.A. ALTON, "Natural" complexity measures, subrecursive languages, and speed-up, Computer Science report 76-05, University of Iowa, December 1976.

   Google Scholar 

2. D.A.ALTON, "Natural" complexity measures and time versus memory: some definitional proposals, Fourth Coll. Automata, Languages and Programming, Turku 1977, Lecture Notes in Computer Science 52, 16–29.

   Google Scholar 

3. G. AUSIELLO, Abstract computational complexity and cycling computations, J. Computer and System Sciences, 5 (1971), 118–128.

   Google Scholar 

4. J. BISKUP, Über Projektionsmengen von Komplexitätsmaßen, Elektronische Informationsv. und Kybernetik (EIK), 13 (1977), 359–368.

   Google Scholar 

5. M. BLUM, A machine-independent theory of the complexity of recursive functions, J.Assoc.Comput.Mach., 14 (1967), 322–336.

   Google Scholar 

6. W.S. BRAINERD/L.H. LANDWEBER, Theory of computation, Wiley-Interscience, New York, 1974.

   Google Scholar 

7. R. L. CONSTABLE, Type two computational complexity, Proc.Fifth Ann.ACM Symp. Theory of Computing (1973), 108–121.

   Google Scholar 

8. S. EILENBERG, Automata, languages and machines, vol.A, Academic Press, New York-London, 1974.

   Google Scholar 

9. J. HARTMANIS, On the problem of finding natural computational complexity measures, Proc. Int. Symp. and Summer School Math. Foundations of Computer Science, High Tatra, Sept. 3–8 (1973), 95–103.

   Google Scholar 

10. D.E. KNUTH, The art of computer programming, Vol. 1, Addison-Wesley, Reading (Mass.), 1968, 1973.

    Google Scholar 

11. G. LISCHKE, Flußbildmaße — Ein Versuch zur Definition natürlicher Kompliziert-heitsmaße, Elektronische Informationsv. und Kybernetik (EIK), 11 (1975), 423–436.

    Google Scholar 

12. K. WEIHRAUCH, Über Eigenschaften abstrakter Komplexitätsmaße von Algorithmen, Seminarbericht Nr. 34 der GMD, Birlinghoven, 1971.

    Google Scholar 

Download references