This paper deals with a connection between two decision problems for recognizable trace languages: the star problem and the finite power property problem. Due to a theorem by Richomme from 1994 [26, 28], we know that both problems are decidable in trace monoids which do not contain a C4 submonoid. It is not known, whether the star problem or the finite power property are decidable in the C4 or in trace monoids containing a C4.
In this paper, we show a new connection between these problems. Assume a trace monoid IM (Σ, I) which is isomorphic to the Cartesian Product of two disjoint trace monoids IM (Σ1, I1) and IM (Σ2, I2). Assume further a recognizable language L in IM (Σ, I) such that every trace in L contains at least one letter in Σ1 and at least in one letter in Σ2. Then, the main theorem of this paper asserts that L* is recognizable iff L has the finite power property.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:14-qucosa-100445 |
| Date | 28 November 2012 |
| Creators | Kirsten, Daniel |
| Contributors | 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 ; 1998,09 (TUD-FI98-09 October 1998) |
Page generated in 0.002 seconds