PublicationsManuscripts

Vincenzo Ciancia asked on cstheory.stackexchange about the class of regular languages satisfying the following property: whenever a word $w$ belongs to the language, all of its positive powers $w^k$ also belong to the language. He termed these languages ‘circular languages’. Answering his question, we have shown the following:

• Every circular language can be written as the union of expressions $r^+$. We exhibit a language where this union cannot be disjoint.
• Given a DFA for a regular language, it is PSPACE-complete to decide whether the language is circular.

The normal form appears in a paper by Calbrix and Nivat, and the PSPACE-completeness result follows quite easily from a paper by Kozen, as I detail in my answer. My proofs appear below.