Complexity arguments in algebraic language theory

Helmut Alt; Kurt Mehlhorn

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1979)

  • Volume: 13, Issue: 3, page 217-225
  • ISSN: 0988-3754

How to cite

top

Alt, Helmut, and Mehlhorn, Kurt. "Complexity arguments in algebraic language theory." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 13.3 (1979): 217-225. <http://eudml.org/doc/92100>.

@article{Alt1979,
author = {Alt, Helmut, Mehlhorn, Kurt},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {computational complexity; multitape Turing machines; lower bounds; recognizing generators of the rational cone of context-free languages; language of palindromes},
language = {eng},
number = {3},
pages = {217-225},
publisher = {EDP-Sciences},
title = {Complexity arguments in algebraic language theory},
url = {http://eudml.org/doc/92100},
volume = {13},
year = {1979},
}

TY - JOUR
AU - Alt, Helmut
AU - Mehlhorn, Kurt
TI - Complexity arguments in algebraic language theory
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1979
PB - EDP-Sciences
VL - 13
IS - 3
SP - 217
EP - 225
LA - eng
KW - computational complexity; multitape Turing machines; lower bounds; recognizing generators of the rational cone of context-free languages; language of palindromes
UR - http://eudml.org/doc/92100
ER -

References

top
  1. 1. A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, Publ. Comp., 1974. Zbl0326.68005MR413592
  2. 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. Zbl0368.68069
  3. 3. H. ALT, Einige Beobachtungen zum Produkt von Zeit und Platzbedarf bei Turingmaschinen, Universität des Saarlandes, Fachbereich Informatik, Report-A 76/09. 
  4. 4. J. BEAUQUIER, Générateurs algébriques non-ambigus, 3rd Colloquium on Automata, Languages and Programming, Edinburgh, 1976, pp.66-73. Zbl0363.68106
  5. 5. L. BOASSON, Classification of the Context-Free Languages, MFCS 1977, Lecture Notes in Computer Science, Vol. 53, pp. 34-43. Zbl0357.68089MR474990
  6. 6. L. BOASSON, Un Langage Algébrique Particulier R.A.I.R.O., Informatique Théorique, (this issue). Zbl0424.68042
  7. 7. J. HARTMANIS, One-Tape Turing Machine Computations, J. Assoc. Comput. Mach., Vol. 15, 1968, pp. 325-339. Zbl0162.31703MR252127
  8. 8. J. W. HOPCROFT and J. D. ULLMAN, Formal Languages and their Relation to Automata, Addison-Wesley, Reading, Mass., 1969. Zbl0196.01701MR237243
  9. 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. Zbl0272.68054

NotesEmbed ?

top

You must be logged in to post comments.