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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Subregular Expressions with Two Operations

  • Martin Kutrib,
  • Priscilla Raucci,
  • Matthias Wendlandt

摘要

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.