Testing primitivity on partial words

Primitive words, or strings over a finite alphabet that cannot be written as a power of another string, play an important role in numerous research areas including formal language theory, coding theory, and combinatorics on words. Testing whether or not a word is primitive can be done in linear time...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2007-02, Vol.155 (3), p.279-287
Main Authors: Blanchet-Sadri, F., Anavekar, Arundhati R.
Format: Article
Language:English
Subjects:
Algorithm
Algorithmics. Computability. Computer arithmetics
Applied sciences
Combinatorics
Combinatorics on words
Combinatorics. Ordered structures
Compatibility
Computer science
control theory
systems
Designs and configurations
Exact sciences and technology
Language theory and syntactical analysis
Mathematics
Partial words
Primitive partial words
Primitive words
Sciences and techniques of general use
Special partial words
Theoretical computing
Words
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Primitive words, or strings over a finite alphabet that cannot be written as a power of another string, play an important role in numerous research areas including formal language theory, coding theory, and combinatorics on words. Testing whether or not a word is primitive can be done in linear time in the length of the word. Indeed, a word is primitive if and only if it is not an inside factor of its square. In this paper, we describe a linear time algorithm to test primitivity on partial words which are strings that may contain a number of “do not know” symbols. Our algorithm is based on the combinatorial result that under some condition, a partial word is primitive if and only if it is not compatible with an inside factor of its square. The concept of special, related to commutativity on partial words, is foundational in the design of our algorithm. A World Wide Web server interface at http://www.uncg.edu/mat/primitive/ has been established for automated use of the program.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2006.07.001