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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.