Comparison of the active visiting and the crossing complexities

1. Barzdin J., Complexity of recognition of symmetry by Turing machines (in Russian). In Problemy kibernetiki, vol. 15 (1965), 245–248.

   Google Scholar 

2. Brandstädt A. and Saalfeld D., Eine Hierarchie beschränkter Rückkehrberechnungen auf on-line Turingmachinen, preprint.

   Google Scholar 

3. Chytil M. P., Analysis of the non-context-free component of formal languages. In Proceedings of MFCS 1976, Lecture Notes in Computer Science 45, 230–236.

   Google Scholar 

4. Chytil M. P., Separation of the context-free component from formal languages, paper in preparation.

   Google Scholar 

5. Chytil M. P., Crossing-bounded computations and their relation to the LBA-problem, Kybernetika 12 (1976), 2, 76–85.

   Google Scholar 

6. Cook S. A., Characterizations of pushdown machines in terms of time-bounded computers, JACM, 18, 1 (1971), 4–18.

   Article  Google Scholar 

7. Peckel J., this volume.

   Google Scholar 

8. Trachtenbrot B. A., Turing computations with logarithmic delay (in Russian), Algebra i logika, III, 4 (1964), 33–48.

   Google Scholar 

9. Wechsung G., Characterization of some classes of context-free languages in terms of complexity classes. In Proceedings of MFCS 1975, Lecture Notes in Computer Science 32, 457–461.

   Google Scholar 

10. Wechsung G., Kompliziertheitstheoretische Characterisierung der kontext-freien und linearen Sprachen, Elektronische Informations-verarbeitung und Kybernetik 12 (1976), 6, 289–300.

    Google Scholar 

11. Wechsung G., private communication.

    Google Scholar 

Download references