Automaticity of primitive words and irreducible polynomials - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2013

Automaticity of primitive words and irreducible polynomials

Résumé

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.
Fichier principal
Vignette du fichier
2006-7665-1-PB.pdf (240.44 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00990604 , version 1 (13-05-2014)

Identifiants

Citer

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

Collections

TDS-MACS
87 Consultations
1126 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More