Asymptotical behaviour of some non-uniform measures

Maria José Serna

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1989)

  • Volume: 23, Issue: 3, page 281-293
  • ISSN: 0988-3754

How to cite

top

Serna, Maria José. "Asymptotical behaviour of some non-uniform measures." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 23.3 (1989): 281-293. <http://eudml.org/doc/92335>.

@article{Serna1989,
author = {Serna, Maria José},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {non-uniform measures; Shannon effect; hardest finite languages},
language = {eng},
number = {3},
pages = {281-293},
publisher = {EDP-Sciences},
title = {Asymptotical behaviour of some non-uniform measures},
url = {http://eudml.org/doc/92335},
volume = {23},
year = {1989},
}

TY - JOUR
AU - Serna, Maria José
TI - Asymptotical behaviour of some non-uniform measures
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1989
PB - EDP-Sciences
VL - 23
IS - 3
SP - 281
EP - 293
LA - eng
KW - non-uniform measures; Shannon effect; hardest finite languages
UR - http://eudml.org/doc/92335
ER -

References

top
  1. [Ba, Di, Ga, 85] J. L. BALCAZAR, J. DIAZ and J. GABARRO, Uniform Characterizations of Non-Uniform Measures, Inf. and Cont., Vol. 67, 1985, pp. 53-69. Zbl0588.68021MR833860
  2. [Be, Br] J. BERSTEL and S. BRLEK, On the Length of Word Chains, I.P.L., Vol. 26, 1987, pp. 23-28. Zbl0654.68096MR908568
  3. [Bu, Cu, Ma, Wo, 81] W. BUCHER, K. CULIK, H. MAURER and D. WOTSCHKE, Concise Description of Finite Languages, Theor. Comp. Sci., Vol. 14, 1981, pp. 227-246. Zbl0469.68081MR619000
  4. [Ch, 66] G. J. CHAITIN, On the Length of Programs for Compute Finite Binary Sequences, Jour. A. C. M., Vol. 13, No. 4, 1966, pp. 547-569. Zbl0158.25301MR210520
  5. [Eh, Ze, 74] A. EHRENFEUCHT and P. ZEIGER, Complexity Measures for Regular Expressions, J. Comp. and Sys. Sci., Vol. 12, No. 2, 1976, pp. 134-146. Zbl0329.94024MR418509
  6. [F1, U11, 82] R. FLOYD and J. ULLMAN, The Compilation of Regular Expressions into Integrated Circuits, Jour. A. C. M., Vol. 29, No. 2, 1982, pp. 603-622. Zbl0485.68047MR666770
  7. [Ga, 83] J. GABARRO, Initial Index : a New Complexity Function for languages, I. C. A. L. P. 83 L. N. C. S. 154, Springer-Verlag, 1983, pp. 226-236. Zbl0523.68068MR727660
  8. [Go, La, Fi, 77] G. GOODRICH, R. LADNER and M. FISHER, Straight Line Programs to Compute Finite Languages, Conf. on Theor. Comp. Sci., Waterloo, 1977. Zbl0409.68025
  9. [Kr, Le, 84] M. R. KRAMER and J. VAN LEEUWEN, The VLSI Complexity of Boolean Functions, L.N.C.S. 171, Springer-Verlag, 1984, pp. 397-407. Zbl0551.94025MR775178
  10. [Lu, 58] O. B. LUPANOV, A Method of Circuit Synthesis, Izv. V.U.Z. Radiofiz, Vol. 1, 1958, pp. 120-140. 
  11. [Lu, 62] O. B. LUPANOV, Complexity of Formula Realization of Functions of Logical Algebra, Prob. Kibern., Vol. 3, 1962, pp. 782-811. 
  12. [Lu, 70] O. B LUPANOV, On Circuits of Functional Elements with Delay, Problems of Cybernetics [in Russian], Vol. 23, 1970, pp. 43-81. Zbl0267.94037MR332361
  13. [Ne, 65] E. I. NECHIPORUK, On the Design of Logical Networks in Incomplete and Degenerate Bases, Problems of Cybernetics [in Russian], Vol. 14, 1965, pp. 111-160. 
  14. [Ri, Sha, 42] J. RIORDAN and C. E. SHANNON, The Number of Two-Terminals Series Parallel Networks, J. on Math. Phys., Vol. 21, 1942, pp. 83-93. MR7511
  15. [Sto, 79] L. J. STOCKMEYER, Classifying the computational Complexity of Problems, M.I.T. Research Report R.C. 7606, 1979. 
  16. [Ug, 76] A. B. UGOLNIKOV, On the Realization of Monotone Functions by Circuits of Functional Elements, Problems of Cybernetics [in Russian], Vol. 31, 1976, pp. 167-185. MR421891
  17. [We, 87] I. WEGENER, The Complexity of Boolean Functions, Wiley-Teubner, 1987. Zbl0623.94018MR905473

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.