Deleting powers in words

DOI10.25596/JALC-2016-339zbMATH Open1380.68256arXiv1608.08689OpenAlexW2508205580MaRDI QIDQ4590912FDOQ4590912

Authors: John Machacek 

Publication date: 20 November 2017

Abstract: We consider the language consisting of all words such that it is possible to obtain the empty word by iteratively deleting powers. It turns out that in the case of deleting squares in binary words this language is regular, and in the case of deleting squares in words over a larger alphabet the language is not regular. However, for deleting squares over any alphabet we find that this language can be generated by a linear index grammar which is a mildly context sensitive grammar formalism. In the general case we show that this language is generated by an indexed grammar.

Full work available at URL: https://arxiv.org/abs/1608.08689

Recommendations

• On parallel deletions applied to a word
• Squares of regular languages
• scientific article; zbMATH DE number 465524
• State Complexity of Deletion
• Computing by commuting.

zbMATH Keywords

combinatorics on wordsformal languagesindexed grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Combinatorics on words (68R15)

Cited In (1)

• Computing by commuting.

This page was built for publication: Deleting powers in words

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