Dissertation/Thesis Abstract

The author has requested that access to this graduate work be delayed until 2020-05-29. After this date, this graduate work will be available on an open access basis.
On LM-Systems and Forward Closed String Rewriting Systems
by Hono, Daniel S., II, Ph.D., State University of New York at Albany, 2018, 74; 10810387
Abstract (Summary)

The E-Unification problem appears in important application areas, e.g. automated deduction and cryptographic protocol analysis. As E-Unification is undecidable in general, there is an active search for decidable and, ideally, tractable instances of the problem.

In this dissertation we investigate a class of equational theories, which we call LM-Systems, that give rise to E-Unification problems solvable in polynomial time. This remarkable class of theories was first discovered by Dr. Christopher Lynch and Dr. Barbara Morawska in their paper ``Basic Syntactic Mutation". We adapt their definitions to convergent and forward-closed term-rewriting systems, and show that LM-Systems are highly restrictive. However, we also prove that the Cap Problem, a known undecidable problem from the field of cryptographic protocol analysis, remains undecidable when restricted to LM-Systems.

Motivated by the definition of LM-Systems, we next investigate the case of forward-closed and convergent string-rewriting systems. We show that the Subterm Collapse problem, which is undecidable for general convergent term-rewriting systems, becomes decidable when restricted to these systems. In particular, there is an algorithm to determine if such a string-rewriting system is an LM-System.

Finally, we show that the Finiteness of Forward-Closure problem, which is undecidable in general, is decidable for convergent and monadic string-rewriting systems.

Indexing (document details)
Advisor: Narendran, Paliath
Commitee: Lynch, Christopher, Murray, Neil
School: State University of New York at Albany
Department: Computer Science
School Location: United States -- New York
Source: DAI-B 79/10(E), Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Computer science
Keywords: LM-systems, Term rewriting, Unification
Publication Number: 10810387
ISBN: 9780438004375
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest