×
Serna, Maria José

Asymptotical behaviour of some non-uniform measures. (English) Zbl 0677.68086

RAIRO, Inf. Théor. Appl. 23, No. 3, 281-293 (1989).
Summary: We show the existence of the Shannon effect for some well-known non- uniform measures such as regular complexity, initial index and context- free cost. We also obtain the asymptotical behaviour of the hardest finite languages for these measures.

Cited in 1 Document

MSC:

68Q45 Formal languages and automata
03D15 Complexity of computation (including implicit computational complexity)
94A17 Measures of information, entropy

Keywords:

non-uniform measures; Shannon effect; hardest finite languages
PDF BibTeX XML Cite
\textit{M. J. Serna}, RAIRO, Inform. Théor. Appl. 23, No. 3, 281--293 (1989; Zbl 0677.68086)
Full Text: DOI EuDML

References:

[1] J. L. BALCAZAR, J. DIAZ and J. GABARRO, Uniform Characterizations of Non-Uniform Measures, Inf. and Cont., Vol. 67, 1985, pp. 53-69. Zbl0588.68021 MR833860 · Zbl 0588.68021
[2] J. BERSTEL and S. BRLEK, On the Length of Word Chains, I.P.L., Vol. 26, 1987, pp. 23-28. Zbl0654.68096 MR908568 · Zbl 0654.68096
[3] W. BUCHER, K. CULIK, H. MAURER and D. WOTSCHKE, Concise Description of Finite Languages, Theor. Comp. Sci., Vol. 14, 1981, pp. 227-246. Zbl0469.68081 MR619000 · Zbl 0469.68081
[4] 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.25301 MR210520 · Zbl 0158.25301
[5] A. EHRENFEUCHT and P. ZEIGER, Complexity Measures for Regular Expressions, J. Comp. and Sys. Sci., Vol. 12, No. 2, 1976, pp. 134-146. Zbl0329.94024 MR418509 · Zbl 0329.94024
[6] 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.68047 MR666770 · Zbl 0485.68047
[7] 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.68068 MR727660 · Zbl 0523.68068
[8] G. GOODRICH, R. LADNER and M. FISHER, Straight Line Programs to Compute Finite Languages, Conf. on Theor. Comp. Sci., Waterloo, 1977. Zbl0409.68025 · Zbl 0409.68025
[9] 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.94025 MR775178 · Zbl 0551.94025
[10] O. B. LUPANOV, A Method of Circuit Synthesis, Izv. V.U.Z. Radiofiz, Vol. 1, 1958, pp. 120-140. · Zbl 0081.20902
[11] O. B. LUPANOV, Complexity of Formula Realization of Functions of Logical Algebra, Prob. Kibern., Vol. 3, 1962, pp. 782-811.
[12] O. B LUPANOV, On Circuits of Functional Elements with Delay, Problems of Cybernetics [in Russian], Vol. 23, 1970, pp. 43-81. Zbl0267.94037 MR332361 · Zbl 0267.94037
[13] 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. · Zbl 0256.94044
[14] 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] L. J. STOCKMEYER, Classifying the computational Complexity of Problems, M.I.T. Research Report R.C. 7606, 1979. · Zbl 0444.94037
[16] 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] I. WEGENER, The Complexity of Boolean Functions, Wiley-Teubner, 1987. Zbl0623.94018 MR905473 · Zbl 0623.94018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.