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.


Seen <100 times

More articles like this

Two techniques in the area of the star problem in...

on Theoretical Computer Science Jan 01, 2003

[Research techniques applied to nursing. Some note...

on Sogo kango. Comprehensive nurs... September 1967

The market area problem with two plants

on Regional Science and Urban Eco... Jan 01, 1976
More articles like this..