Conference paper

Publication year: 2018

Pages: 201-218

Journal: RAIRO: Theoretical Informatics and Applications

Volume number: 52

Issue number: 2-4

ISSN: 0988-3754

eISSN: 1290-385X

Open access status: Green

DOI Link: https://doi.org/10.1051/ita/2018014

Conference: 8th Workshop on Non-Classical Models of Automata and Applications (NCMA)

Publisher: EDP Sciences

Abstract: 
Different types of subregular expressions are studied. Each type is obtained by either omitting one of the regular operations or replacing it by complementation or intersection. For uniformity and in order to allow non-trivial languages to be expressed, the set of literals is a finite set of words instead of letters. The power and limitations as well as relations with each other are considered, which is often done in terms of unary languages. Characterizations of some of the language families are obtained. A finite hierarchy is shown that reveals that the operation complementation is generally stronger than intersection. Furthermore, we investigate the closures of language families described by regular expressions with omitted operation under that operation. While it is known that in case of union this closure captures all regular languages, for the cases of concatenation and star incomparability results are obtained with the corresponding language families where the operation is replaced by complementation.

Harvard Citation style: Kutrib, M. and Wendlandt, M. (2018) EXPRESSIVE CAPACITY OF SUBREGULAR EXPRESSIONS, RAIRO: Theoretical Informatics and Applications, 52(2-4), pp. 201-218. https://doi.org/10.1051/ita/2018014

APA Citation style: Kutrib, M., & Wendlandt, M. (2018). EXPRESSIVE CAPACITY OF SUBREGULAR EXPRESSIONS. RAIRO: Theoretical Informatics and Applications. 52(2-4), 201-218. https://doi.org/10.1051/ita/2018014