An extension of Kleene's and Ochmański's theorems to infinite traces

DOI10.1016/0304-3975(94)90254-2MaRDI QIDQ1318685zbMATH OpenOpenAlexFDO

Authors Paul Gastin, A. Petit, Wiesław Zielonka

Publication date 5 April 1994

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

Full work available at URL https://doi.org/10.1016/0304-3975(94)90254-2

zbMATH Keywords

closure propertiesfinite behaviour of concurrent systemsinfinite behaviour of nonterminating concurrent systemsinfinite tracesnormal-form representationsrational sets of infinite tracesrecognizable trace languagesSchützenberger product of monoids

Mathematics Subject Classification ID

Semigroups in automata theory, linguistics, etc. (20M35) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Formal languages and automata (68Q45) Semantics in the theory of computing (68Q55)

Recommendations

• scientific article; zbMATH DE number 176739
• Toward a Structure Theory of Regular Infinitary Trace Languages
• scientific article; zbMATH DE number 176496
• scientific article; zbMATH DE number 512867
• Rational and recognizable complex trace languages

Cites work

• A syntactic congruence for rational -languages
• Asynchronous cellular automata for infinite traces
• Asynchronous mappings and asynchronous cellular automata
• Combinatorial problems of commutation and rearrangements
• Combinatorics on traces
• scientific article; zbMATH DE number 1638658 (Why is no real title available?)
• scientific article; zbMATH DE number 3862473 (Why is no real title available?)
• scientific article; zbMATH DE number 3924146 (Why is no real title available?)
• scientific article; zbMATH DE number 3970130 (Why is no real title available?)
• scientific article; zbMATH DE number 3976377 (Why is no real title available?)
• scientific article; zbMATH DE number 4030996 (Why is no real title available?)
• scientific article; zbMATH DE number 3711961 (Why is no real title available?)
• scientific article; zbMATH DE number 8897 (Why is no real title available?)
• scientific article; zbMATH DE number 18653 (Why is no real title available?)
• scientific article; zbMATH DE number 176133 (Why is no real title available?)
• scientific article; zbMATH DE number 176496 (Why is no real title available?)
• scientific article; zbMATH DE number 176497 (Why is no real title available?)
• scientific article; zbMATH DE number 176739 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 512867 (Why is no real title available?)
• scientific article; zbMATH DE number 3445172 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• Matrices de Hankel
• Maximal serializability of iterated transactions
• Notes on finite asynchronous automata
• On recognizable subsets of free partially commutative monoids
• ON THE STAR OPERATION IN FREE PARTIALLY COMMUTATIVE MONOIDS
• Recognizable closures and submonoids of free partially commutative monoids
• Semi-commutations
• Sequential and concurrent behaviour in Petri net theory
• The poset of infinitary traces
• Theory of traces

Cited in

(13)

• Infinite time extensions of Kleene's \({\mathcal O}\)
• Rational and recognizable complex trace languages
• On the equivalence of the two existing extensions of the leximax criterion to the infinite case
• A Kleene-Schützenberger theorem for trace series over bounded lattices
• An extension of the wreath product principle for finite Mazurkiewicz traces
• scientific article; zbMATH DE number 176496 (Why is no real title available?)
• scientific article; zbMATH DE number 176497 (Why is no real title available?)
• scientific article; zbMATH DE number 176739 (Why is no real title available?)
• Schützenberger-like products in non-free monoids
• Recognizable and logically definable languages of infinite computations in concurrent automata
• Projection representation of Mazurkiewicz traces
• Logical definability on infinite traces
• Disjointness, inclusion, and regularity of -rational trace languages (extended abstract)

This page was built for publication: An extension of Kleene's and Ochmański's theorems to infinite traces

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