Skip to Main content Skip to Navigation
Journal articles

Automaticity of primitive words and irreducible polynomials

Abstract : If L is a language, the automaticity function A_L(n) (resp. N_L(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.
Document type :
Journal articles
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990604
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 4:28:47 PM
Last modification on : Thursday, September 7, 2017 - 1:03:37 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:45:13 PM

File

2006-7665-1-PB.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Anne Lacroix, Narad Rampersad. Automaticity of primitive words and irreducible polynomials. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.29--36. ⟨10.46298/dmtcs.632⟩. ⟨hal-00990604⟩

Share

Metrics

Record views

82

Files downloads

924