ในทางคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีลำดับk -synchronizedคือลำดับอนันต์ของเทอมs ( n ) ที่มีลักษณะเฉพาะโดยออโตมาตาจำกัดซึ่งรับอินพุตเป็นสตริงสองสตริงmและnโดยแต่ละสตริงแสดงอยู่ในฐานk ที่กำหนดไว้ และยอมรับก็ต่อเมื่อm  =  s ( n ) เท่านั้น คลาสของ ลำดับ k -synchronized อยู่ระหว่างคลาสของลำดับk -automatic และลำดับk - regular

ให้ Σ เป็นตัวอักษรkตัว โดยที่k  ≥ 2 และให้ [ n ] _kแทนการแทนฐานkของจำนวนn บางจำนวน เมื่อกำหนดr  ≥ 2 เซตย่อยRของ Σ ∗ จะ ถูกซิงโครไนซ์ด้วย kถ้าความสัมพันธ์ {([ n ₁ ] _k , ..., [ n _r ] _k )} เป็น ความสัมพันธ์เชิงตรรกะแบบซิงโครไนซ์ทางขวา^{[ 1 ]}เหนือ Σ ^{∗ ×}  ... × Σ ^∗โดยที่ ( n ₁ , ..., n _r ) R [ ^{2 ]}${\displaystyle \mathbb {N} ^{r}}$${\displaystyle \in }$

ให้n  ≥ 0 เป็นจำนวนธรรมชาติและให้f : เป็นฟังก์ชันที่ทั้งnและf ( n ) แสดงอยู่ในฐานkลำดับf ( n ) จะ ถูกซิงโครไนซ์ด้วยฐาน kถ้าภาษาของคู่ลำดับนั้นเป็นภาษา ปกติ${\displaystyle \mathbb {N} \rightarrow \mathbb {N} }$${\displaystyle \{(n,f(n))\}}$

กลุ่ม ลำดับ k-ซิงโครไนซ์ได้รับการแนะนำโดย Carpi และ Maggi ^{[ 2 ]}

กำหนดลำดับอัตโนมัติk ตัว s ( n ) และสตริงอนันต์S  =  s (1) s (2)... ให้ ρS ₍ n) แทนความซับซ้อนของคำย่อยของSนั่นคือ จำนวนคำย่อย ที่แตกต่างกัน ที่มีความยาวnในS Goč, Schaeffer และ Shallit ^{[ 3 ]}แสดงให้เห็นว่ามีออโตมาตาจำกัดที่ยอมรับภาษา

${\displaystyle \{(n,m)_{k}\mid n\geq 0{\text{ และ }}m=\rho _{S}(n)\}.}$

ออโตมาตอนตัวนี้คาดเดาจุดสิ้นสุดของบล็อกสัญลักษณ์ที่ต่อเนื่องกันทุกบล็อกในSและตรวจสอบว่าคำย่อยแต่ละคำที่มีความยาวnซึ่งเริ่มต้นภายในบล็อกที่กำหนดนั้นเป็นคำใหม่ ในขณะที่คำย่อยอื่นๆ ทั้งหมดไม่ใช่คำใหม่ จากนั้นจะตรวจสอบว่าmเป็นผลรวมของขนาดของบล็อก เนื่องจากคู่ ( n ,  m ) _kได้รับการยอมรับโดยออโตมาตอนตัวนี้ฟังก์ชันความซับซ้อน ของคำย่อย ของ ลำดับอัตโนมัติ k ตัวs ( n ) จึง มี การซิง โครไนซ์k

ลำดับที่มีการซิงโครไนซ์ kมีคุณสมบัติที่น่าสนใจหลายประการ รายการคุณสมบัติเหล่านี้ (แต่ไม่ครบถ้วน) แสดงไว้ด้านล่างนี้

• ลำดับที่ซิงโครไนซ์ kทุกลำดับเป็นแบบk-ปกติ^{[ 4 ]}
• ลำดับk- อัตโนมัติ ทุกตัวจะ ซิงโครไนซ์กับ kกล่าวคือ ลำดับs ( n ) จะเป็นk-อัตโนมัติก็ต่อเมื่อs ( n ) ซิง โครไนซ์กับ kและs ( n ) มีจำนวนเทอมจำกัด^{[ 5 ]}นี่เป็นผลสืบเนื่องโดยตรงจากคุณสมบัติข้างต้นและข้อเท็จจริงที่ว่า ลำดับ k-ปกติทุกตัวที่มีจำนวนเทอมจำกัดจะเป็นk-อัตโนมัติ
• คลาสของ ลำดับ k-ซิงโครไนซ์ปิดภายใต้ผลรวมเทอมและการประกอบเทอม^{[ 6 ] [ 7 ]}
• เงื่อนไขของลำดับk-ซิงโครไนซ์ใดๆ จะมีอัตราการเติบโตเชิงเส้น^{[ 8 ]}
• ถ้าs ( n ) เป็น ลำดับที่ซิงโครไน ซ์ kแล้วทั้งความซับซ้อนของคำย่อยของs ( n ) และความซับซ้อนของพาลินโดรมของs ( n ) (คล้ายกับความซับซ้อนของคำย่อย แต่สำหรับพาลินโดรม ที่แตกต่างกัน ) จะเป็นลำดับปกติk ^{[ 9 ]}