| Title:
|
Reversals-space-parallelism tradeoffs for language recognition (English) |
| Author:
|
Hromkovič, Juraj |
| Language:
|
English |
| Journal:
|
Mathematica Slovaca |
| ISSN:
|
0139-9918 |
| Volume:
|
41 |
| Issue:
|
2 |
| Year:
|
1991 |
| Pages:
|
121-136 |
| . |
| Category:
|
math |
| . |
| MSC:
|
03D15 |
| MSC:
|
68Q05 |
| MSC:
|
68Q10 |
| MSC:
|
68Q15 |
| MSC:
|
68Q45 |
| idZBL:
|
Zbl 0749.68030 |
| idMR:
|
MR1108576 |
| . |
| Date available:
|
2009-09-25T10:30:07Z |
| Last updated:
|
2012-08-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/129539 |
| . |
| Reference:
|
[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. |
| Reference:
|
[2] CHANDRA A. K., KOZEN D. C., STOCKMEYER L. J.: Alternation.J. ACM, 28, 1981, 114-133. Zbl 0473.68043, MR 0603186 |
| Reference:
|
[3] COBHAM A.: The recognition for perfect squares.In: Proc. 7th Annual IEEE Symp. on SWAT, Berkeley 1966, pp. 78-87. |
| Reference:
|
[4] DURIS P., GALIL Z.: A time-space tradeoff for language recognition.Math. Systems Theory, 17, 1984, 3-12. Zbl 0533.68047, MR 0738748 |
| Reference:
|
[5] DURIS P., GALIL Z., PAUL W., REISCHUK R.: Two nonlinear lower bounds.In: Proc. 15th Annual ACM STOC, ACM 1983, pp. 127-132. |
| Reference:
|
[6] FREIVALDS R.: Quadratic lower bound for nondeterministic Turing machines.Unpublished communication at the 11th MFCS '84, Prague 1984. |
| Reference:
|
[7] LUPANOV O. B.: Ob odnom metode sinteza schem.(Russian.) Izv. Vuzov Radiofiz., 1, 1958, 120-140. |
| Reference:
|
[8] HROMKOVIČ J.: One-way multihead deterministic finite automata.Acta Inform., 19, 1983, 377-384. Zbl 0504.68049, MR 0717992 |
| Reference:
|
[9] HROMKOVIČ J.: On the power of alternation in automata theory.J. Comput. Syst. Sci., 31. 1985, 28-39. Zbl 0582.68018, MR 0813367 |
| Reference:
|
[10] HROMKOVIČ J.: Pooling a two-way multihead automaton with reversal number restriction.Acta Inform., 22, 1985, 589-594. MR 0822328 |
| Reference:
|
[11] HROMKOVIČ J.: Tradeoffs for language recognition on alternating machines.Theor. Comput. Sci., 63, 1989, 203-221. Zbl 0667.68060, MR 0984317 |
| Reference:
|
[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. Zbl 0413.68085, MR 0563679 |
| Reference:
|
[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 0471.68060 |
| Reference:
|
[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. |
| Reference:
|
[15] MATSUNO H., INOUE K., TANIGUCHI H., TAKANAMI I.: Alternating simple multihead finite automata.Theor. Comput. Sci., 36, 1985, 299-308. Zbl 0565.68055, MR 0796305 |
| Reference:
|
[16] LI M.: On one tape versus two stacks.Technical Report, 84 591, January 1984, Dept. of Computer Science, Cornell University, Ithaca, New York. |
| Reference:
|
[17] RIVEST R. L., YAO A. C: k + 1 heads are better than k.J. ACM, 25, 1978, 337-340. Zbl 0372.68017, MR 0483728 |
| Reference:
|
[18] SUDBOROUGH I. H.: Bounded-reversal multihead finite automata languages.Informat. Control, 25, 1974, 317-328 Zbl 0282.68033, MR 0400818 |
| . |
