Lower bounds on the complexity of real-time branching programs. (English) Zbl 0664.68046

Author’s summary: “A \((2m)^{n/24}\) lower bound is given for the real- time decision graph complexity of the Dyck language \(D_ m^*\). Furthermore, a \(2^{n/48}\) lower bound for the real-time branching program complexity of an encoding of the Dyck language \(D^*_ 2\) is proved. Previously known similar lower bounds are \(2^{c\cdot n}\), \(c\approx 10^{-13}\), for one-time-only branching programs (a less powerful model), and \(2^{\Omega (\sqrt{n})}\) for real-time branching programs.”
Reviewer: D.Lucanu


68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q45 Formal languages and automata
Full Text: DOI EuDML


[1] 1. M. AJTAI, L. BABAI, P. HAJNAL, J. KOMLOS, P. PUDLAK, V. RÖDEL, E. SZEMEREDI and G. TURAN, Two lower bounds for branching programs, 18th ACM STOC, 1986, pp. 30-39.
[2] 2. A. BORODIN, D. DOLEV, F. E. FICH and W. PAUL, Bounds for width two branching programs, 15th ACM STOC, 1983, pp. 87-93. · Zbl 0589.68034
[3] 3. L. BUDACH, Lower bounds for the number of nodes in a decision tree, EIK 21, 1985, No 4/5, pp.221-228. MR824578
[4] 4. A. K. CHANDRA, M. L. FURST and R. J. LIPTON, Multiparty protocols, 15th ACM STOC, 1983, pp.94-99.
[5] 5. P. E. DUNNE, Lower bounds on the complexity of 1-time-only branching programs, FCT Proc., Lect. Notes in Comp. Sci.,Vol. 199, 1985, pp. 90-99. Zbl0575.68064 MR821228 · Zbl 0575.68064
[6] 6. R. J. LIPTON and Y. ZALCSTEIN, Word problems solvable in logspace, Journal of the ACM, Vol. 24, No.3, 1977, pp. 522-526. Zbl0359.68049 MR445901 · Zbl 0359.68049
[7] 7. E. I. NECHIPORUK, On a Boolean function, Dokl. Akad. Nauk USSR, Vol. 169, No. 4, 1966, pp.765-766. Zbl0161.00901 MR218148 · Zbl 0161.00901
[8] 8. P. PUDLAK, A lower bound on the complexity of branching programs, Preprint, Univ. Prague, 1983. MR783479
[9] 9. U. VISHKIN and A. WIGDERSON, Trode-offs between depth and width in parallel computation, SIAM J. Comput, Vol. 14, No.2, 1985, pp. 303-314. Zbl0573.68015 MR784739 · Zbl 0573.68015
[10] 10. I. WEGENER, On the complexity of branching programs and decision trees for clique fonctions, Univ. of Frankfurt, Fachbereich Informatik, Interner Bericht, 5/84, 1984. · Zbl 0592.94025
[11] 11. A. C. YAO, Lower bounds by probabilistic arguments, 24th IEEE FOCS, 1983, pp. 420-428.
[12] 12. S. ZAK, An exponential lower bound for one-time-only branching programs, MFCS Proc., Lect. Notes in Comp. Sci., Vol. 176, 1984, pp. 562-566. Zbl0558.68044 MR783488 · Zbl 0558.68044
[13] 13. S. ZAK, An exponential lower bound for real-time branching programs, manuscript.
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.