Optimal word chains for the Thue-Morse word

DOI10.1016/0890-5401(89)90056-4MaRDI QIDQ582129zbMATH OpenOpenAlexFDO

Authors André Arnold, Srečko Brlek

Publication date 1989

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(89)90056-4

zbMATH Keywords

complexity measure for languagesWord chains

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The number of minimal word chains computing the Thue-Morse word
• On the longest common subsequence of Thue-Morse words
• On the length of word chains
• A note on word chains and regular languages
• Tight lower bounds on the length of word chains

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• Enumeration of factors in the Thue-Morse word
• On the length of word chains

Cited in

(6)

• Tight lower bounds on the length of word chains
• A note on word chains and regular languages
• On the length of word chains
• The number of minimal word chains computing the Thue-Morse word
• On Bellman's and Knuth's problems and their generalizations
• Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits

This page was built for publication: Optimal word chains for the Thue-Morse word

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