The infinite 2-star height hierarchy of extended regular languages of star degree at most two
type: Item
instance of: scholarly article
title: The infinite 2-star height hierarchy of extended regular languages of star degree at most two
zbMATH Open document ID: 0852.68044
author: Kosaburo Hashiguchi
published in: Information and Computation
publication date: 1995-01-11T00:00:00Z
review text: The concept of regular expressions and their equivalence to regular languages is well-known. The operation of 2-star (an extension of Kleene star as used in regular expressions), and the corresponding class of extended regular expressions, were introduced by the author and H. Yoo in 1990. The extended regular expressions define a superclass of regular languages and a proper subclass of context-free languages. In this paper the author defines the concept of 2-star height (again, in analogy to star height of regular expressions), and proves that the resulting height-hierarchy is infinite.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 708750
zbMATH Keywords: regular expressions
zbMATH Keywords: regular languages
zbMATH Keywords: 2-star height
reviewed by: Giora Slutzki
MaRDI profile type: Publication
full work available at URL: inco.1994.1087
OpenAlex ID: W2046008802
DOI: 10.1006/INCO.1994.1087
description: scientific article; zbMATH DE number 708750