2017/06/18 by Zümrüt Akçam, Akçam, Zümrüt, Daniel S. Hono +3
Computer Science · #Advanced Authentication Protocols Security #Cryptography and Data Security #Digital Rights Management and Security #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)
paper · pdf · doi:10.48550/arxiv.1706.05607
openalex publication_date 2017/06/18 · openalex created_date 2017/06/30 · openalex updated_date 2026/07/28
In this paper, we investigate a problem dual to the unification problem, namely the Common Term (CT) problem for string rewriting systems. Our main motivation was in computing fixed points in systems, such as loop invariants in programming languages. We show that the fixed point problem is reducible to the common term problem. We also prove that the common term problem is undecidable for dwindling string rewriting systems.