Two techniques in the area of the star problem in trace monoids

DOI10.1016/S0304-3975(03)00313-XzbMath1106.68371MaRDI QIDQ1884907

Daniel Kirsten, Jerzy Marcinkowski

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

DecidabilityRecognizable languageStar problemTrace monoid

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (1)

Distance desert automata and the star height problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved limitedness theorems on finite automata with distance functions
• Limitedness theorem on finite automata with distance functions
• Semi-commutations
• On regular trace languages
• Mixed product and asynchronous automata
• Decidability of the star problem in \(A^*\times{}\{ b\}^*\)
• Matrices de Hankel
• The star problem and the finite power property in trace monoids: Reductions beyond C4
• New results on the star problem in trace monoids
• Semigroups, Presburger formulas, and languages
• Kleene quotient theorems
• Combinatorial problems of commutation and rearrangements
• Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif
• Trace languages defined by regular string languages
• Some trace monoids where both the Star problem and the Finite Power Property Problem are decidable
• Bounded Regular Sets
• Decidability equivalence between the star problem and the finite power problem in trace monoids

This page was built for publication: Two techniques in the area of the star problem in trace monoids