Some periodicity of words and Marcus contextual grammars (Q873801)

From MaRDI portal





scientific article; zbMATH DE number 5135222
Language Label Description Also known as
English
Some periodicity of words and Marcus contextual grammars
scientific article; zbMATH DE number 5135222

    Statements

    Some periodicity of words and Marcus contextual grammars (English)
    0 references
    0 references
    0 references
    0 references
    20 March 2007
    0 references
    A word \(u\) is quasi-periodic if, for some word \(v\neq u\), each position in \(u\) is covered by some factor \(v\) of \(u\); it is hyper-primitive if it is not quasi-periodic. The authors prove in a simple way that the language of all hyper-primitive words can be described by a Marcus external contextual grammar with choice. No motivation is given for the research. Analogous results for the languages of primitive and strongly primitive words are quoted from [\textit{P. Dömösi, M. Ito} and \textit{S. Marcus}, ``Marcus contextual languages consisting of primitive words'', Discrete Math. (to appear)], which I was not able to find.
    0 references
    periodicity of words
    0 references
    Marcus contextual grammar
    0 references
    quasi-periodic
    0 references
    hyper-primitive
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references