scientific article
From MaRDI portal
Publication:3736919
zbMath0601.68055MaRDI QIDQ3736919
Publication date: 1985
Full work available at URL: https://eudml.org/doc/92219
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)
Related Items (79)
Lyndon traces and shuffle algebras ⋮ On some equations in free partially commutative monoids ⋮ On the structure of recognizable languages of dependence graphs ⋮ Two optimal parallel algorithms on the commutation class of a word ⋮ A decision procedure on partially commutative free monoids ⋮ Deterministic asynchronous automata for infinite traces ⋮ Undecidability of the trace coding problem and some decidable cases ⋮ Pattern matching in trace monoids ⋮ A partial trace semantics for Petri nets ⋮ Semi-commutations ⋮ On regular trace languages ⋮ Mixed product and asynchronous automata ⋮ An extension of the notions of traces and of asynchronous automata ⋮ Rewriting systems and word problems in a free partially commutative monoid ⋮ Overlaps in free partially commutative monoids ⋮ Efficient solution of some problems in free partially commutative monoids ⋮ The inclusion structure of partially lossy queue monoids and their trace submonoids ⋮ Theory of traces ⋮ The word problem for free partially commutative groups ⋮ 2-asynchronous automata ⋮ On recognizable subsets of free partially commutative monoids ⋮ Théorèmes de transfert pour les polynômes partiellement commutatifs. (Transfer theorems for partially commutative polynomials) ⋮ Complete subgraphs of bipartite graphs and applications to trace languages ⋮ Serialization of concurrent programs ⋮ Trace languages defined by regular string languages ⋮ On confluence of one-rule trace-rewriting systems ⋮ Regular languages and partial commutations ⋮ One-rule trace-rewriting systems and confluence ⋮ Some trace monoids where both the Star problem and the Finite Power Property Problem are decidable ⋮ The code problem for traces -- improving the boundaries ⋮ Schützenberger-like products in non-free monoids ⋮ Parties reconnaissables de monoïdes définis par générateurs et relations ⋮ A cut-invariant law of large numbers for random heaps ⋮ Non-repetitive words relative to a rewriting system ⋮ Un modèle asynchrone pour les systèmes distribués. (An asynchronous model of distributed systems) ⋮ Word problems over traces which are solvable in linear time ⋮ Distribution and synchronized automata ⋮ On aperiodic and star-free formal power series in partially commuting variables ⋮ Monoïde libre et musique, première partie : les musiciens ont-ils besoin des mathématiques ? ⋮ Recognizable closures and submonoids of free partially commutative monoids ⋮ A kleene theorem for recognizable languages over concurrency monoids ⋮ Trace monoids with some invertible generators: Two decision problems ⋮ On the number of partially abelian square-free words on a three-letter alphabet ⋮ 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 ⋮ Two recognizable string-matching problems over free partially commutative monoids ⋮ Computing the closure of sets of words under partial commutations ⋮ Star-free trace languages ⋮ On the concatenation of infinite traces ⋮ Möbius functions and confluent semi-commutations ⋮ Semicommutations and algebraic languages ⋮ The free partially commutative Lie algebra: Bases and ranks ⋮ Decidability of the star problem in \(A^*\times{}\{ b\}^*\) ⋮ String matching problems over free partially commutative monoids ⋮ Time-stamps for Mazurkiewicz traces. ⋮ Synchronization of Bernoulli sequences on shared letters ⋮ On a conjecture about finite fixed points of morphisms ⋮ Partially abelian squarefree words ⋮ A remark on the representation of trace monoids ⋮ A generalization of traces ⋮ Local testability from words to traces, a suitable definition ⋮ Semi-commutations and rational expressions ⋮ On the Knuth-Bendix completion for concurrent processes ⋮ On deciding confluence of finite string-rewriting systems modulo partial commutativity ⋮ Word problems over traces which are solvable in linear time ⋮ The Trace Monoids in the Queue Monoid and in the Direct Product of Two Free Monoids ⋮ The lattices of prefixes and overlaps of traces ⋮ Characterizations of the decidability of some problems for regular trace languages ⋮ On the synchronization of traces ⋮ The Kleene-Schützenberger theorem for formal power series in partially commuting variables. ⋮ Confluence problems for trace rewriting systems ⋮ The star problem and the finite power property in trace monoids: Reductions beyond C4 ⋮ Graphs and free partially commutative monoids ⋮ Atomic semicommutations ⋮ An extension of Kleene's and Ochmański's theorems to infinite traces ⋮ The parallel complexity of two problems on concurrency ⋮ Recognizable trace languages, distributed automata and the distribution problem
Cites Work
This page was built for publication:
