Affordable Access

Two Techniques in the Area of the Star Problem

Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden
Publication Date
  • Entscheidbarkeit
  • Algebra
  • Formale Sprachen
  • Halbgruppe
  • Mathematik
  • Star Problem
  • Trace Monoids
  • Formal Languages
  • Decidability
  • Recognizable Trace Language
  • Ddc:004
  • Rvk:Ss 5514
  • Mathematics


This paper deals with decision problems related to the star problem in trace monoids, which means to determine whether the iteration of a recognizable trace language is recognizable. Due to a theorem by G. Richomme from 1994 [32, 33], we know that the star problem is decidable in trace monoids which do not contain a submonoid of the form {a,c}* x {b,d}*. Here, we consider a more general problem: Is it decidable whether for some recognizable trace language and some recognizable or finite trace language P the intersection R ∩ P* is recognizable? If P is recognizable, then we show that this problem is decidale iff the underlying trace monoid does not contain a submonoid of the form {a,c}* x b*. In the case of finite languages P, we show several decidability and undecidability results.

There are no comments yet on this publication. Be the first to share your thoughts.