Some remarks on multihead automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1977)
- Volume: 11, Issue: 3, page 181-195
- ISSN: 0988-3754
Access Full Article
topHow to cite
topSudborough, I. H.. "Some remarks on multihead automata." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 11.3 (1977): 181-195. <http://eudml.org/doc/92050>.
@article{Sudborough1977,
author = {Sudborough, I. H.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
language = {eng},
number = {3},
pages = {181-195},
publisher = {EDP-Sciences},
title = {Some remarks on multihead automata},
url = {http://eudml.org/doc/92050},
volume = {11},
year = {1977},
}
TY - JOUR
AU - Sudborough, I. H.
TI - Some remarks on multihead automata
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1977
PB - EDP-Sciences
VL - 11
IS - 3
SP - 181
EP - 195
LA - eng
UR - http://eudml.org/doc/92050
ER -
References
top- 1. A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, Time and Tape Complexity of Pushdown Automata, Information and Control, 13, 3, 1968, 186-206. Zbl0257.68065
- 2. A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, On the Computational Power of Pushdown Automata, J. Computer and System Sci., 4, 2, 1970, 129-136. Zbl0207.01701MR266692
- 3. A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974. Zbl0326.68005MR413592
- 4. C. BEERI, Reductions in the Number of Heads for the Nondeterminancy Problem in Multihead Automata, Technical Report, Institute of Mathematics, The Hebrew Institute of Jerusalem, Israel.
- 5. R. BOOK, Translational Lemmas, Polynomial Time, and (Log (n))j-Space, Theoretical Computer Science, 1, 1976, 215-226. Zbl0326.68030MR405918
- 6. R. BOOK, Comparing Complexity Classes, J. Computer and System Sci., 9, 1974, 213-229. Zbl0331.02020MR366099
- 7. S. A. COOK, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers J. ACM, 18, 1971, 4-18. Zbl0222.02035MR292605
- 8. S.A. COOK, An Observation on Time-Storage Trade Off, J. Computer and System Sci., 9, 1974, 308-316. Zbl0306.68026MR398160
- 9. S. A. COOK and R. SETHI, Storage Requirements for Deterministic Polynomial Time Recognizable Languages, Sixth Annual ACM Symposium on Theory of Computing, 1974, 40-46. Zbl0412.68078MR421161
- 10. S. A. COOK, Linear Time Simulation of Deterministic Two-Way Pushdown Automata, Proceedings of IFIP Congress, 1971, North Holland Publishers. Zbl0255.68015MR400792
- 11. S. A. COOK and R. A. RECKHOW, Time Bounded Rondom Access Machines, J. Computer and System Sci., 7, 1973, 354-375. Zbl0284.68038MR327074
- 12. P. FLAJOLET and J. M. STEYAERT, Decision Problems for Multihead Finite Automata, Proceedings of Symposium and Summer School on the Mathematical Foundations of Computer Science, High Tatras, Czechoslavakia, 1973, 225-230. MR408315
- 13. Z. GALIL, Two-Way Deterministic Pushdown Automaton Languages and Some Open Problems in the Theory of Computation, Proceedings of Fifteenth Annual IEEE Symposium on Switching and Automata Theory, 1974, 170-177. MR414337
- 14. S. A. GREIBACH, The Hardest Context-Free Language, SIAM J. on Computing, 2, 1973, 304-310. Zbl0278.68073MR334591
- 15. S. A. GREIBACH, A Note on the Recognition of One Counter Language, Revue Française d'Automatique, Informatique et Recherche Opérationnelle, 1975, 5-12. MR391578
- 16. M. A. HARRISON and O. H. IBARRA, Multitape and Multihead Pushdown Automata, Information and Control, 13, 1968, 433-470. Zbl0174.02701MR238622
- 17. J. HARTMANIS, On Nondeterminancy in Simple Computing Devices, Acta Informatica, 1, 1972, 336-344. Zbl0229.68014MR317582
- 18. J. E. HOPCROFT and J. D. ULLMAN, Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, Mass., 1969. Zbl0196.01701MR237243
- 19. O. H. IBARRA, On Two-Way Multihead Automata, J. Computer and System Sci., 7. 1973, 28-36. Zbl0256.68028MR408317
- 20. O. H. IBARRA, Characterizations of Some Tape and Time Complexity Classes of Turing Machines in Terms of Multihead and Auxiliary Stack Automata, J. Computer and System Sci., 5, 1971, 88-117. Zbl0255.68012MR284290
- 21. N. D. JONES, Space-Bounded Reducibility among Combinational Problems, J. Computer and System Sci., 11, 1975, 68-85. Zbl0317.02039MR398165
- 22. N. D. JONES and W. T. LAASER, Complete Problems for Deterministic Polynomial Time, Proceeding of Sixth Annual ACM Symposium on Theory of Computing, 1974, 33-39. Zbl0376.68040MR438800
- 23. T. KAMEDA, Pushdown Automata with Counters, J. Computer and System Sci.,6, 1972. Zbl0242.68022MR428804
- 24. T. KASAMI, A Note on Computing Time for Recognition of Languages Generated by Linear Grammars, Information and Control, 10, 1967, 209-214. Zbl0163.01002
- 25. P. M. LEWIS, R. E. STEARNS and J. HARTMANIS, Memory Bounds for the Recognition of Context-Free and Context-Sensitive Languages, Proceedings of Sixth Annual IEEE Conference on Switching Circuit Theory and Logical Design, 1965, 199-212. Zbl0272.68054
- 26. A. R. MEYER and L. J. STOCKMEYER, Word Problems Requiring Exponential Time, Proceedings of Fifth Annual ACM Symposium on Theory of Computing, 1973, 1-9. Zbl0359.68050MR418518
- 27. J. SEIFERAS, Nondeterministic Time and Space Complexity Classes, Ph. D. dissertation, MIT, 1974. Project Mac Report TR-137, MIT, Cambridge, Mass.
- 28. J. SEIFERAS, personal communication.
- 29. I. H. SUDBOROUGH, On Tape-Bounded Complexity Classes and Multihead Finite Automata, J. Computer and System Sci., 10, 1975. Zbl0299.68031MR363832
- 30. I. H. SUDBOROUGH, On Deterministic Context-Free Languages, Multihead Automata, and the Power of an Auxiliary Pushdown Store, Proceedings of Eighth Annual ACM Symposium on Theory of Computing, 1976, 141-148. Zbl0365.68077MR436674
- 31. L. VALIANT, General Context-Free Recognition in Less than Cubic Time, J. Computer and System Sci., 10, 1975, 308-315. Zbl0312.68042MR428796
- 32. R. WEICKER, General Context Free Language Recognition by a RAM with Uniform Cost Criterion in Time n2log n, Technical Report No. 182, February, 1976, The Pennsylvania State University, University Park, Pa.
Citations in EuDML Documents
topNotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.