Word problems over traces which are solvable in linear time
From MaRDI portal
Publication:914395
DOI10.1016/0304-3975(90)90003-ZzbMath0701.68056MaRDI QIDQ914395
Publication date: 1990
Published in: Theoretical Computer Science (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Grammars and rewriting systems (68Q42) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03)
Related Items
The submonoid and rational subset membership problems for graph groups., Confluence problems for trace rewriting systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Partial commutations and faithful rational transductions
- Complete semi-Thue systems for abelian groups
- Rewriting systems and word problems in a free partially commutative monoid
- Theory of traces
- Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
- The word problem for free partially commutative groups
- New decision algorithms for finitely presented commutative semigroups
- Presentations of groups and monoids
- On the Knuth-Bendix completion for concurrent processes
- The complexity of the word problems for commutative semigroups and polynomial ideals
- Semigroups, Presburger formulas, and languages
- Combinatorial problems of commutation and rearrangements
- Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems
- Confluent and Other Types of Thue Systems
- Recursive Unsolvability of a problem of Thue
- Counter machines and counter languages
