Reversals-space-parallelism tradeoffs for language recognition
Mathematica Slovaca (1991)
- Volume: 41, Issue: 2, page 121-136
- ISSN: 0232-0525
Access Full Article
top
How to cite
topHromkovič, Juraj. "Reversals-space-parallelism tradeoffs for language recognition." Mathematica Slovaca 41.2 (1991): 121-136. <http://eudml.org/doc/31849>.
@article{Hromkovič1991,
author = {Hromkovič, Juraj},
journal = {Mathematica Slovaca},
keywords = {alternation; lower bound; tradeoff of complexity measures},
language = {eng},
number = {2},
pages = {121-136},
publisher = {Mathematical Institute of the Slovak Academy of Sciences},
title = {Reversals-space-parallelism tradeoffs for language recognition},
url = {http://eudml.org/doc/31849},
volume = {41},
year = {1991},
}
TY - JOUR
AU - Hromkovič, Juraj
TI - Reversals-space-parallelism tradeoffs for language recognition
JO - Mathematica Slovaca
PY - 1991
PB - Mathematical Institute of the Slovak Academy of Sciences
VL - 41
IS - 2
SP - 121
EP - 136
LA - eng
KW - alternation; lower bound; tradeoff of complexity measures
UR - http://eudml.org/doc/31849
ER -
References
top- 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. (1980)
- CHANDRA A. K., KOZEN D. C., STOCKMEYER L. J., Alternation, J. ACM, 28, 1981, 114-133. (1981) Zbl0473.68043MR0603186
- COBHAM A., The recognition for perfect squares, In: Proc. 7th Annual IEEE Symp. on SWAT, Berkeley 1966, pp. 78-87. (1966)
- DURIS P., GALIL Z., A time-space tradeoff for language recognition, Math. Systems Theory, 17, 1984, 3-12. (1984) Zbl0533.68047MR0738748
- DURIS P., GALIL Z., PAUL W., REISCHUK R., Two nonlinear lower bounds, In: Proc. 15th Annual ACM STOC, ACM 1983, pp. 127-132. (1983)
- FREIVALDS R., Quadratic lower bound for nondeterministic Turing machines, Unpublished communication at the 11th MFCS '84, Prague 1984. (1984)
- LUPANOV O. B., Ob odnom metode sinteza schem, (Russian.) Izv. Vuzov Radiofiz., 1, 1958, 120-140. (1958)
- HROMKOVIČ J., One-way multihead deterministic finite automata, Acta Inform., 19, 1983, 377-384. (1983) Zbl0504.68049MR0717992
- HROMKOVIČ J., On the power of alternation in automata theory, J. Comput. Syst. Sci., 31. 1985, 28-39. (1985) Zbl0582.68018MR0813367
- HROMKOVIČ J., Pooling a two-way multihead automaton with reversal number restriction, Acta Inform., 22, 1985, 589-594. (1985) MR0822328
- HROMKOVIČ J., Tradeoffs for language recognition on alternating machines, Theor. Comput. Sci., 63, 1989, 203-221. (1989) Zbl0667.68060MR0984317
- 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. (1979) Zbl0413.68085MR0563679
- 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. (1981) Zbl0471.68060
- MAASS W., Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines, In: Proc. 16th Annual ACM STOC, ACM 1984, pp. 401-408. (1984)
- MATSUNO H., INOUE K., TANIGUCHI H., TAKANAMI I., Alternating simple multihead finite automata, Theor. Comput. Sci., 36, 1985, 299-308. (1985) Zbl0565.68055MR0796305
- LI M., On one tape versus two stacks, Technical Report, 84 591, January 1984, Dept. of Computer Science, Cornell University, Ithaca, New York. (1984)
- RIVEST R. L., YAO A. C, k + 1 heads are better than k, J. ACM, 25, 1978, 337-340. (1978) Zbl0372.68017MR0483728
- SUDBOROUGH I. H., Bounded-reversal multihead finite automata languages, Informat. Control, 25, 1974, 317-328 (1974) Zbl0282.68033MR0400818
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.