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)

Review text

\textit{D. Dolev} and \textit{A. C. Yao} [IEEE Trans. Inf. Theory IT-29, 198- 208 (1983; Zbl 0502.94005)] developed formal models of two-party protocols. Here the sets of cancellation rules underlying their models are shown to be finite homogeneous Thue systems of degree 2 that are Church-Rosser. Now the question of whether or not a given protocol is secure in the sense of Dolev and Yao can be stated as a special case of the following extended word problem: Instance: Two regular sets R and F on \(\Sigma\). Question: Does there exist \(\alpha\in R\) and \(\beta\in F\) such that \(\alpha\) is reducible to \(\beta\) ? Conceptually simple polynomial-time algorithms are given for the above problem and for the following decision problem: Instance: Two regular sets R and F on \(\Sigma\). Question: Does there exist \(\alpha\in R\) and \(\beta\in F\) such that \(\alpha\) is congruent to \(\beta\) ? These algorithms are based on a construction that given a nondeterministic finite state acceptor A with m states yields in \(O(m^ 4)\) steps a nondeterministic finite state acceptor with m states, that recognizes the set of descendants of L(A) modulo a given finite homogeneous Thue system of degree 2. All these results can be extended to finite monadic Thue systems, however, the complexity bounds then depend on the maximum length of the left-hand sides of the rules of the Thue system under consideration.

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)