# Two Techniques in the Area of the Star Problem

- Authors
- Publisher
- Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden
- Publication Date
- Source
- legacy-msw
- Keywords
- Disciplines

## Abstract

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.