EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 26 / No 6 (1992) RAIRO-Theor. Inf. Appl., 26 6 (1992) 507-522 References
Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 26, Number 6, 1992
Page(s) 507 - 522
DOI https://doi.org/10.1051/ita/1992260605071
Published online 01 February 2017
  1. [A&86] M. AJTAI, L. BABAJ, P. HAJNAL, J. KOMLOS, P. PUDLAK, V. RÖDEL, E. SZEMEREDI and G. TURAN, Two Lower Bounds for Branching Programs, Proc. 18 ACM-STOC, 1986, pp. 30-39. [Google Scholar]
  2. [AM86] N. ALON and W. MAASS, Meanders, Ramsey Theory and Lower Bounds for Branching Programs, Proc. 27th ACM-STOC, 1986, pp. 30-39. [Google Scholar]
  3. [CH89] J. CAI and L. HEMACHANDRA, On the Power of Parity Polynomial Time, Proc. STACS'89, Springer Verlag, L.N.C.S., No. 349, pp. 229-239. [MR: 1027404] [Google Scholar]
  4. [Co66] H. COBHAM, The Recognisation Problem for Perfect Square, Proc. 7-th I.E.E.E. Symp. on SWAT, 1966, pp. 78-87. [Google Scholar]
  5. [DM89] C. DAMM and Ch. MEINEL. Separating Completely Complexity Classes Related to Polynomial Size Ω-Decision Trees, Proc. of FCT'89, L.N.C.S., No. 380, pp. 127-136. [MR: 1033541] [Zbl: 0756.68039] [Google Scholar]
  6. [H&87] A. HAJNAL, W. MAASS, P. PUDLAK, M. SZEGEDY and G. TURAN, Threshold Circuits of Bounded Depth, Proc. 28 I.E.E.E. Symp. F.O.C.S., pp. 99-110. [Zbl: 0801.68052] [Google Scholar]
  7. N. IMMERMAN, Nondeterministic Space is Closed Under Complement, Techn. Report 552, Yale University, 1987. [MR: 961049] [Google Scholar]
  8. [J86] S. JUKNA, Lower Bounds on the Complexity of Local Circuits, Proc. MFCS'86, 1986, L.N.C.S. No. 233, pp. 440-448. [Zbl: 0609.94018] [Google Scholar]
  9. [KMW88] M. KRAUSE, Ch. MEINEL and S. WAACK, Separating the Eraser Turing Machine Classes L, NL, co-NL and P, Proc. of M.F.C.S.'88, Lect. Notes in Compct. Sci, No. 324, pp. 405-413, Theoret. Comput. Sci. (to appear). [MR: 1023444] [Zbl: 0656.68050] [Google Scholar]
  10. [KMW89] M. KRAUSE, S. WAACK and Ch. MEINEL, Separating Complexity Classes Related to Certain Input-Oblivious Logarithmic-Space Bounded Turing-Machines, Proc. I.E.E.E. Structure & Complexity, 1989, Eugenie, U.S.A. [Zbl: 0768.68017] [Google Scholar]
  11. [KW88] M. KRAUSE and S. WAACK, On Oblivious Branching Programs of Linear Length, Proc. of FCT'89, L.N.C.S., No. 380, pp. 287-296 Inform. Comput. (to appear). [MR: 1127534] [Zbl: 0756.68042] [Google Scholar]
  12. [M88] Ch. MEINEL, The Power of Polynomial Size Ω-Branching Programs, Proc. STACS'88, Bordeaux, L.N.C.S. No. 294, pp. 81-90, Inform. Comput. (to appear). [MR: 935789] [Zbl: 0644.68074] [Google Scholar]
  13. [M89] Ch. MEINEL, Modified Branching Programs and their Computational Power, Berlin, 1988, in L.N.C.S. No. 370. [MR: 1009367] [Zbl: 0669.68042] [Google Scholar]
  14. [PZ83] C. PAPADIMITRIOU and S. ZACHOS, Two Remarks on the Power of Counting, Proc. 6 th GI Conf. on Theor. Comp. Sci., Springer Verlag, L.N.C.S., No. 145 pp. 269-276. [Zbl: 0506.68039] [Google Scholar]
  15. [Ru81] W. Ruzzo, On Uniform Circuit Complexity, J. Comp. System Sci., 1981, 22, (3), pp. 236-283. [MR: 633540] [Zbl: 0462.68013] [Google Scholar]
  16. [S87] R. SZELEPCSENYI, The Method of Forcing for Nondeterministic Automata, Bulletin of the E.A.T.C.S., 1987, 33, pp. 96-99. [Zbl: 0664.68082] [Google Scholar]
  17. [W84] I. WEGENER, On the Complexity of Branching Programs and Decision Trees for Clique Functions, Interner Bericht der Univ. Frankfurt, 1984, in J. of the A.C.M., 1988, 35, pp. 461-471. [MR: 935261] [Zbl: 0652.68063] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.