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 REGw, in fact, are regular languages that are the same as their cyclic permutations. Strongly accepted circular word languages, REGs, having words with the property that all their conjugates are also in the language, are also regular. We prove that REGw and REGs coincide. We also provide regular-like expressions for these languages. Closure properties of this class are also investigated.

Keywords

• circular words
• conjugate class
• cyclic words
• regular expressions
• finite automata
• weak and strong acceptance