On Concatenations of Regular Circular Word Languages

Abstract

In this paper, one-wheel and two-wheel concatenations of circular words and their languages are investigated. One-wheel concatenation is an operation that is commutative but not associative, while two-wheel concatenation is associative but not commutative. Moreover, two-wheel concatenation may produce languages that are not languages of circular words. We define two classes of regular languages of circular words based on finite automata: in a weakly accepted circular word language, at least one conjugate of each word is accepted by the automaton; in contrast, a strongly accepted language consists of words for which all conjugates are accepted. Weakly accepted circular word languages ${REG}_w$, in fact, are regular languages that are the same as their cyclic permutations. Strongly accepted circular word languages, ${REG}_s$, having words with the property that all their conjugates are also in the language, are also regular. We prove that ${REG}_w$ and ${REG}_s$ coincide. We also provide regular-like expressions for these languages. Closure properties of this class are also investigated.