Automaticity of Primitive Words and Irreducible Polynomials
MetadataShow full item record
Lacroix, Anne, and Narad Rampersad. “Automaticity of primitive words and irreducible polynomials.” Discrete Mathematics and Theoretical Computer Science 15(1) (2013): 29-36.
If L is a language, the automaticity function AL(n) (resp. NL(n)) of L counts the number of states of a smallest deterministic (resp. non-deterministic) finite automaton that accepts a language that agrees with L on all inputs of length at most n. We provide bounds for the automaticity of the language of primitive words and the language of unbordered words over a k-letter alphabet. We also give a bound for the automaticity of the language of base-b representations of the irreducible polynomials over a finite field. This latter result is analogous to a result of Shallit concerning the base-k representations of the set of prime numbers.