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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:14-qucosa-100584 |
| Date | 30 November 2012 |
| Creators | Kirsten, Daniel, Marcinkowski, Jerzy |
| Contributors | Technische Universität Dresden, Fakultät Informatik, University of Wrocław,, Technische Universität Dresden, Fakultät Informatik |
| Publisher | Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:workingPaper |
| Format | application/pdf, application/postscript, application/zip |
| Relation | dcterms:isPartOf:Technische Berichte / Technische Universität Dresden, Fakultät Informatik ; 1999,08 (TUD-FI99-08 Dezember 1999) |
Page generated in 0.002 seconds