Journal article

Publication year: 2017

Pages: 83-94

Journal: Theoretical Computer Science

Volume number: 679

ISSN: 0304-3975

eISSN: 1879-2294

Open access status: Bronze

DOI Link: https://doi.org/10.1016/j.tcs.2016.08.014

Publisher: Elsevier

Abstract: 
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. (C) 2016 Elsevier B.V. All rights reserved.

Harvard Citation style: Kutrib, M. and Wendlandt, M. (2017) Concatenation-free languages, Theoretical Computer Science, 679, pp. 83-94. https://doi.org/10.1016/j.tcs.2016.08.014

APA Citation style: Kutrib, M., & Wendlandt, M. (2017). Concatenation-free languages. Theoretical Computer Science. 679, 83-94. https://doi.org/10.1016/j.tcs.2016.08.014