Optimal word chains for the Thue-Morse word

DOI10.1016/0890-5401(89)90056-4zbMATH Open0689.68097OpenAlexW2092064035MaRDI QIDQ582129FDOQ582129

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

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

zbMATH Keywords

complexity measure for languagesWord chains

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Enumeration of factors in the Thue-Morse word
• On the length of word chains

Cited In (6)

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

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)