EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 23 / No 2 (1989) RAIRO-Theor. Inf. Appl., 23 2 (1989) 177-194 References
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] [Google Scholar]
  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] [Google Scholar]
  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. [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  7. 7. R. CASAS and J. GABARRO, About LOG-ON languages, Internal report RR 85/02, Facultat d'Informàtica de Barcelona. [Google Scholar]
  8. 8. M. CHYTIL, Almost context-free languages, Manuscript, 1984. [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  11. 11. J. GABARRÓ Funciones de complejidad y su relación con las familias abstractas de lenguajes. Ph. D. dissertation, 1983. [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  14. 13. M. HARRISON, Introduction to Switching and Automata Theory, McGraw Hill, New York, 1965. [MR: 186503] [Zbl: 0196.51702] [Google Scholar]
  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] [Google Scholar]
  16. 15. J. HOPCROFT and J. ULLMAN, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading (Mass.), 1979. [MR: 645539] [Zbl: 0426.68001] [Google Scholar]
  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. [Google Scholar]
  18. 17. D. KNUTH, Big Omicron and Big Omega and Big Theta, SIGACT News, Apr.-June 1976, pp. 18-24. [Google Scholar]
  19. 18. R. LADNER, The Circuit Value Problem is Log Space Completefor P, SIGACT News, January 1975, pp. 18-20. [Google Scholar]
  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] [Google Scholar]
  21. 20. J. SAVAGE, The Complexity of Computing, Wiley Interscience 1976. [MR: 495205] [Zbl: 0391.68025] [Google Scholar]
  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] [Google Scholar]
  23. 22. M. J. SERNA, Asymptotical Behaviour of Some Non-Uniform Measures, Inf. Théor. et Appl., (to appear). [EuDML: 92335] [Zbl: 0677.68086] [Google Scholar]
  24. 23. P. VITANYI and L. MEERTENS, Big Omega Versus the Wild Functions, Bull. EATCS, 22 Feb. 1984, pp. 14-19. [Google Scholar]
  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] [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.