Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 23, Number 2, 1989
Page(s) 177 - 194
DOI https://doi.org/10.1051/ita/1989230201771
Published online 01 February 2017
  1. 1. J. L. BALCÁZAR, J. DÍAZ and J. GABARRÓ Uniform Characterizations of Nonuniform Complexity Measures, Information and Control, Vol. 67, Nos. 1-3, 1985, pp. 53-69. [MR: 833860] [Zbl: 0588.68021]
  2. 2. J. L. BALCÁZAR and J. GABARRÓ, Some Comments About Notations of Orders of Magnitude, Buil. EATCS, Vol. 30, 1986, pp. 34-42. [Zbl: 1023.68587]
  3. 3. D. BARRINGTON, Bounded-width Polynomial-size Branching Programs Recognize Exactly Those Languages in NCl, In: l8th ACM Symp. Th. of Comp., 1986, pp. 1-5.
  4. 4. A. BORODIN, On Relating Time and Space to Size and Depth, SIAM J. Comp., Vol. 6. No. 4, 1977, pp. 733-744. [MR: 461984] [Zbl: 0366.68039]
  5. 5. F. BRANDENBURG, On One-way Auxiliary Pushdown Automata, In: 3rd GI Conf. on Theor. Comp. Sci., 1977, Springer Verlag, Lect. Notes in Comp. Sci., Vol. 48, pp. 132-144. [MR: 483712] [Zbl: 0359.68055]
  6. 6. W. BUCHER, K. CULIK, H. MAURER and D. WOTSCHKE, Concise Description of Finite Languages, Theor. Comp. Sci., Vol. 14, No. 3, 1981, pp. 227-246. [MR: 619000] [Zbl: 0469.68081]
  7. 7. R. CASAS and J. GABARRO, About LOG-ON languages, Internal report RR 85/02, Facultat d'Informàtica de Barcelona.
  8. 8. M. CHYTIL, Almost context-free languages, Manuscript, 1984.
  9. 9. S. COOK, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal ACM, Vol. 18, No. 1, 1971, pp. 4-18. [MR: 292605] [Zbl: 0222.02035]
  10. 10. A. EHRENFEUTCH and G. ROZENBERG, On the Separating Power of EOL Systems, RAIRO Inf. Theor., Vol. 17, No. 1, 1983, pp. 13-22. [EuDML: 92174] [MR: 701985] [Zbl: 0512.68059]
  11. 11. J. GABARRÓ Funciones de complejidad y su relación con las familias abstractas de lenguajes. Ph. D. dissertation, 1983.
  12. See also: Initial Index: a new Complexity Function for Languages, In: 10th Int. Coll. on Aut. Lang. and Prog., 1983, Springer Verlag, Lect. Notes in Comp. Sci., Vol. 154, pp. 226-236. [MR: 727660] [Zbl: 0523.68068]
  13. 12. G. GOODRICH, R. LADNER and M. FISCHER, Straight-line Programs to Compute Finite Languages, Conf. Theor. Comp. Sci., Waterloo, 1977. [MR: 502232] [Zbl: 0409.68025]
  14. 13. M. HARRISON, Introduction to Switching and Automata Theory, McGraw Hill, New York, 1965. [MR: 186503] [Zbl: 0196.51702]
  15. 14. J. HOPCROFT, W. PAUL and L. VALIANT, On Time Versus Space and Related Problems, Journal ACM, Vol. 2, 1977, pp. 332-337. [MR: 443428] [Zbl: 0358.68082]
  16. 15. J. HOPCROFT and J. ULLMAN, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading (Mass.), 1979. [MR: 645539] [Zbl: 0426.68001]
  17. 16. R. KARP and R. LIPTON, Some Connections between Nonuniform and Uniform Complexity Classes. In: 12th ACM Symp. Th. of Comp., 1980, pp. 302-309.
  18. 17. D. KNUTH, Big Omicron and Big Omega and Big Theta, SIGACT News, Apr.-June 1976, pp. 18-24.
  19. 18. R. LADNER, The Circuit Value Problem is Log Space Completefor P, SIGACT News, January 1975, pp. 18-20.
  20. 19. W. Ruzzo, J. SIMON and M. TOMPA, Space-bounded Hierarchies and Probabilistic Computations, J. Comp. Syst. Sci., Vol. 28, 1984, pp. 216-230. [MR: 760544] [Zbl: 0573.68021]
  21. 20. J. SAVAGE, The Complexity of Computing, Wiley Interscience 1976. [MR: 495205] [Zbl: 0391.68025]
  22. 21. C. SCHNORR, The Network Complexity and the Turing Machine Complexity of Finite Functions, Acta Informática, Vol. 7, 1976, pp. 95-107. [MR: 421889] [Zbl: 0338.02019]
  23. 22. M. J. SERNA, Asymptotical Behaviour of Some Non-Uniform Measures, Inf. Théor. et Appl., (to appear). [EuDML: 92335] [Zbl: 0677.68086]
  24. 23. P. VITANYI and L. MEERTENS, Big Omega Versus the Wild Functions, Bull. EATCS, 22 Feb. 1984, pp. 14-19.
  25. 24. I. WEGENER, On the Complexity of Branching Programs and Decision Trees for Clique Functions, Journal ACM, Vol. 35, 1988, pp. 461-471. [MR: 935261] [Zbl: 0652.68063]

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.