WinnSpace Repository

Automaticity of Primitive Words and Irreducible Polynomials

Show simple item record

dc.contributor.author Lacroix, Anne
dc.contributor.author Rampersad, Narad
dc.date.accessioned 2018-03-16T14:27:01Z
dc.date.available 2018-03-16T14:27:01Z
dc.date.issued 2013
dc.identifier.citation Lacroix, Anne, and Narad Rampersad. “Automaticity of primitive words and irreducible polynomials.” Discrete Mathematics and Theoretical Computer Science 15(1) (2013): 29-36. en_US
dc.identifier.issn 1462-7264
dc.identifier.uri http://hdl.handle.net/10680/1409
dc.description.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. en_US
dc.description.uri https://hal.archives-ouvertes.fr/hal-00990604v1
dc.language.iso en en_US
dc.publisher Discrete Mathematics and Theoretical Computer Science en_US
dc.rights info:eu-repo/semantics/openAccess
dc.subject automaticity en_US
dc.subject primitive word
dc.subject unbordered word
dc.subject irreducible polynomial
dc.title Automaticity of Primitive Words and Irreducible Polynomials en_US
dc.type Article en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search WinnSpace


Advanced Search

Browse

My Account