A note on the equivalence and complexity of linear grammars

DOI10.1023/A:1026142613465zbMath1081.68041MaRDI QIDQ1430207

Jose M. Sempere

Publication date: 27 May 2004

Published in: Grammars (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexityformal languageslinear grammarsequivalence propertiesreversal complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Grammars and rewriting systems (68Q42)

Related Items (1)

On deterministic 1-limited 5′ → 3′ sensing Watson–Crick finite-state transducers

This page was built for publication: A note on the equivalence and complexity of linear grammars