Complexity arguments in algebraic language theory
Alt, Helmut ; Mehlhorn, Kurt
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 13 (1979), p. 217-225 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1979-01-01
@article{ITA_1979__13_3_217_0,
     author = {Alt, Helmut and Mehlhorn, Kurt},
     title = {Complexity arguments in algebraic language theory},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {13},
     year = {1979},
     pages = {217-225},
     mrnumber = {554683},
     zbl = {0421.68048},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1979__13_3_217_0}
}

Alt, Helmut; Mehlhorn, Kurt. Complexity arguments in algebraic language theory. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 13 (1979) pp. 217-225. http://gdmltest.u-ga.fr/item/ITA_1979__13_3_217_0/

1. A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Publ. Comp., 1974. | MR 413592 | Zbl 0326.68005

2. H. Alt and K. Mehlhorn, Lower Bounds for the Space Complexity of Context-Free Recognition, 3rd Coll. on Automata, Languages and Programming, Edinburgh, 1976, pp. 338-354. | Zbl 0368.68069

3. H. Alt, Einige Beobachtungen zum Produkt von Zeit und Platzbedarf bei Turingmaschinen, Universität des Saarlandes, Fachbereich Informatik, Report-A 76/09.

4. J. Beauquier, Générateurs algébriques non-ambigus, 3rd Colloquium on Automata, Languages and Programming, Edinburgh, 1976, pp.66-73. | Zbl 0363.68106

5. L. Boasson, Classification of the Context-Free Languages, MFCS 1977, Lecture Notes in Computer Science, Vol. 53, pp. 34-43. | MR 474990 | Zbl 0357.68089

6. L. Boasson, Un Langage Algébrique Particulier R.A.I.R.O., Informatique Théorique, (this issue). | Numdam | Zbl 0424.68042

7. J. Hartmanis, One-Tape Turing Machine Computations, J. Assoc. Comput. Mach., Vol. 15, 1968, pp. 325-339. | MR 252127 | Zbl 0162.31703

8. J. W. Hopcroft and J. D. Ullman, Formal Languages and their Relation to Automata, Addison-Wesley, Reading, Mass., 1969. | MR 237243 | Zbl 0196.01701

9. P. M. Lewis, J. Hartmanis and R. E. Stearns, Memory Bounds for the Recognition of Context-Free and Context-Sensitive Languages, I.E.E.E. Conference Record on Switching Circuit Theory and Logical Design, 1965, pp. 179-202. | Zbl 0272.68054