Cancellation rules and extended word problems

DOI10.1016/0020-0190(85)90122-XMaRDI QIDQ2266586zbMATH OpenFDO

Authors Ronald V. Book, Friedrich Otto

Publication date 1985

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

Full work available at URL https://doi.org/10.1016/0020-0190(85)90122-X

zbMATH Keywords

cancellation rulesChurch-Rosser propertycongruencesextended word problemnondeterministic finite state acceptorpolynomial-time algorithmssecurityThue systemstwo-party protocols

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Word problems, etc. in computability and recursion theory (03D40) Formal languages and automata (68Q45) Abstract data types; algebraic specification (68Q65) Communication, information (94A99)

Recommendations

• On the complexity of some extended word problems defined by cancellation rules
• The cancellation problem
• Cancellation and regular derivations
• scientific article; zbMATH DE number 1517014
• On the cancellation problem
• On generalized cancellation problem

Cites work

• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Decidable sentences of Church-Rosser congruences
• Homogeneous Thue systems and the Church-Rosser property
• scientific article; zbMATH DE number 3898258 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• Monadic Thue systems
• On the security of ping-pong protocols
• On the security of public key protocols
• Some undecidability results for non-monadic Church-Rosser Thue systems

Cited in

(9)

• On the security of name-stamp protocols
• On the verifiability of two-party algebraic protocols
• Thue systems as rewriting systems
• On the security of p-party protocols
• The word problem of inverse monoids presented by one idempotent relator
• Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems
• FINDING FINITE AUTOMATA THAT CERTIFY TERMINATION OF STRING REWRITING SYSTEMS
• On the complexity of some extended word problems defined by cancellation rules
• Some undecidable termination problems for semi-Thue systems

This page was built for publication: Cancellation rules and extended word problems

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