Lower bounds on the complexity of real-time branching programs
Open Access
- 1 January 1988
- journal article
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 22 (4) , 447-459
- https://doi.org/10.1051/ita/1988220404471
Abstract
No abstract availableThis publication has 8 references indexed in Scilit:
- Lower bounds on the complexity of 1-time only branching programs (Preliminary version)Published by Springer Nature ,2006
- Two lower bounds for branching programsPublished by Association for Computing Machinery (ACM) ,1986
- Trade-Offs between Depth and Width in Parallel ComputationSIAM Journal on Computing, 1985
- An exponential lower bound for one-time-only branching programsPublished by Springer Nature ,1984
- Lower bounds by probabilistic argumentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Bounds for width two branching programsPublished by Association for Computing Machinery (ACM) ,1983
- Multi-party protocolsPublished by Association for Computing Machinery (ACM) ,1983
- Word Problems Solvable in LogspaceJournal of the ACM, 1977