A Class of Automatic Sequences

2017/12/29 by Rigo, Michel, Underwood, Robert
#68Q45 #68Q70 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1712.10259

Abstract

Let k≥ 2. We prove that the characteristic sequence of a regular language over a k-letter alphabet is k-automatic. More generally, if t≥ 2 and t,k are multiplicatively dependent, we show that the characteristic sequence of a regular language over a t-letter alphabet is k-automatic.

Related

• Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences
• Generalization of automatic sequences for numeration systems on a regular language
• Periodicity, repetitions, and orbits of an automatic sequence
• Enumeration and Decidable Properties of Automatic Sequences
• On asymptotically automatic sequences