- AutorIn
- Daniel Kirsten
- Titel
- A Connection between the Star Problem and the Finite Power Property in Trace Monoids
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa-100445
- Schriftenreihe
- Technische Berichte
- Bandnummer
- 1998,09 (TUD-FI98-09 October 1998)
- Erstveröffentlichung
- 1998
- ISSN
- 1430-211X
- Abstract (EN)
- 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.
- Freie Schlagwörter (DE)
- formale Sprachen, Halbgruppe, Mathematik
- Freie Schlagwörter (EN)
- star problem, trace monoids, formal languages
- Klassifikation (DDC)
- 004
- Klassifikation (RVK)
- SS 5514
- Publizierende Institution
- Technische Universität Dresden, Dresden
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa-100445
- Veröffentlichungsdatum Qucosa
- 28.11.2012
- Dokumenttyp
- Forschungsbericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis