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

DOI10.1016/0304-3975(94)90254-2zbMath0795.68116OpenAlexW2017031131MaRDI QIDQ1318685

Antoine Petit, Paul Gastin, 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 propertiesinfinite tracesfinite behaviour of concurrent systemsinfinite behaviour of nonterminating concurrent systemsnormal-form representationsrational sets of infinite tracesrecognizable trace languagesSchützenberger product of monoids

Mathematics Subject Classification ID

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

Related Items (4)

An extension of the wreath product principle for finite Mazurkiewicz traces ⋮ Schützenberger-like products in non-free monoids ⋮ Logical definability on infinite traces ⋮ RECOGNIZABLE AND LOGICALLY DEFINABLE LANGUAGES OF INFINITE COMPUTATIONS IN CONCURRENT AUTOMATA

Cites Work

• The poset of infinitary traces
• Asynchronous mappings and asynchronous cellular automata
• Maximal serializability of iterated transactions
• A syntactic congruence for rational \(\omega\)-languages
• Semi-commutations
• Theory of traces
• On recognizable subsets of free partially commutative monoids
• Sequential and concurrent behaviour in Petri net theory
• Recognizable closures and submonoids of free partially commutative monoids
• Combinatorics on traces
• Matrices de Hankel
• Combinatorial problems of commutation and rearrangements
• Notes on finite asynchronous automata
• ON THE STAR OPERATION IN FREE PARTIALLY COMMUTATIVE MONOIDS
• Asynchronous cellular automata for infinite traces
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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