Automata and partial commutations
From MaRDI portal
We consider words over an alphabet equipped with a partial commutation rule. The main result of the paper gives a sufficient condition for a set of words closed under the commutation rule to be recognizable by a finite automaton. More precisely, if \(X\) is recognizable and if \(ab\sim ba\) implies that the letters \(a\) and \(b\) do not appear in the same word of \(X\), then the closure of \(X^*\) under the commutation rule is recognizable.
Recommendations
Cites work
Cited in
(86)- On some equations in free partially commutative monoids
- A decision procedure on partially commutative free monoids
- Semi-commutations
- On regular trace languages
- Mixed product and asynchronous automata
- Rewriting systems and word problems in a free partially commutative monoid
- Theory of traces
- On lexicographic semi-commutations
- 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)
- Serialization of concurrent programs
- Recognizable closures and submonoids of free partially commutative monoids
- Trace monoids with some invertible generators: Two decision problems
- Event structures and trace monoids
- Probabilistic estimation of the number of prefixes of a trace
- Two recognizable string-matching problems over free partially commutative monoids
- Star-free trace languages
- 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
- On the Knuth-Bendix completion for concurrent processes
- On deciding confluence of finite string-rewriting systems modulo partial commutativity
- Atomic semicommutations
- An extension of Kleene's and Ochmański's theorems to infinite traces
- Recognizable trace languages, distributed automata and the distribution problem
- Lyndon traces and shuffle algebras
- Deterministic asynchronous automata for infinite traces
- A partial trace semantics for Petri nets
- The code problem for traces -- improving the boundaries
- A cut-invariant law of large numbers for random heaps
- The lattices of prefixes and overlaps 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
- Two optimal parallel algorithms on the commutation class of a word
- Undecidability of the trace coding problem and some decidable cases
- Synchronization of Bernoulli sequences on shared letters
- Time-stamps for Mazurkiewicz traces.
- Overlaps in free partially commutative monoids
- Efficient solution of some problems in free partially commutative monoids
- The trace monoids in the queue monoid and in the direct product of two free monoids
- A generalization of traces
- Complete subgraphs of bipartite graphs and applications to trace languages
- A sufficient condition for recognizability in a partially commutative monoid
- Trace languages defined by regular string languages
- Monoïde libre et musique, première partie : les musiciens ont-ils besoin des mathématiques ?
- Regular languages and partial commutations
- An extension of the notions of traces and of asynchronous automata
- Parties reconnaissables de monoïdes définis par générateurs et relations
- The inclusion structure of partially lossy queue monoids and their trace submonoids
- A Kleene theorem for recognizable languages over concurrency monoids
- Computing the closure of sets of words under partial commutations
- scientific article; zbMATH DE number 2143013 (Why is no real title available?)
- Characterizations of the decidability of some problems for regular trace languages
- On the synchronization of traces
- On confluence of one-rule trace-rewriting systems
- Schützenberger-like products in non-free monoids
- Pattern matching in trace monoids (extended abstract)
- Word problems over traces which are solvable in linear time
- One-rule trace-rewriting systems and confluence
- Some trace monoids where both the star problem and the finite power property problem are decidable (extended abstract)
- Semi-commutations and rational expressions
- On the structure of recognizable languages of dependence graphs
- On a conjecture about finite fixed points of morphisms
- Partially abelian squarefree words
- A remark on the representation of trace monoids
- On the number of partially abelian square-free words on a three-letter alphabet
- Recognizable languages in concurrency monoids
- On some decision problems for trace codings
- On the concatenation of infinite traces
- Möbius functions and confluent semi-commutations
- Active learning of deterministic transducers with outputs in arbitrary monoids
- Active learning of deterministic transducers with outputs in arbitrary monoids
- Reachability in trace-pushdown systems
- Local testability from words to traces, a suitable definition
- Analysis of algorithms for the recognition of rational and context-free trace languages
- Graphs and free partially commutative monoids
- The parallel complexity of two problems on concurrency
- 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
This page was built for publication: Automata and partial commutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3736919)