Subword complexity and k-synchronization
From MaRDI portal
Publication:5300845
DOI10.1007/978-3-642-38771-5_23zbMATH Open1381.68234arXiv1206.5352OpenAlexW1768688475MaRDI QIDQ5300845FDOQ5300845
Authors: Daniel Goč, Luke Schaeffer, Jeffrey Shallit 
Publication date: 28 June 2013
Published in: Developments in Language Theory (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1206.5352
Recommendations
Cited In (16)
- Additive number theory via automata theory
- General framework
- On factors of synchronized sequences
- Title not available (Why is that?)
- Decision algorithms for Fibonacci-automatic words. III: Enumeration and abelian properties.
- Mechanical proofs of properties of the Tribonacci word
- How to prove that a sequence is not automatic
- First-order logic and numeration systems
- Dyck Words, Pattern Avoidance, and Automatic Sequences
- Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences
- Synchronized sequences
- Automatic sequences of rank two
- Counting the number of non-zero coefficients in rows of generalized Pascal triangles
- On synchronized sequences and their separators
- Abelian complexity and synchronization
- Proof of a conjecture of Krawchuk and Rampersad on the cyclic complexity of the Thue-Morse sequence
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)
