Extended regular expressions of star degree at most two
type: Item
instance of: scholarly article
title: Extended regular expressions of star degree at most two
zbMATH Open document ID: 0709.68023
DOI: 10.1016/0304-3975(90)90021-9
author: Kosaburo Hashiguchi
author: Heekeun Yoo
published in: Theoretical Computer Science
publication date: 1990-01-01T00:00:00Z
review text: The paper introduces the star operator of degree two, a generalization of Kleene star in regular expressions. One investigates the family of languages obtained by a finite number of operations of union, concatenation, Kleene star and star operator of degree two, starting from finite languages. This family is incomparable with those of linear languages and of deterministic context-free languages, and it is equal to the family of completely linearly nested context-free languages. Closure and decision properties of this family are examined, too.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 4166863
zbMATH Keywords: star operator
zbMATH Keywords: Kleene star
zbMATH Keywords: finite languages
zbMATH Keywords: context-free languages
reviewed by: Gheorghe Păun
describes a project that uses: ALGOL 60
MaRDI profile type: Publication
full work available at URL: 0304-3975(90)90021-9
OpenAlex ID: W2091689674
cites work: Q5576254
cites work: Two Families of Languages Related to ALGOL
cites work: Bounded Algol-Like Languages
cites work: The Unsolvability of the Recognition of Linear Context-Free Languages
cites work: Q4198075
cites work: Q3862379
Recommended article: Extended regular expressions of arbitrary star degrees
Recommended article: Extended automata-like regular expressions of star degree at most (2,1)
Recommended article: On Extended Regular Expressions
Recommended article: On Average Behaviour of Regular Expressions in Strong Star Normal Form
Recommended article: Regular expression star-freeness is PSPACE-complete
Recommended article: Q4382097
Recommended article: Extended regular expressions: succinctness and decidability
Recommended article: Extended Regular Expressions: Succinctness and Decidability
Recommended article: On a generalization of regular expressions
Recommended article: Q4418600
description: scientific article; zbMATH DE number 4166863