×

Some remarks on multihead automata. (English) Zbl 0369.68035


MSC:

68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
68W99 Algorithms in computer science
03D10 Turing machines and related notions
PDFBibTeX XMLCite
Full Text: EuDML

References:

[1] 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 · Zbl 0257.68065 · doi:10.1016/S0019-9958(68)91087-5
[2] 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.01701 MR266692 · Zbl 0207.01701 · doi:10.1016/S0022-0000(70)80004-6
[3] 3. A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974. Zbl0326.68005 MR413592 · Zbl 0326.68005
[4] 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] 5. R. BOOK, Translational Lemmas, Polynomial Time, and (Log (n))j-Space, Theoretical Computer Science, 1, 1976, 215-226. Zbl0326.68030 MR405918 · Zbl 0326.68030 · doi:10.1016/0304-3975(76)90057-8
[6] 6. R. BOOK, Comparing Complexity Classes, J. Computer and System Sci., 9, 1974, 213-229. Zbl0331.02020 MR366099 · Zbl 0331.02020 · doi:10.1016/S0022-0000(74)80008-5
[7] 7. S. A. COOK, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers J. ACM, 18, 1971, 4-18. Zbl0222.02035 MR292605 · Zbl 0222.02035 · doi:10.1145/321623.321625
[8] 8. S.A. COOK, An Observation on Time-Storage Trade Off, J. Computer and System Sci., 9, 1974, 308-316. Zbl0306.68026 MR398160 · Zbl 0306.68026 · doi:10.1016/S0022-0000(74)80046-2
[9] 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.68078 MR421161 · Zbl 0412.68078
[10] 10. S. A. COOK, Linear Time Simulation of Deterministic Two-Way Pushdown Automata, Proceedings of IFIP Congress, 1971, North Holland Publishers. Zbl0255.68015 MR400792 · Zbl 0255.68015
[11] 11. S. A. COOK and R. A. RECKHOW, Time Bounded Rondom Access Machines, J. Computer and System Sci., 7, 1973, 354-375. Zbl0284.68038 MR327074 · Zbl 0284.68038 · doi:10.1016/S0022-0000(73)80029-7
[12] 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 · Zbl 0298.68038
[13] 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] 14. S. A. GREIBACH, The Hardest Context-Free Language, SIAM J. on Computing, 2, 1973, 304-310. Zbl0278.68073 MR334591 · Zbl 0278.68073 · doi:10.1137/0202025
[15] 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] 16. M. A. HARRISON and O. H. IBARRA, Multitape and Multihead Pushdown Automata, Information and Control, 13, 1968, 433-470. Zbl0174.02701 MR238622 · Zbl 0174.02701 · doi:10.1016/S0019-9958(68)90901-7
[17] 17. J. HARTMANIS, On Nondeterminancy in Simple Computing Devices, Acta Informatica, 1, 1972, 336-344. Zbl0229.68014 MR317582 · Zbl 0229.68014 · doi:10.1007/BF00289513
[18] 18. J. E. HOPCROFT and J. D. ULLMAN, Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, Mass., 1969. Zbl0196.01701 MR237243 · Zbl 0196.01701
[19] 19. O. H. IBARRA, On Two-Way Multihead Automata, J. Computer and System Sci., 7. 1973, 28-36. Zbl0256.68028 MR408317 · Zbl 0256.68028 · doi:10.1016/S0022-0000(73)80048-0
[20] 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.68012 MR284290 · Zbl 0255.68012 · doi:10.1016/S0022-0000(71)80029-6
[21] 21. N. D. JONES, Space-Bounded Reducibility among Combinational Problems, J. Computer and System Sci., 11, 1975, 68-85. Zbl0317.02039 MR398165 · Zbl 0317.02039 · doi:10.1016/S0022-0000(75)80050-X
[22] 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.68040 MR438800 · Zbl 0376.68040
[23] 23. T. KAMEDA, Pushdown Automata with Counters, J. Computer and System Sci.,6, 1972. Zbl0242.68022 MR428804 · Zbl 0242.68022 · doi:10.1016/S0022-0000(72)80019-9
[24] 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 · Zbl 0163.01002 · doi:10.1016/S0019-9958(67)80008-1
[25] 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 · Zbl 0272.68054
[26] 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.68050 MR418518 · Zbl 0359.68050
[27] 27. J. SEIFERAS, Nondeterministic Time and Space Complexity Classes, Ph. D. dissertation, MIT, 1974. Project Mac Report TR-137, MIT, Cambridge, Mass. · Zbl 0358.68088
[28] 28. J. SEIFERAS, personal communication.
[29] 29. I. H. SUDBOROUGH, On Tape-Bounded Complexity Classes and Multihead Finite Automata, J. Computer and System Sci., 10, 1975. Zbl0299.68031 MR363832 · Zbl 0299.68031 · doi:10.1016/S0022-0000(75)80014-6
[30] 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.68077 MR436674 · Zbl 0365.68077
[31] 31. L. VALIANT, General Context-Free Recognition in Less than Cubic Time, J. Computer and System Sci., 10, 1975, 308-315. Zbl0312.68042 MR428796 · Zbl 0312.68042 · doi:10.1016/S0022-0000(75)80046-8
[32] 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.