On the complexity of some extended word problems defined by cancellation rules

DOI10.1016/0020-0190(86)90087-6zbMath0624.68070OpenAlexW2019872646MaRDI QIDQ578921

Jacques Sakarovitch, Michèle Benois

Publication date: 1986

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(86)90087-6

zbMATH Keywords

algorithmcomplexity boundsword problemscancellation rulesset of descendants of a regular setThue systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03)

Related Items

On the security of p-party protocols ⋮ Some decision problems about controlled rewriting systems ⋮ An automata theoretic approach to the generalized word problem in graphs of groups ⋮ Bottom-up rewriting for words and terms ⋮ The word problem of inverse monoids presented by one idempotent relator ⋮ The finite power property in free groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cancellation rules and extended word problems
• Deux applications de la représentation matricielle d'une série rationnelle non commutative. (Two applications of matrix representations of a rational non -commutative series)
• On the security of ping-pong protocols
• On the security of public key protocols
• A Theorem on Boolean Matrices