Coding by minimal linear grammars

DOI10.1016/J.TCS.2020.01.032MaRDI QIDQ2192369zbMATH OpenOpenAlexFDO

Authors Arturo Carpi, Flavio D'Alessandro

Publication date 17 August 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2020.01.032

zbMATH Keywords

Bernoulli distributioncoding theorycommutative equivalencecontext-free linear grammarinformation theorymaximal codeuniquely decipherable code

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)

Recommendations

• Efficient coding of formalized messages
• Grammatical codes of trees
• Properties of grammatical codes of trees
• Application of formal grammars for encoding information sources
• A note on binary grammatical codes of trees

Cites work

• A conjecture on continued fractions
• A counterexample to the triangle conjecture
• A Mathematical Theory of Communication
• A note on multiset decipherable codes
• Coding partitions
• Coding partitions of regular sets
• Completions in measure of languages and related combinatorial problems
• Counting bordered and primitive words with a fixed weight
• Decipherability of codes
• Each regular code is included in a maximal regular code
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3760085 (Why is no real title available?)
• scientific article; zbMATH DE number 3228255 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• Inherent ambiguity of minimal linear grammars
• Minimal complete sets of words
• On codes having no finite completions
• On multiset decipherable codes (Corresp.)
• On the commutative equivalence of bounded context-free and regular languages: the code case
• On the commutative equivalence of bounded context-free and regular languages: the semi-linear case
• On the commutative equivalence of context-free languages
• On the commutative equivalence of semi-linear sets of \(\mathbb{N}^k\)
• Some combinatorial results on Bernoulli sets and codes
• Some decompositions of Bernoulli sets and codes
• The undecidability of the ambiguity problem for minimal linear grammars
• Varieties of codes and Kraft inequality

Cited in

(6)

• On bounded linear codes and the commutative equivalence
• Relatively regular languages and thin codes
• The emergence of compositional grammars in artificial codes
• Bidirectional grammars for machine-code decoding and encoding
• On the Commutative Equivalence of Algebraic Formal Series and Languages
• On the commutative equivalence of algebraic structures and related problems

This page was built for publication: Coding by minimal linear grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2192369)