Subregular Expressions with Two Operations

Martin Kutrib

doi:10.1007/978-3-032-01475-7_16

Return

Subregular Expressions with Two Operations

2026-01-01

PRE

Martin Kutrib *

Priscilla Raucci

Matthias Wendlandt

DOI：10.1007/978-3-032-01475-7_16

Original

Save

Abstract

En 中文

Subregular expressions are closely related to regular expressions, but instead of relying solely on the classical operations of union, concatenation, and Kleene star, they explore subsets of operations under which regular languages remain closed. Previous work has examined various combinations of these operations, including complement and intersection, alongside the standard trio. In this work, we investigate several unexplored combinations of operations, focusing specifically on three language families, namely, subregular expressions with complement and Kleene star, subregular expressions with concatenation and complement, and subregular expressions with intersection and Kleene star. We examine basic properties of these families of languages and analyze how these families relate to each other. Further, we distinguish between the unary and general alphabet cases, and explore the possibility of a hierarchical structure based on the number of operations used.

Keywords:

LANGUAGES