String Rewriting and Security Analysis: An Extension of a Result of Book and Otto
Siva Anantharaman, Paliath Narendran, Michaël Rusinowitch · HAL (Le Centre pour la Communication Scientifique Directe) · 2011
In their seminal work Dolev and Yao used string rewriting to check protocol security against an active intruder. The main technical result and algorithm were improved by Book and Otto who formulated the security check in terms of an extended word problem for cancellation rules. We extend their main decidability result to a larger class of string rewrite systems called opt-monadic systems.