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

DOI10.1016/0020-0190(86)90087-6MaRDI QIDQ578921zbMATH OpenOpenAlexFDO

Authors Michèle Benois, Jacques Sakarovitch

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

algorithmcancellation rulescomplexity boundsset of descendants of a regular setThue systemsword problems

Mathematics Subject Classification ID

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

Review text

We give an algorithm which computes the set of descendants of a regular set R, for Thue systems of certain type. The complexity of the algorithm is \(O(m^ 3)\) where m is the number of states of an automaton recognising R. This allows to improve the known complexity bounds for some extended word problems defined by cancellation rules.

Recommendations

• Cancellation rules and extended word problems
• On two problems related to cancellativity
• Dehn's Algorithm and the Complexity of Word Problems
• scientific article; zbMATH DE number 1615237
• Decision problems for semi-Thue systems with a few rules

Cites work

• A Theorem on Boolean Matrices
• 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)
• scientific article; zbMATH DE number 3150488 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3339488 (Why is no real title available?)
• On the security of ping-pong protocols
• On the security of public key protocols

Cited in

(14)

• On the security of p-party protocols
• The word problem of inverse monoids presented by one idempotent relator
• The finite power property in free groups
• On a method for proving exact bounds on derivational complexity in Thue systems
• Cancellation rules and extended word problems
• scientific article; zbMATH DE number 4049112 (Why is no real title available?)
• scientific article; zbMATH DE number 2068882 (Why is no real title available?)
• An automata theoretic approach to the generalized word problem in graphs of groups.
• Rational cross-sections, bounded generation, and orders on groups
• Subgroup membership in \(\mathrm{GL}(2, \mathrm{Z})\)
• Membership problems in nilpotent groups
• Subgroup membership in GL\((2,\mathbb{Z})\)
• Bottom-up rewriting for words and terms
• Some decision problems about controlled rewriting systems

This page was built for publication: On the complexity of some extended word problems defined by cancellation rules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q578921)