Higman's Theorem in Theory of Computation

In this article, we have presented Higman's Theorem in Theory of Computation which was formulated in 1952. We have outlined the overview of proof of Higman's Theorem.

Table of contents:

  1. Higman's Theorem in Theory of Computation
  2. Proof of Higman's Theorem

Let us get started with Higman's Theorem in Theory of Computation.

Higman's Theorem in Theory of Computation

Basic terms to understand Higman's Theorem in Theory of Computation:

Σ is a finite alphabet.

For two given strings x and y which belongs to Σ*, x is a subsequence of y if x can be obtained from y by deleting zero or more alphabets in y.
L be a language which is a proper subset of Σ*.

We define subsequence as:

SUBSEQ(L) = {x : there exists y ∈ L such that x is a subsequence of y}.

In simple terms, SUBSEQ(L) is a language that consist of subsequence of all strings in L.

Highman's Theorem states that: For any finite alphabet Σ and for a given language L which is a proper subset of Σ*, then the language SUBSEQ(L) is a regular language.

Higman's Theorem was found in 1952.

Proof of Higman's Theorem

To prove Higman's Theorem, we need to prove or use an existing result which was first formulated in 1913:

Consider the case Σ = {0, 1}.

If L = null or SUBSEQ(L) = {0, 1}* , then SUBSEQ(L) is a Regular Language by default. Therefore, assume L is non-empty language and SUBSEQ(L) is a proper subset of {0, 1} *.

Prove the following first:

  • SUBSEQ(L) is a proper subset of A.
  • not SUBSEQ(L) = (A intersection (not SUBSEQ(L)) union (not A)
  • The Language (not A) is a Regular Language.
  • If b belongs to {0, 1} and o <= k <= N and x is an element of Mbk, then the Language { y belongs to Abk : x is a subsequence of y} is described by the regular expression 11111* 0000* 11* 0000*
  • For each b belonging to {0, 1} and o <= k <= N, the set Mbk is a finite set.

You will eventually arrive at: Since not SUBSEQ(L) is a Regular Language, the Language SUBSEQ(L) is a Regular Language based on the Higman's Theorem.

With this article at OpenGenus, you must have the complete idea of Higman's Theorem in Theory of Computation.