On regular trace languages

DOI10.1016/0304-3975(87)90080-6zbMath0634.68076OpenAlexW2092700841MaRDI QIDQ1097040

Jacques Sakarovitch

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90080-6

zbMATH Keywords

commutative monoidtrace languagegeneralized automata on free products of monoids

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

On some equations in free partially commutative monoids ⋮ Two techniques in the area of the star problem in trace monoids ⋮ Generalized rational relations and their logical definability ⋮ Theory of traces ⋮ Complete subgraphs of bipartite graphs and applications to trace languages ⋮ Logical definability of some rational trace languages ⋮ RATIONAL SUBSETS IN HNN-EXTENSIONS AND AMALGAMATED PRODUCTS ⋮ WORD EQUATIONS OVER GRAPH PRODUCTS ⋮ Reordering Derivatives of Trace Closures of Regular Languages. ⋮ Star-free trace languages ⋮ On the decidability of the equivalence problem for partially commutative rational power series ⋮ Efficient recognition of trace languages defined by repeat-until loops ⋮ A remark on the representation of trace monoids ⋮ Equidivisible Kleene monoids and the Elgot-Mezei theorem ⋮ Recognizable trace languages, distributed automata and the distribution problem

Uses Software

• ALGOL 60

Cites Work

• Maximal serializability of iterated transactions
• Recognizable subsets of some partially Abelian monoids
• Combinatorial problems of commutation and rearrangements
• Rational sets in commutative monoids
• Deux applications de la représentation matricielle d'une série rationnelle non commutative. (Two applications of matrix representations of a rational non -commutative series)
• Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif
• Trace languages defined by regular string languages
• Bounded Algol-Like Languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item