2016/04/21 by Daniel S. Hono, Hono, Daniel S., Paliath Narendran +3
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.1604.06509
openalex publication_date 2016/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate properties of convergent and forward-closed string rewriting systems in the context of the syntactic criteria introduced in \citeLynchMorawska by Christopher Lynch and Barbara Morawska (we call these LM-Systems). Since a string rewriting system can be viewed as a term-rewriting system over a signature of purely monadic function symbols, we adapt their definition to the string rewriting case. We prove that the subterm-collapse problem for convergent and forward-closed string rewriting systems is effectively solvable. Therefore, there exists a decision procedure that verifies if such a system is an LM-System. We use the same construction to prove that the cap problem from the field of cryptographic protocol analysis, which is undecidable for general LM-systems, is decidable when restricted to the string rewriting case.