Theory of traces

DOI10.1016/0304-3975(88)90051-5zbMath0652.68017OpenAlexW1967736886WikidataQ57402292 ScholiaQ57402292MaRDI QIDQ1107296

Grzegorz Rozenberg, Ijsbrand Jan Aalbersberg

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90051-5

zbMATH Keywords

concurrent systemsPetri netscondition/event systemssynchronizationdependency graphtraces

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Abstract data types; algebraic specification (68Q65) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (69)

Weak equivalence of higher-dimensional automata ⋮ Connections between a concrete and an abstract model of concurrent systems ⋮ Asynchronous automata versus asynchronous cellular automata ⋮ Lyndon traces and shuffle algebras ⋮ On the structure of recognizable languages of dependence graphs ⋮ On a subclass of context-free groups ⋮ Efficient rewriting in cograph trace monoids ⋮ Computing Petri net languages by reductions ⋮ A note on the construction of marked graphs ⋮ Efficient solution of some problems in free partially commutative monoids ⋮ Lyndon heaps: An analogue of Lyndon words in free partially commutative monoids ⋮ Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata ⋮ The monadic second-order logic of graphs. X: Linear orderings ⋮ Net models of discrete information transducers. I ⋮ On recognizable and rational formal power series in partially commuting variables ⋮ Shuffle on trajectories: Syntactic constraints ⋮ Compositional relational semantics for indeterminate dataflow networks ⋮ Subclasses of recognizable trace languages ⋮ Poset properties of complex traces ⋮ Logical definability of some rational trace languages ⋮ Trade-offs in true concurrency: Pomsets and mazurkiewicz traces ⋮ Probabilistic asynchronous automata ⋮ The complexity of regular DNLC graph languages ⋮ Word problems over traces which are solvable in linear time ⋮ The word problem for \(1\mathcal{LC}\) congruences is NP-hard. ⋮ From domains to automata with concurrency ⋮ A kleene theorem for recognizable languages over concurrency monoids ⋮ Trace monoids with some invertible generators: Two decision problems ⋮ Linear automata with translucent letters and linear context-free trace languages ⋮ Executions: A new partial-order semantics of Petri nets ⋮ Event structures and trace monoids ⋮ Probabilistic estimation of the number of prefixes of a trace ⋮ Recognizable languages in concurrency monoids ⋮ On some decision problems for trace codings ⋮ Logical definability on infinite traces ⋮ A denotational theory of synchronous reactive systems ⋮ Star-free trace languages ⋮ On the concatenation of infinite traces ⋮ Möbius functions and confluent semi-commutations ⋮ The expressive power of indeterminate dataflow primitives ⋮ Decidability of the star problem in \(A^*\times{}\{ b\}^*\) ⋮ The poset of infinitary traces ⋮ Partially abelian squarefree words ⋮ A remark on the representation of trace monoids ⋮ A generalization of traces ⋮ On Restarting Automata with Window Size One ⋮ Local testability from words to traces, a suitable definition ⋮ Semi-commutations and rational expressions ⋮ Asynchronous cellular automata for infinite traces ⋮ An Automata-Theoretical Characterization of Context-Free Trace Languages ⋮ The shuffle algebra and its derivations ⋮ Word problems over traces which are solvable in linear time ⋮ The lattices of prefixes and overlaps of traces ⋮ Algebra and theory of order-deterministic pomsets ⋮ Representation of computations in concurrent automata by dependence orders ⋮ Synchronization expressions with extended join operation ⋮ Semi-commutations and Petri nets ⋮ SC-EXPRESSIONS IN OBJECT-ORIENTED LANGUAGES ⋮ Characterizations of the decidability of some problems for regular trace languages ⋮ On the synchronization of traces ⋮ CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store ⋮ RECOGNIZABLE AND LOGICALLY DEFINABLE LANGUAGES OF INFINITE COMPUTATIONS IN CONCURRENT AUTOMATA ⋮ The Kleene-Schützenberger theorem for formal power series in partially commuting variables. ⋮ Compositionality in dataflow synchronous languages: Specification and distributed code generation ⋮ Nonexpressibility of fairness and signaling ⋮ \(\Pi_ 1^ 1\)-universality of some propositional logics of concurrent programs ⋮ An extension of Kleene's and Ochmański's theorems to infinite traces ⋮ Resource traces: A domain for processes sharing exclusive resources. ⋮ Recognizable trace languages, distributed automata and the distribution problem

Cites Work

• Multiserialization of iterated transactions
• Partial commutations and faithful rational transductions
• Maximal serializability of iterated transactions
• Some properties of commutation in free partially commutative monoids
• Square-free words on partially commutative free monoids
• Traces, dependency graphs and DNLC grammars
• Semi-commutations
• On regular trace languages
• A characterization of context-free string languages by directed node- label controlled graph grammars
• Matrices de Hankel
• Parallel concepts in graph theory
• Membership problems for regular and context-free trace languages
• Recognizable subsets of some partially Abelian monoids
• Combinatorial problems of commutation and rearrangements
• A lattice-theoretical fixpoint theorem and its applications
• Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif
• Trace languages defined by regular string languages
• Notes on finite asynchronous automata
• An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages
• Rough sets
• Communicating sequential processes
• On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
• Decomposing partial orderings into chains
• 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
• 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: Theory of traces