Return to search

Two Techniques in the Area of the Star Problem

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.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:26306
Date30 November 2012
CreatorsKirsten, Daniel, Marcinkowski, Jerzy
ContributorsUniversity of Wrocław
PublisherTechnische Universität Dresden
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typedoc-type:workingPaper, info:eu-repo/semantics/workingPaper, doc-type:Text
Rightsinfo:eu-repo/semantics/openAccess
Relationurn:nbn:de:bsz:14-qucosa-79344, qucosa:24841

Page generated in 0.002 seconds