×
Galil, Zvi

Palindrome recognition in real time by a multitape Turing machine. (English) Zbl 0386.03020

J. Comput. Syst. Sci. 16, 140-157 (1978).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0386.03020

Cited in 9 Documents

MSC:

03D15 Complexity of computation (including implicit computational complexity)
03D10 Turing machines and related notions
PDF BibTeX XML Cite
\textit{Z. Galil}, J. Comput. Syst. Sci. 16, 140--157 (1978; Zbl 0386.03020)
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0286.68029
[2] Atrubin, A. J., A one-dimensional real-time iterative multiplier, IEEE Trans. Electron. Computers, EC-14, 394-399 (1965)
[3] Bergerson, H. W., Palindromes and Anagrams (1973), Dover: Dover New York
[4] Cole, S. N., Real-Time Computation by Iterative Arrays of Finite-State Machines, (Doctoral Thesis (August 1964), Harvard Univ.,: Harvard Univ., Cambridge, Mass) · Zbl 0172.20804
[5] Cole, S. N., Real-time computation by n-dimensional iterative arrays of finite-state machines, IEEE Trans. Computers, C-13, 349-365 (1969) · Zbl 0172.20804
[7] Fischer, P. C.; Meyer, A. R.; Rosenberg, A. L., Real-time simulation of multihead tape units, J. Assoc. Comput. Mach., 19, 590-607 (1972) · Zbl 0261.68027
[8] Fischer, M. J.; Paterson, M. S., String matching and other products, (Karp, R. M., SIAM AXIS Proc. on Complexity of Computation (1974), Amer. Math. Soc.,: Amer. Math. Soc., Providence, R.I), 113-126
[9] Galil, Z., Two fast simulations which imply some fast string-matching and palindrome recognition algorithms, Inform. Process. Lett., 4, 85-87 (1976) · Zbl 0328.68047
[11] Hartmanis, J.; Stearns, R. E., On the computational complexity of algorithms, Trans. Amer. Math. Soc., 117, 285-306 (1965) · Zbl 0131.15404
[12] Hopcroft, J. E.; Ullman, J. D., Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0196.01701
[13] Knuth, E. E.; Morris, J. H.; Pratt, V. R., Fast pattern matching in strings, SIAM J. Computing, 6, 323-350 (1977) · Zbl 0372.68005
[14] Manacher, G., A new linear-time on-line algorithm for finding the smallest initial palindrome of a string, J. Assoc. Comput. Mach., 22, 346-351 (1975) · Zbl 0305.68027
[15] Rarin, M. O., Real-time computation, Israel J. Math., 1, 203-211 (1963) · Zbl 0156.25603
[16] Seiferas, J. I., Iterative arrays with direct central control, Acto Inform., 8, 177-192 (1977) · Zbl 0337.94035
[17] Slisenko, A. O., Recognition of palindromes by multihead Turing machines, (Orverkov, V. P.; Sonin, N. A., Problems in the Constructive Trend in Mathematics VI. Problems in the Constructive Trend in Mathematics VI, Proceeding of the Steklov Institute of Mathematics, No. 129 (1973), Academy of Sciences of the USSR), 30-202
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.