On the length of word chains

DOI10.1016/0020-0190(87)90031-7zbMath0654.68096OpenAlexW2028460486MaRDI QIDQ1108812

Srečko Brlek, Jean Berstel

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90031-7

zbMATH Keywords

addition chainsD0L-systemsword chain

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (10)

Constructing small tree grammars and small circuits for formulas ⋮ A note on word chains and regular languages ⋮ Tight lower bounds on the length of word chains ⋮ Processor-efficient exponentiation in finite fields ⋮ Efficient and optimal exponentiation in finite fields ⋮ The number of minimal word chains computing the Thue-Morse word ⋮ Asymptotical behaviour of some non-uniform measures ⋮ Optimal word chains for the Thue-Morse word ⋮ Approximation ratios of \textsf{RePair}, \textsf{LongestMatch} and \textsf{Greedy} on unary strings ⋮ Simulating finite automata with context-free grammars.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the length of word chains