Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

The Star Problem in Trace Monoids: Reductions Beyond C4
Extended Abstract

Daniel KirstenContact Information

(7)  Institute of Algebra, Dresden University of Technology, D-01062 Dresden, Germany
Abstract
We deal with the star problem in trace monoids which means to decide whether the iteration of a recognizable trace language is recognizable. We consider trace monoids K n={a 1 b 1}* × … ×{a n b n }*. Our main theorem asserts that the star problem is decidable in a trace monoid M iff it is decidable in the biggest K n submonoid in M. Thus, future research on the star problem can focus on the trace monoids K n. The recently shown decidability equivalence between the star problem and the finite power problem [14] plays a crucial role in the paper.
Partially supported by the PhD program “Specification of discrete processes and systems of processes by operational models and logics” of the DFG.
See author’s homepage for a long version including complete proofs [13].

Contact Information Daniel Kirsten
Email: kirsten@math.tu-dresden.de
URL: www.math.tu-dresden.de/~kirsten
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: MPWEB26
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)