Efficient solution of some problems in free partially commutative monoids
From MaRDI portal
Publication:2640345
DOI10.1016/0890-5401(90)90010-FzbMath0719.68036MaRDI QIDQ2640345
Publication date: 1990
Published in: Information and Computation (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)
Related Items
Algorithmic problems in right-angled Artin groups: complexity and applications, Pattern matching in trace monoids, Overlaps in free partially commutative monoids, Intersection problem for Droms RAAGs, On confluence of one-rule trace-rewriting systems, Pattern matching and membership for hierarchical message sequence charts, Full-featured peak reduction in right-angled Artin groups., Trace monoids with some invertible generators: Two decision problems, COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS, Parabolic and quasiparabolic subgroups of free partially commutative groups., On the Hochschild homology of \(\ell^1\)-rapid decay group algebras, The lattices of prefixes and overlaps of traces, The conjugacy problem in subgroups of right-angled Artin groups
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Conjugacy in monoids with a special Church-Rosser presentation is decidable
- Maximal serializability of iterated transactions
- Some properties of commutation in free partially commutative monoids
- On some equations in free partially commutative monoids
- Rewriting systems and word problems in a free partially commutative monoid
- Theory of traces
- Time-space-optimal string matching
- Recognizable subsets of some partially Abelian monoids
- Combinatorial problems of commutation and rearrangements
- Fast Pattern Matching in Strings
- Parallel Program Schemata and Maximal Parallelism I. Fundamental Results
