Star height of certain families of regular events

DOI10.1016/S0022-0000(70)80025-3zbMath0245.94039OpenAlexW2090529921MaRDI QIDQ2555472

Rina S. Cohen

Publication date: 1970

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(70)80025-3

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

The chop of languages, Distance desert automata and the star height problem, Stamina: stabilisation monoids in automata theory, Algorithms for determining relative star height and star height, Inversion height in free fields, Techniques for establishing star height of regular sets, Numeration systems, linear recurrences, and regular sets, ON TRANSITION MINIMALITY OF BIDETERMINISTIC AUTOMATA, Algorithms for determining relative inclusion star height and inclusion star height, Complexity measures for regular expressions, Tight Bounds on the Descriptional Complexity of Regular Expressions, The solutions of two star-height problems for regular trees, General properties of star height of regular events, An application of Cohen's result on star height to the theory of control structures, Characterization and complexity results on jumping finite automata

Cites Work

• Unnamed Item
• Transition graphs and the star-height of regular events
• General properties of star height of regular events
• Roots of Star Events
• The loop complexity of pure-group events
• On a question of Eggan
• Derivatives of Regular Expressions