The solutions of two star-height problems for regular trees
Regular trees can be defined by two types of rational expressions. For these two types we solve the star-height problem, i.e., we show how to construct a rational expression of minimal star-height from the minimal graph of the given tree (i.e., the analogue of the minimal deterministic automaton for regular languages). In one case, the minimal star-height is the rank (in the sense of Eggan) of the minimal graph. There corresponds a characterization of the star-height of a prefix-free regular language w.r.t. rational expressions of a special kind (called deterministic) as the rank of its minimal deterministic automaton considered as a graph.
- scientific article; zbMATH DE number 3917723
- Some results on the generalized star-height problem
- Some Variants of the Star Height Problem
- An algorithmic framework for the exact solution of tree-star problems
- The p-arborescence star problem: formulations and exact solution approaches
- The tree-star problem: a formulation and a branch-and-cut algorithm
- The 2-radius and 2-radiian problems on trees
- On trees as star complements in regular graphs
- Some results on symmetric double starlike trees
- On characteristic functions of equilateral regular star-trees
- A representation of trees by languages. II
- An algebraic definition for control structures
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Fundamental properties of infinite trees
- General properties of star height of regular events
- scientific article; zbMATH DE number 3695144 (Why is no real title available?)
- scientific article; zbMATH DE number 3497806 (Why is no real title available?)
- scientific article; zbMATH DE number 3512082 (Why is no real title available?)
- On the algebraic structure of rooted trees
- Rank-non-increasing transformations on transition graphs
- Regular trees and the free iterative theory
- Star height of certain families of regular events
- Techniques for establishing star height of regular sets
- The existence and construction of free iterative theories
- The loop complexity of pure-group events
- Transition graphs and the star-height of regular events
- Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
- Algorithms for determining relative star height and star height
- Algorithms for determining relative inclusion star height and inclusion star height
- Unification and combination of a class of traversal strategies made with pattern matching and fixed-points
- Some Variants of the Star Height Problem
- scientific article; zbMATH DE number 4213459 (Why is no real title available?)
- scientific article; zbMATH DE number 3924121 (Why is no real title available?)
- scientific article; zbMATH DE number 522865 (Why is no real title available?)
- The variable hierarchy for the games -calculus
- Type inference with recursive types: Syntax and semantics
This page was built for publication: The solutions of two star-height problems for regular trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q760212)
