Eylem Seç
On LM-Systems and Forward Closed String Rewriting Systems
Başlık:
On LM-Systems and Forward Closed String Rewriting Systems
Yazar:
Hono, Daniel S., II, author.
ISBN:
9780438004375
Yazar Ek Girişi:
Fiziksel Tanımlama:
1 electronic resource (74 pages)
Genel Not:
Source: Dissertation Abstracts International, Volume: 79-10(E), Section: B.
Advisors: Paliath Narendran Committee members: Christopher Lynch; Neil Murray.
Özet:
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.
Notlar:
School code: 0668
Konu Başlığı:
Tüzel Kişi Ek Girişi:
Mevcut:*
Yer Numarası | Demirbaş Numarası | Shelf Location | Lokasyon / Statüsü / İade Tarihi |
---|---|---|---|
XX(680590.1) | 680590-1001 | Proquest E-Tez Koleksiyonu | Arıyor... |
On Order
Liste seç
Bunu varsayılan liste yap.
Öğeler başarıyla eklendi
Öğeler eklenirken hata oldu. Lütfen tekrar deneyiniz.
:
Select An Item
Data usage warning: You will receive one text message for each title you selected.
Standard text messaging rates apply.