On asymptotic estimates of the complexity of circuit realization of languages
From MaRDI portal
Publication:2563374
The author introduces a) the notion of complexity for the words in the alphabet \(B=\{ 0,1 \}\) analogously to the case of Boolean functions, and b) Shannon's function for sets of words, i. e. languages. Then the asymptotic equality of the Snannon's function to its lower bound is shown under some sufficient conditions. If the asymptotic equality is true the language is called standard. Sufficient conditions are given for a language to be standard, and two types of languages are shown to be standard.
Recommendations
- On the complexity of realization of finite languages by formulas
- Complexity of monotonic functions
- Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits
- Asymptotic behavior of the Shannon function for a class of circuits of functional elements.
- Refined bounds on Shannon's function for complexity of circuits of functional elements
Cited in
(7)- On the relative complexity of some languages in \(NC^ 1\)
- Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits
- Asymptotical behaviour of some non-uniform measures
- scientific article; zbMATH DE number 18343 (Why is no real title available?)
- On the complexity of realization of finite languages by formulas
- Circuit complexity and the expressive power of generalized first-order formulas
- Generalised Entropy and Asymptotic Complexities of Languages
This page was built for publication: On asymptotic estimates of the complexity of circuit realization of languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2563374)
