On the entropy of context-free languages
From MaRDI portal
Publication:5588670
DOI10.1016/S0019-9958(70)90105-1zbMath0193.32603OpenAlexW2042720934MaRDI QIDQ5588670
Publication date: 1970
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(70)90105-1
Related Items
Repetition-free words, Truncations of infinite matrices and algebraic series associated with some CF grammars, Lossiness of communication channels modeled by transducers1, Asymptotic Subword Complexity, Reduction of a class of Fox-Wright Psi functions for certain rational parameters, Natural halting probabilities, partial randomness, and zeta functions, Quantifying communication in synchronized languages, Valuations, regular expressions, and fractal geometry, Quantifying Communication in Synchronized Languages, Ein Satz über die Entropie von Untermonoiden. (A theorem on the entropy of submonoids), Information rate of some classes of non-regular languages: an automata-theoretic approach, Structural complexity of DNA sequence, Why We Need Semirings in Automata Theory (Extended Abstract), Security of Numerical Sensors in Automata, Compression and entropy, EDT0L grammars with only one variable have tractable generating functions, The characterization of parallel ultralinear grammars by rational power series, A note on the density of inherently ambiguous context-free languages, Execution information rate for some classes of automata, Groups, graphs, languages, automata, games and second-order monadic logic, Properties of structure generating functions of automata and their applications for linear systems, On the number of words in the language \(\{w \epsilon \Sigma^* | w=w^ r\}^ 2\), Exploring the topological entropy of formal languages, Combinatorial properties of the Hausdorff dimension, Growth-sensitivity of context-free languages., Context-free pairs of groups. II: Cuts, tree sets, and random walks, ON COMPUTING GEODESICS IN BAUMSLAG–SOLITAR GROUPS, Fractals, dimension, and formal languages, Valuations of languages, with applications to fractal geometry, FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME, A note on the ambiguity of context-free grammars, Dimension, entropy rates, and compression, Regular Language Distance and Entropy, Deciding regularity of hairpin completions of regular languages in polynomial time, On universal computably enumerable prefix codes, A definition of measures over language space, Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract), Definitions and properties of entropy and distance for regular languages, INFINITE ITERATED FUNCTION SYSTEMS IN CANTOR SPACE AND THE HAUSDORFF MEASURE OF ω-POWER LANGUAGES, Effective entropies and data compression, A contect-free language and enumeration problems on infinite trees and digraphs, On the inherent ambiguity of simple tuple languages, PREFIX-FREE ŁUKASIEWICZ LANGUAGES, Growth and ergodicity of context-free languages II: The linear case, Theory of formal grammars, Infinite linear systems and one counter languages, Entropy of generating series for nonlinear input-output systems and their interconnections, Sampling automata and programs, Even linear simple matrix languages: formal language properties and grammatical inference., Iterated function systems and control languages, Computation theory of cellular automata, On the growth of linear languages, Growth and ergodicity of context-free languages, Entropy rates and finite-state dimension
