Cancellation rules and extended word problems

DOI10.1016/0020-0190(85)90122-XzbMath0561.68030MaRDI QIDQ2266586

Friedrich Otto, Ronald V. Book

Publication date: 1985

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

zbMATH Keywords

securitycongruencespolynomial-time algorithmscancellation rulesThue systemsChurch-Rosser propertyextended word problemnondeterministic finite state acceptortwo-party protocols

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Decidable sentences of Church-Rosser congruences
• Homogeneous Thue systems and the Church-Rosser property
• Some undecidability results for non-monadic Church-Rosser Thue systems
• Monadic Thue systems
• On the security of ping-pong protocols
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• On the security of public key protocols