On aperiodic trace languages

DOI10.1007/BFB0020789MaRDI QIDQ4035659zbMATH OpenFDO

Authors Sergio Salemi, Giovanna Guaiana, Antonio Restivo

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0020789

zbMATH Keywords

concurrent systemsfree partially commutative monoidstrace languages

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Review text

[For the entire collection see Zbl 0753.00019.] The main result of the paper generalizes the theorem of Schützenberger to trace languages: the family of aperiodic trace languages coincides with the family of star-free trace languages. As a corollary we derive a characterization given in [\textit{M. P. Schützenberger}, Sur certaines pseudo-variétés de monoîdes finis, Report IRIA-Laboria N.62 (1974)] of aperiodic commutative languages.

Recommendations

• Asynchronous automata-theoretic characterization of aperiodic trace languages
• Star-free star and trace languages
• A Star Operation for Star-Free Trace Languages
• Star-free languages and local divisors
• scientific article; zbMATH DE number 2143013

Cited in

(14)

• Star-free trace languages
• Representation of computations in concurrent automata by dependence orders
• Aperiodic languages in concurrency monoids
• Bounded synchronization delay in omega-rational expressions
• An extension of the wreath product principle for finite Mazurkiewicz traces
• Rational, recognizable, and aperiodic sets in the partially lossy queue monoid
• scientific article; zbMATH DE number 3870628 (Why is no real title available?)
• Logical definability on infinite traces
• Rational, recognizable, and aperiodic partially lossy queue languages
• Star-free star and trace languages
• Star-free languages and local divisors
• Local testability from words to traces, a suitable definition
• Characterizations of fragments of temporal logic over Mazurkiewicz traces
• On bounded rational trace languages

This page was built for publication: On aperiodic trace languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4035659)