scientific article; zbMATH DE number 3972211

From MaRDI portal
Publication:3738577





[For the entire collection see Zbl 0563.00018.] The authors are interested in those strings generated by context-free grammars containing nonempty substrings which are immediately repeated (e.g. aa, abab). Such a string is called a square. A string containing a substring which is a square is called square-containing (a string without squares is called squarefree). First, the construction of a context-free language with an infinite strongly-cubefree complement is summarized (a cube consists of three consecutive occurrences of a nonempty string; a string is called cubefree if no substring is a cube, and it is called strongly cubefree if it has no substring of the form xxa where x is a nonempty string and a is the first character of x). Using this result, together with closure properties, the construction of a context-free language with an infinite squarefree complement is discussed. In the last section some applications and open problems are presented.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3738577)