- AutorIn
- Daniel Kirsten
- Jerzy Marcinkowski
- Titel
- Two Techniques in the Area of the Star Problem
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa-100584
- Schriftenreihe
- Technische Berichte
- Bandnummer
- 1999,08 (TUD-FI99-08 Dezember 1999)
- Erstveröffentlichung
- 1999
- ISSN
- 1430-211X
- Abstract (EN)
- 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.
- Freie Schlagwörter (DE)
- Entscheidbarkeit, Algebra, formale Sprachen, Halbgruppe, Mathematik
- Freie Schlagwörter (EN)
- star problem, trace monoids, formal languages, decidability, recognizable trace language
- Klassifikation (DDC)
- 004
- Klassifikation (RVK)
- SS 5514
- Publizierende Institution
- Technische Universität Dresden, Dresden
- Sonstige beteiligte Institution
- Technische Universität Dresden, Dresden
- University of Wrocław, Wrocław, Polen
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa-100584
- Veröffentlichungsdatum Qucosa
- 30.11.2012
- Dokumenttyp
- Forschungsbericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis