Voir la notice de l'article provenant de la source Numdam
@article{ITA_1977__11_3_181_0,
author = {Sudborough, I. H.},
title = {Some remarks on multihead automata},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {181--195},
publisher = {Centrale des revues, Dunod-Gauthier-Villars},
address = {Montreuil},
volume = {11},
number = {3},
year = {1977},
mrnumber = {474983},
zbl = {0369.68035},
language = {en},
url = {http://geodesic.mathdoc.fr/item/ITA_1977__11_3_181_0/}
}
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 SP - 181 EP - 195 VL - 11 IS - 3 PB - Centrale des revues, Dunod-Gauthier-Villars PP - Montreuil UR - http://geodesic.mathdoc.fr/item/ITA_1977__11_3_181_0/ LA - en ID - ITA_1977__11_3_181_0 ER -
%0 Journal Article %A Sudborough, I. H. %T Some remarks on multihead automata %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 1977 %P 181-195 %V 11 %N 3 %I Centrale des revues, Dunod-Gauthier-Villars %C Montreuil %U http://geodesic.mathdoc.fr/item/ITA_1977__11_3_181_0/ %G en %F ITA_1977__11_3_181_0
Sudborough, I. H. Some remarks on multihead automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 11 (1977) no. 3, pp. 181-195. http://geodesic.mathdoc.fr/item/ITA_1977__11_3_181_0/
1. , and , Time and Tape Complexity of Pushdown Automata, Information and Control, 13, 3, 1968, 186-206. | Zbl
2. , and , On the Computational Power of Pushdown Automata, J. Computer and System Sci., 4, 2, 1970, 129-136. | Zbl | MR
3. , and , The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974. | Zbl | MR
4. , 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. , Translational Lemmas, Polynomial Time, and (Log (n))j-Space, Theoretical Computer Science, 1, 1976, 215-226. | Zbl | MR
6. , Comparing Complexity Classes, J. Computer and System Sci., 9, 1974, 213-229. | Zbl | MR
7. , Characterizations of Pushdown Machines in Terms of Time-Bounded Computers J. ACM, 18, 1971, 4-18. | Zbl | MR
8. , An Observation on Time-Storage Trade Off, J. Computer and System Sci., 9, 1974, 308-316. | Zbl | MR
9. and , Storage Requirements for Deterministic Polynomial Time Recognizable Languages, Sixth Annual ACM Symposium on Theory of Computing, 1974, 40-46. | Zbl | MR
10. , Linear Time Simulation of Deterministic Two-Way Pushdown Automata, Proceedings of IFIP Congress, 1971, North Holland Publishers. | Zbl | MR
11. and , Time Bounded Rondom Access Machines, J. Computer and System Sci., 7, 1973, 354-375. | Zbl | MR
12. and , 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. | MR
13. , 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. | MR
14. , The Hardest Context-Free Language, SIAM J. on Computing, 2, 1973, 304-310. | Zbl | MR
15. , A Note on the Recognition of One Counter Language, Revue Française d'Automatique, Informatique et Recherche Opérationnelle, 1975, 5-12. | MR | mathdoc-id
16. and , Multitape and Multihead Pushdown Automata, Information and Control, 13, 1968, 433-470. | Zbl | MR
17. , On Nondeterminancy in Simple Computing Devices, Acta Informatica, 1, 1972, 336-344. | Zbl | MR
18. and , Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, Mass., 1969. | Zbl | MR
19. , On Two-Way Multihead Automata, J. Computer and System Sci., 7. 1973, 28-36. | Zbl | MR
20. , 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. | Zbl | MR
21. , Space-Bounded Reducibility among Combinational Problems, J. Computer and System Sci., 11, 1975, 68-85. | Zbl | MR
22. and , Complete Problems for Deterministic Polynomial Time, Proceeding of Sixth Annual ACM Symposium on Theory of Computing, 1974, 33-39. | Zbl | MR
23. , Pushdown Automata with Counters, J. Computer and System Sci.,6, 1972. | Zbl | MR
24. , A Note on Computing Time for Recognition of Languages Generated by Linear Grammars, Information and Control, 10, 1967, 209-214. | Zbl
25. , and , 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. | Zbl
26. and , Word Problems Requiring Exponential Time, Proceedings of Fifth Annual ACM Symposium on Theory of Computing, 1973, 1-9. | Zbl | MR
27. , Nondeterministic Time and Space Complexity Classes, Ph. D. dissertation, MIT, 1974. Project Mac Report TR-137, MIT, Cambridge, Mass.
28. , personal communication.
29. , On Tape-Bounded Complexity Classes and Multihead Finite Automata, J. Computer and System Sci., 10, 1975. | Zbl | MR
30. , 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. | Zbl | MR
31. , General Context-Free Recognition in Less than Cubic Time, J. Computer and System Sci., 10, 1975, 308-315. | Zbl | MR
32. , 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.