Geodesic
Reversals-space-parallelism tradeoffs for language recognition
Mathematica slovaca, Tome 41 (1991) no. 2, pp. 121-136
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Classification : 03D15, 68Q05, 68Q10, 68Q15, 68Q45 
@article{MASLO_1991_41_2_a1,
     author = {Hromkovi\v{c}, Juraj},
     title = {Reversals-space-parallelism tradeoffs for language recognition},
     journal = {Mathematica slovaca},
     pages = {121--136},
     year = {1991},
     volume = {41},
     number = {2},
     mrnumber = {1108576},
     zbl = {0749.68030},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MASLO_1991_41_2_a1/}
}
TY  - JOUR
AU  - Hromkovič, Juraj
TI  - Reversals-space-parallelism tradeoffs for language recognition
JO  - Mathematica slovaca
PY  - 1991
SP  - 121
EP  - 136
VL  - 41
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MASLO_1991_41_2_a1/
LA  - en
ID  - MASLO_1991_41_2_a1
ER  - 
%0 Journal Article
%A Hromkovič, Juraj
%T Reversals-space-parallelism tradeoffs for language recognition
%J Mathematica slovaca
%D 1991
%P 121-136
%V 41
%N 2
%U http://geodesic.mathdoc.fr/item/MASLO_1991_41_2_a1/
%G en
%F MASLO_1991_41_2_a1
Hromkovič, Juraj. Reversals-space-parallelism tradeoffs for language recognition. Mathematica slovaca, Tome 41 (1991) no. 2, pp. 121-136. http://geodesic.mathdoc.fr/item/MASLO_1991_41_2_a1/

[1] BORODIN A. B., COOK S. A.: A time-space tradeoff for sorting on a general model of computation. In: Proc. 12th Annual ACM STOC, Los Angeles, ACM 1980, pp. 294-301.

[2] CHANDRA A. K., KOZEN D. C., STOCKMEYER L. J.: Alternation. J. ACM, 28, 1981, 114-133. | MR | Zbl

[3] COBHAM A.: The recognition for perfect squares. In: Proc. 7th Annual IEEE Symp. on SWAT, Berkeley 1966, pp. 78-87.

[4] DURIS P., GALIL Z.: A time-space tradeoff for language recognition. Math. Systems Theory, 17, 1984, 3-12. | MR | Zbl

[5] DURIS P., GALIL Z., PAUL W., REISCHUK R.: Two nonlinear lower bounds. In: Proc. 15th Annual ACM STOC, ACM 1983, pp. 127-132.

[6] FREIVALDS R.: Quadratic lower bound for nondeterministic Turing machines. Unpublished communication at the 11th MFCS '84, Prague 1984.

[7] LUPANOV O. B.: Ob odnom metode sinteza schem. (Russian.) Izv. Vuzov Radiofiz., 1, 1958, 120-140.

[8] HROMKOVIČ J.: One-way multihead deterministic finite automata. Acta Inform., 19, 1983, 377-384. | MR | Zbl

[9] HROMKOVIČ J.: On the power of alternation in automata theory. J. Comput. Syst. Sci., 31. 1985, 28-39. | MR | Zbl

[10] HROMKOVIČ J.: Pooling a two-way multihead automaton with reversal number restriction. Acta Inform., 22, 1985, 589-594. | MR

[11] HROMKOVIČ J.: Tradeoffs for language recognition on alternating machines. Theor. Comput. Sci., 63, 1989, 203-221. | MR | Zbl

[12] JANIGA L.: Real-time computations of two-way multihead finite automata. In: Proc. FCT '79, ed. L. Budach. Academic Verlag, Berlin 1979, pp. 214-219. | MR | Zbl

[13] KING K. N.: Alternating multihead finite automata. In: Proc. 8th ICALP'81. Lecture Notes in Computer Science 115. Springer-Verlag, Berlin 1981, pp 506-520. | Zbl

[14] MAASS W.: Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines. In: Proc. 16th Annual ACM STOC, ACM 1984, pp. 401-408.

[15] MATSUNO H., INOUE K., TANIGUCHI H., TAKANAMI I.: Alternating simple multihead finite automata. Theor. Comput. Sci., 36, 1985, 299-308. | MR | Zbl

[16] LI M.: On one tape versus two stacks. Technical Report, 84 591, January 1984, Dept. of Computer Science, Cornell University, Ithaca, New York.

[17] RIVEST R. L., YAO A. C: k + 1 heads are better than k. J. ACM, 25, 1978, 337-340. | MR | Zbl

[18] SUDBOROUGH I. H.: Bounded-reversal multihead finite automata languages. Informat. Control, 25, 1974, 317-328 | MR | Zbl