Decidability of the star problem in A^*\ b\^*
From MaRDI portal
Publication:1201865
The Star problem in trace monoids is the following problem: Let \(L\) be a recognizable trace language, is \(L^*\) recognizable? It is proved that this problem is decidable when the trace monoid is a direct product of free monoids \(A^*\times\{b\}^*\).
Recommendations
- Two techniques in the area of the star problem in trace monoids
- scientific article; zbMATH DE number 1754623
- Decidability equivalence between the star problem and the finite power problem in trace monoids
- scientific article; zbMATH DE number 1304323
- Some trace monoids where both the star problem and the finite power property problem are decidable (extended abstract)
Cites work
- A decision procedure for the order of regular events
- An algorithm to decide whether a rational subset of \({\mathbb{N}}^ k\) is recognizable
- Bounded Regular Sets
- Combinatorial problems of commutation and rearrangements
- Combinatorics on traces
- scientific article; zbMATH DE number 3970130 (Why is no real title available?)
- scientific article; zbMATH DE number 3660804 (Why is no real title available?)
- scientific article; zbMATH DE number 8897 (Why is no real title available?)
- scientific article; zbMATH DE number 4119618 (Why is no real title available?)
- Matrices de Hankel
- Maximal serializability of iterated transactions
- ON THE STAR OPERATION IN FREE PARTIALLY COMMUTATIVE MONOIDS
- Recognizable closures and submonoids of free partially commutative monoids
- Recognizable subsets of some partially Abelian monoids
- Semi-commutations
- Semigroups, Presburger formulas, and languages
- Theory of traces
- Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif
Cited in
(7)- The star problem and the finite power property in trace monoids: Reductions beyond C4
- Two techniques in the area of the star problem in trace monoids
- scientific article; zbMATH DE number 8897 (Why is no real title available?)
- scientific article; zbMATH DE number 1304323 (Why is no real title available?)
- Computing the closure of sets of words under partial commutations
- scientific article; zbMATH DE number 1405661 (Why is no real title available?)
- Some trace monoids where both the star problem and the finite power property problem are decidable (extended abstract)
This page was built for publication: Decidability of the star problem in \(A^*\times{}\{ b\}^*\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1201865)
