The solutions of two star-height problems for regular trees

DOI10.1016/0304-3975(84)90063-XzbMath0554.68037OpenAlexW2054822300MaRDI QIDQ760212

J. P. Braquelaire, Bruno Courcelle

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90063-x

zbMATH Keywords

ranked graphrational expressions

Mathematics Subject Classification ID

Trees (05C05) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items (6)

Equivalences and transformations of regular systems - applications to recursive program schemes and grammars ⋮ Algorithms for determining relative star height and star height ⋮ Unification and combination of a class of traversal strategies made with pattern matching and fixed-points ⋮ The variable hierarchy for the games \(\mu \)-calculus ⋮ Algorithms for determining relative inclusion star height and inclusion star height ⋮ Type inference with recursive types: Syntax and semantics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamental properties of infinite trees
• A representation of trees by languages. II
• An algebraic definition for control structures
• Regular trees and the free iterative theory
• The existence and construction of free iterative theories
• On the algebraic structure of rooted trees
• Transition graphs and the star-height of regular events
• General properties of star height of regular events
• Star height of certain families of regular events
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• The loop complexity of pure-group events
• Techniques for establishing star height of regular sets
• Rank-non-increasing transformations on transition graphs

This page was built for publication: The solutions of two star-height problems for regular trees