2
$\begingroup$

After looking through many papers, I noticed that most of the discussions and proofs for Higman's Lemma and Kruskal's Tree Theorem only have formal applications in set theory, logic, and type theory. What are some non-formal applications for Higman's Lemma and/or Kruskal's Tree Theorem?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Not sure what you mean by "informal". Some people might define math as the study of formal structures, so... Can you give an example of what you mean by an "informal application", not related to the theorems mentioned in your question? $\endgroup$
    – Todd Trimble
    Commented Jan 17, 2016 at 0:21
  • 1
    $\begingroup$ @ToddTrimble What I mean is like other fields of mathematics like geometry or Ramsey Theory, etc. $\endgroup$
    – Julian Rachman
    Commented Jan 17, 2016 at 0:23

2 Answers 2

Reset to default
3
$\begingroup$

I believe the correctness proof of the Knuth-Bendix completion algorithm uses Kruskal's theorem.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ How so? Can you show me? $\endgroup$
    – Julian Rachman
    Commented Jan 17, 2016 at 7:35
3
$\begingroup$

Unsurprisingly, there are various ways in which Higman's lemma is used in the context of Gröbner bases. One interesting recent example : http://www.msri.org/people/members/chillar/files/HS-MonoidGBFiniteness.pdf

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Ah. Quite interesting. I will have to learn some ring theory before attempting to truly understand this paper. $\endgroup$
    – Julian Rachman
    Commented Jan 17, 2016 at 22:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .