Subword complexity and k-synchronization

DOI10.1007/978-3-642-38771-5_23MaRDI QIDQ5300845zbMATH OpenOpenAlexFDO

Authors Daniel Goč, Luke Schaeffer, Jeffrey Shallit

Publication date 28 June 2013

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.5352

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: We show that the subword complexity function p_x(n), which counts the number of distinct factors of length n of a sequence x, is k-synchronized in the sense of Carpi if x is k-automatic. As an application, we generalize recent results of Goldstein. We give analogous results for the number of distinct factors of length n that are primitive words or powers. In contrast, we show that the function that counts the number of unbordered factors of length n is not necessarily k-synchronized for k-automatic sequences.

Recommendations

• On factors of synchronized sequences
• Abelian complexity and synchronization
• Reconnaissabilité des substitutions et complexité des suites automatiques
• Automata calculating the complexity of automatic sequences
• Synchronized sequences

Cited in

(16)

• Synchronized sequences
• On synchronized sequences and their separators
• Abelian complexity and synchronization
• How to prove that a sequence is not automatic
• Proof of a conjecture of Krawchuk and Rampersad on the cyclic complexity of the Thue-Morse sequence
• Dyck Words, Pattern Avoidance, and Automatic Sequences
• On factors of synchronized sequences
• Additive number theory via automata theory
• Mechanical proofs of properties of the Tribonacci word
• scientific article; zbMATH DE number 6606363 (Why is no real title available?)
• First-order logic and numeration systems
• Automatic sequences of rank two
• Counting the number of non-zero coefficients in rows of generalized Pascal triangles
• Decision algorithms for Fibonacci-automatic words. III: Enumeration and abelian properties.
• Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences
• General framework

This page was built for publication: Subword complexity and \(k\)-synchronization

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