๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Star height of certain families of regular events

โœ Scribed by Rina S. Cohen

Book ID
104148017
Publisher
Elsevier Science
Year
1970
Tongue
English
Weight
728 KB
Volume
4
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis

This paper studies the relationship between the apparent star height of a given regular expression and the structure of its reduced deterministic state graph. Sufficient conditions for the star height of a regular event R to equal the cycle rank of its reduced state graph GR are derived. The cycle rank of GR is also shown to constitute a lower bound to the star height of certain subsets of R. These results are then applied to fully characterize the star height of events consisting of ~ sets of paths in finite digraphs and two open problems posed by Eggan are answered.

๐Ÿ“œ SIMILAR VOLUMES

General properties of star height of reg
General properties of star height of regular events
โœ Rina S. Cohen; J.A. Brzozowski ๐Ÿ“‚ Article ๐Ÿ“… 1970 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 891 KB

Properties of star height of regular events are investigated. It is shown that star height is preserved under such operations as taking quotients, addition or subtraction of a finite event, removal of all words beginning with a given letter, and removal of certain subsets of smaller star height. Nex

Families of Regular Graphs in Regular Ma
Families of Regular Graphs in Regular Maps
โœ Steve Wilson ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 227 KB

The question of when a given graph can be the underlying graph of a regular map has roots a hundred years old and is currently the object of several threads of research. This paper outlines this topic briefly and proves that a product of graphs which have regular embeddings also has such an embeddin