In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexity of regular expressions: The star height equals the maximum nesting depth of stars appearing in the regular expression. The concept of star height was first defined and studied by Eggan (1963).

PropertyValue
dbpprop:abstract
  • In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexity of regular expressions: The star height equals the maximum nesting depth of stars appearing in the regular expression. The concept of star height was first defined and studied by Eggan (1963).
  • Die Sternhöhe ist ein Begriff aus der Theoretischen Informatik.
  • In matematica, considerata una espressione regolare E sopra un alfabeto finito A, si dice altezza star di E l'intero naturale che denotiamo con h(E) definito dalle seguenti richieste ricorsive: h(&empty) := 0, h(&mu) := 0 h(a) := 0 per ogni lettera a ∈ A. h(E ∩ F) := h(E · F) := max(h, h) h(E) := h(E) per ogni intero positivo c h(E) := h(E) + 1 Si definisce inoltre come altezza star h(L) di un linguaggio regolare L la minima delle altezze star delle espressioni regolari che esprimono L. Marcel Schützenberger nel 1965 ha dimostrato che un linguaggio regolare L ha altezza star uguale a 0 se e solo se il suo monoide sintattico è aperiodico.
  • 在數學裡，正則表示法 E 在有限字母 A 的星高 h(E) 定義如下：: h(&empty) = 0, h(&epsilon) = 0, h(a) = 0, ∀ a ∈ A. h(E ∪ F) = h(EF) = max(h, h) h(E) = h(E) h(E) = h(E) + 1 正則語言 L 的星高定義為所有能表示 L 的正則表示式的星高的最小值。 可證明，語言 L 有星高 0 若且唯若 其語法幺半群為非週期么半群。
dbpprop:harvtxtProperty
  • Schützenberger
  • 1965 (xsd:integer)
dbpprop:hasPhotoCollection
dbpprop:wikiPageUsesTemplate
rdf:type
rdfs:comment
  • In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexity of regular expressions: The star height equals the maximum nesting depth of stars appearing in the regular expression. The concept of star height was first defined and studied by Eggan (1963).
  • Die Sternhöhe ist ein Begriff aus der Theoretischen Informatik.
  • In matematica, considerata una espressione regolare E sopra un alfabeto finito A, si dice altezza star di E l'intero naturale che denotiamo con h(E) definito dalle seguenti richieste ricorsive: h(&empty) := 0, h(&mu) := 0 h(a) := 0 per ogni lettera a ∈ A.
  • 在數學裡，正則表示法 E 在有限字母 A 的星高 h(E) 定義如下：: h(&empty) = 0, h(&epsilon) = 0, h(a) = 0, ∀ a ∈ A. h(E ∪ F) = h(EF) = max(h, h) h(E) = h(E) h(E) = h(E) + 1 正則語言 L 的星高定義為所有能表示 L 的正則表示式的星高的最小值。 可證明，語言 L 有星高 0 若且唯若 其語法幺半群為非週期么半群。
rdfs:label
  • Star height
  • Sternhöhe (Informatik)
  • Altezza star
  • 星高
owl:sameAs
skos:subject
foaf:page
is owl:sameAs of