Decision algorithms for Fibonacci-automatic words. II: Related sequences and avoidability

DOI10.1016/J.TCS.2016.10.005MaRDI QIDQ346252zbMATHOpenAlexFDO

Authors Chen Fei Du, Hamoon Mousavi, Luke Schaeffer, Eric Rowland, Jeffrey Shallit

Publication date 5 December 2016

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

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

zbMATH Keywords

automatic sequencefinite automatadecision procedurepalindromeavoidability in wordsFibonacci representation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15) Other number representations (11A67) Automata sequences (11B85)

Recommendations

• Decision algorithms for Fibonacci-automatic words. I: Basic results.
• Decision algorithms for Fibonacci-automatic words. III: Enumeration and abelian properties.
• scientific article; zbMATH DE number 4035171
• On abelian 2-avoidable binary patterns
• Avoidable patterns on two letters

Cites work

• scientific article; zbMATH DE number 1498637 (Why is no real title available?)
• scientific article; zbMATH DE number 3267414 (Why is no real title available?)
• scientific article; zbMATH DE number 3397597 (Why is no real title available?)
• scientific article; zbMATH DE number 2235059 (Why is no real title available?)
• scientific article; zbMATH DE number 3076700 (Why is no real title available?)
• A generalization of automatic sequences
• Arithmetic progressions in lacunary sets
• Avoiding squares and overlaps over the natural numbers
• Avoiding three consecutive blocks of the same size and same sum
• Complexity of the Fibonacci snowflake
• Decision algorithms for Fibonacci-automatic words. I: Basic results.
• Directed graphs and substitutions
• Fibonacci snowflakes
• Growth rate of binary words avoiding \(xxx^{R}\)
• On some generalizations of abelian power avoidability
• On the least number of palindromes contained in an infinite word
• On uniformly repetitive semigroups
• Pattern avoidability with involution
• Sequences on sets of four numbers
• Sequences with subword complexity \(2n\)
• Systems of Numeration
• Two infinite families of polyominoes that tile the plane by translation in two distinct ways
• Unary patterns with involution

Cited in

(10)

• Searching for Zimin patterns
• Additive number theory via automata theory
• Mechanical proofs of properties of the Tribonacci word
• Decision algorithms for Fibonacci-automatic words. I: Basic results.
• Involutive Fibonacci words
• Avoidability index for binary patterns with reversal
• Sumsets of Wythoff sequences, Fibonacci representation, and beyond
• Decision algorithms for Fibonacci-automatic words. III: Enumeration and abelian properties.
• scientific article; zbMATH DE number 7069796 (Why is no real title available?)
• Formulas with reversal

Describes a project that uses

Uses Software

• Walnut

This page was built for publication: Decision algorithms for Fibonacci-automatic words. II: Related sequences and avoidability

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