The star problem and the finite power property in trace monoids: Reductions beyond C4

DOI10.1006/inco.2002.3152zbMath1012.68098OpenAlexW2055206684MaRDI QIDQ1854540

Daniel Kirsten

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2002.3152

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Semi-commutations
• Mixed product and asynchronous automata
• A decision procedure for the order of regular events
• Decidability of the star problem in \(A^*\times{}\{ b\}^*\)
• Matrices de Hankel
• The code problem for traces -- improving the boundaries
• New results on the star problem in trace monoids
• Semigroups, Presburger formulas, and languages
• Combinatorial problems of commutation and rearrangements
• Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif
• Bounded Regular Sets
• Algebraic automata and context-free sets
• Decidability equivalence between the star problem and the finite power problem in trace monoids

This page was built for publication: The star problem and the finite power property in trace monoids: Reductions beyond C4