|
eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1813/6849
| Title: | A Constructive Proof of Higman's Lemma |
| Authors: | Murthy, Chetan R.
Russell, James R. |
| Keywords: | computer science
technical report |
| Issue Date: | Oct-1989 |
| Publisher: | Cornell University |
| Citation: | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-1049 |
| Abstract: | Higman's Lemma is a special case of the more general Kruskal's tree embedding theorem and the graph minor theorem. Prior to this work, only classical (and impredicative) proofs of the Lemma were known. Recently, there has been much interest in developing a constructive proof of the Lemma, primarily via Friedman's A-translation. In this paper we present a direct constructive proof. We achieve this by reducing the problem to a construction of certain sets of sequential regular expressions. We then exhibit a well-founded order on such sets, and the Lemma then follows by induction. |
| URI: | http://hdl.handle.net/1813/6849 |
| Appears in Collections: | Computer Science Technical Reports
|
Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.
|
