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 Richomme from 1994[30,31], we know that the Star Problem is decidable in trace monoids which do not contain a C4-submonoid. The C4 is (isomorphic to) the Caresian Product of two free monoids over doubleton alphabets. It is not known, whether the Star Problem is decidable in C4 or in trace monoids containing a C4. In this paper, we show undecidability of some related problems: Assume a trace monoid which contains a C4. Then, it is undecidable whether for two given recognizable languages K and L, we have K ⊆ L*, although we can decide K* ⊆ L. Further, we can not decide recognizability of K ∩ L* as well as universality and recognizability of K U L*.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:26301 |
| Date | 28 November 2012 |
| Creators | Kirsten, Daniel |
| Publisher | Technische Universität Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:workingPaper, info:eu-repo/semantics/workingPaper, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | urn:nbn:de:bsz:14-qucosa-79344, qucosa:24841 |
Page generated in 0.0021 seconds