• English
    • français
  • English 
    • English
    • français
View Item 
  •   WinnSpace Home
  • Department of Mathematics and Statistics
  • Narad Rampersad
  • View Item
  •   WinnSpace Home
  • Department of Mathematics and Statistics
  • Narad Rampersad
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Automaticity of Primitive Words and Irreducible Polynomials

Thumbnail

View Open

Automaticity of primitive words and irreducible polynomials.pdf (257.3Kb)

Metadata

Show full item record

Author

Lacroix, Anne
Rampersad, Narad

Uri

http://hdl.handle.net/10680/1409

Date

2013

Citation

Lacroix, Anne, and Narad Rampersad. “Automaticity of primitive words and irreducible polynomials.” Discrete Mathematics and Theoretical Computer Science 15(1) (2013): 29-36.

Abstract

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.

Collections

  • Narad Rampersad

Report a copyright concern

Contact Us | Send Feedback
 

 

Browse

All of WinnSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister

Report a copyright concern

Contact Us | Send Feedback