Concatenation-free languages

• Published in: Theoretical computer science 2017-05, Vol.679, p.83-94
• Main Authors: Kutrib, Martin, Wendlandt, Matthias
• Format: Article
• Language: English
• Subjects: Characterizations; Closure properties; Concatenation-free languages; Expressive capacity; Regular expressions; Subregular hierarchy
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2016.08.014

The expressive capacity of three different types of regular expressions without concatenation is studied. In particular, we consider alphabetic concatenation-free expressions, which are ordinary regular expressions without concatenation, simple concatenation-free expressions, where the set of literals is a finite set of words instead of letters, and concatenation-free expressions, where additionally complementation operations are possible. Characterizations of the corresponding language classes are obtained. In particular, a characterization of unary concatenation-free languages by the Boolean closure of certain sets of languages is shown. The characterizations are then used to derive a strict hierarchy that is, in turn, strictly included in the family of regular languages. The closure properties of the families are investigated. Furthermore, the position of the family of concatenation-free languages in the subregular hierarchy is considered and settled for the unary case. In particular, there are concatenation-free languages that do not belong to any of the families in the hierarchy. Moreover, except for comets, all the families considered in the subregular hierarchy are strictly included in the family of concatenation-free languages.