Combinatorics on traces

DOI10.1007/3-540-53031-2zbMath0717.68002OpenAlexW1605354378MaRDI QIDQ1188891

Publication date: 23 January 1993

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

Full work available at URL: https://doi.org/10.1007/3-540-53031-2

zbMATH Keywords

Möbius function Petri nets rewriting systems traces free partially commutative monoids trace theory semi-Thue systems replacement systems algebraic model of concurrent processes mathematical theory of concurrency

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Grammars and rewriting systems (68Q42) Thue and Post systems, etc. (03D03)

Related Items

Weak equivalence of higher-dimensional automata, Contraction of Dirac matrices via chord diagrams, Topological abstraction of higher-dimensional automata, Asynchronous automata versus asynchronous cellular automata, Lyndon traces and shuffle algebras, Two optimal parallel algorithms on the commutation class of a word, Introduction to Probabilistic Concurrent Systems, Deterministic asynchronous automata for infinite traces, Letter Graphs and Geometric Grid Classes of Permutations, Regular sets of infinite message sequence charts, A partial trace semantics for Petri nets, Infinite traces and symbolic dynamics, Labelled domains and automata with concurrency, Efficient rewriting in cograph trace monoids, On the complementation of asynchronous cellular Büchi automata, The inclusion structure of partially lossy queue monoids and their trace submonoids, Lexicographically first reduced words, The transformation monoid of a partially lossy queue, Markovian dynamics of concurrent systems, On confluence of one-rule trace-rewriting systems, Uniform Generation in Trace Monoids, Subclasses of recognizable trace languages, Poset properties of complex traces, One-rule trace-rewriting systems and confluence, On projective and separable properties, The code problem for traces -- improving the boundaries, Schützenberger-like products in non-free monoids, Toward uniform random generation in 1-safe Petri nets, A cut-invariant law of large numbers for random heaps, Centralizers in graph products of semigroups, On graph products of monoids, Probabilistic asynchronous automata, Knapsack in graph groups, GRAPH PRODUCTS AND THE ABSENCE OF PROPERTY (AR), The Tutte-Grothendieck group of an alphabetic rewriting system, A Hopf algebra for counting cycles, Weak morphisms of higher dimensional automata, Fixed points of endomorphisms of trace monoids., On aperiodic and star-free formal power series in partially commuting variables, Keeping track of the latest gossip in a distributed system, Finding k Partially Disjoint Paths in a Directed Planar Graph, On the complementation of Büchi asynchronous cellular automata, A kleene theorem for recognizable languages over concurrency monoids, Uniform and Bernoulli measures on the boundary of trace monoids, Closure properties of knapsack semilinear groups, Recognizable languages in concurrency monoids, On some decision problems for trace codings, Logical definability on infinite traces, COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS, The submonoid and rational subset membership problems for graph groups., Star-free trace languages, On the concatenation of infinite traces, Möbius functions and confluent semi-commutations, Partially commutative inverse monoids., Decidability of the star problem in \(A^*\times{}\{ b\}^*\), The poset of infinitary traces, The global dimension of a trace monoid ring, Algebraic recognizability of regular tree languages, Möbius inversion formula for the trace group, Sequential dynamical systems over words, Synchronization of Bernoulli sequences on shared letters, Unnamed Item, Counting domino tilings of rectangles via resultants, Letter graphs and geometric grid classes of permutations: characterization and recognition, A spectral property for concurrent systems and some probabilistic applications, Semi-commutations and rational expressions, Asynchronous cellular automata for infinite traces, Symbolic Dynamics, Flower Automata and Infinite Traces, Sheaves and Geometric Logic and Applications to Modular Verification of Complex Systems, The shuffle algebra and its derivations, The Trace Monoids in the Queue Monoid and in the Direct Product of Two Free Monoids, The lattices of prefixes and overlaps of traces, Representation of computations in concurrent automata by dependence orders, Weighted asynchronous cellular automata, GRAPH PRODUCTS OF RIGHT CANCELLATIVE MONOIDS, Topological Characterisation of Multi-Buffer Simulation, Parallelization of automata, Elements of a theory of computer simulation. I, Geometric grid classes of permutations, Determinants and Möbius functions in trace monoids, The Kleene-Schützenberger theorem for formal power series in partially commuting variables., Confluence problems for trace rewriting systems, 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, Deterministic concurrent systems