Certification Problem

Input (TPDB SRS_Standard/ICFP_2010/259405)

The rewrite relation of the following TRS is considered.

Property / Task

Prove or disprove termination.

Answer / Result

Yes.

Proof (by matchbox @ termCOMP 2023)

1 Closure Under Flat Contexts

Using the flat contexts

{1(☐), 0(☐)}

We obtain the transformed TRS

1.1 Semantic Labeling

The following interpretations form a model of the rules.

As carrier we take the set {0,1}. Symbols are labeled by the interpretation of their arguments using the interpretations (modulo 2):

[1(x₁)]	=	2x₁ + 0
[0(x₁)]	=	2x₁ + 1

We obtain the labeled TRS

There are 128 ruless (increase limit for explicit display).

1.1.1 Rule Removal

Using the matrix interpretations of dimension 1 with strict dimension 1 over the rationals with delta = 1

[1₀(x₁)]

x₁ +

[1₁(x₁)]

x₁ +

[0₀(x₁)]

x₁ +

[0₁(x₁)]

x₁ +

all of the following rules can be deleted.

There are 128 ruless (increase limit for explicit display).

1.1.1.1 R is empty

There are no rules in the TRS. Hence, it is terminating.

0(0(1(0(1(1(0(0(0(0(1(0(1(1(0(1(0(0(0(1(1(1(1(0(1(0(1(0(0(1(1(1(1(1(1(0(0(0(1(0(0(1(0(0(1(1(0(0(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(0(1(1(0(0(0(1(0(0(1(1(1(0(0(0(0(1(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(1)
0(0(1(0(1(1(0(0(0(0(1(0(1(1(0(1(0(0(0(1(1(1(1(0(1(0(1(0(0(1(1(1(1(1(1(0(0(0(1(0(0(1(0(0(1(1(0(0(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(0(0(0(0(0(0(1(1(1(1(1(0(1(0(0(1(1(0(1(0(0(0(1(0(0(1(1(1(0(0(0(1(0(1(0(1(1(0(0(1(0(0(0(1(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(2)
0(0(1(1(0(0(1(0(0(1(1(1(1(0(1(0(1(1(1(0(1(0(1(0(1(0(1(0(0(1(1(0(0(1(0(0(0(0(0(0(0(1(1(0(1(0(1(1(0(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(1(0(0(1(1(0(1(0(1(1(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(0(0(1(0(1(1(0(1(0(1(1(0(0(1(1(0(1(0(0(0(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(3)
0(0(1(1(0(0(1(0(0(1(1(1(1(0(1(0(1(1(1(0(1(0(1(0(1(0(1(0(0(1(1(0(0(1(0(0(0(0(0(0(0(1(1(0(1(0(1(1(0(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(0(1(1(1(1(1(0(0(1(0(0(0(1(0(1(1(1(0(1(0(1(1(1(0(0(0(1(0(1(1(0(1(1(0(1(0(0(1(1(0(1(0(1(0(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(4)
0(0(1(1(0(0(1(0(0(1(1(1(1(0(1(0(1(1(1(0(1(0(1(0(1(0(1(0(0(1(1(0(0(1(0(0(0(0(0(0(0(1(1(0(1(0(1(1(0(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(0(1(0(1(1(0(0(0(0(1(0(1(1(0(1(0(0(0(1(1(1(1(0(1(0(1(0(0(1(1(1(1(1(1(0(0(0(1(0(0(1(0(0(1(1(0(0(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(5)
0(1(0(0(1(1(0(0(0(0(1(1(1(0(1(1(0(0(0(1(1(0(1(1(0(0(1(1(1(0(0(1(0(1(0(0(0(1(1(0(1(1(1(0(1(1(0(1(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(0(1(1(1(1(1(0(0(1(0(0(0(1(0(1(1(1(0(1(0(1(1(1(0(0(0(1(0(1(1(0(1(1(0(1(0(0(1(1(0(1(0(1(0(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(6)
0(1(0(0(1(1(0(0(0(0(1(1(1(0(1(1(0(0(0(1(1(0(1(1(0(0(1(1(1(0(0(1(0(1(0(0(0(1(1(0(1(1(1(0(1(1(0(1(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(0(0(0(0(0(0(1(1(1(1(1(0(1(0(0(1(1(0(1(0(0(0(1(0(0(1(1(1(0(0(0(1(0(1(0(1(1(0(0(1(0(0(0(1(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(7)
0(1(0(0(1(1(0(0(0(0(1(1(1(0(1(1(0(0(0(1(1(0(1(1(0(0(1(1(1(0(0(1(0(1(0(0(0(1(1(0(1(1(1(0(1(1(0(1(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(0(1(0(1(1(0(0(0(0(1(0(1(1(0(1(0(0(0(1(1(1(1(0(1(0(1(0(0(1(1(1(1(1(1(0(0(0(1(0(0(1(0(0(1(1(0(0(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(8)
0(1(0(0(1(1(0(0(0(0(1(1(1(0(1(1(0(0(0(1(1(0(1(1(0(0(1(1(1(0(0(1(0(1(0(0(0(1(1(0(1(1(1(0(1(1(0(1(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(1(0(0(1(1(0(0(1(1(0(0(0(0(0(0(1(0(0(1(1(1(1(1(0(1(0(0(0(0(0(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(1(1(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(9)
0(1(0(0(1(1(0(0(0(0(1(1(1(0(1(1(0(0(0(1(1(0(1(1(0(0(1(1(1(0(0(1(0(1(0(0(0(1(1(0(1(1(1(0(1(1(0(1(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(1(0(0(0(0(0(1(1(0(1(0(0(1(0(0(0(0(1(1(0(0(1(0(0(1(1(0(0(1(1(1(0(1(0(1(1(1(0(1(0(0(1(0(1(0(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(10)
0(1(0(0(1(1(0(0(0(0(1(1(1(0(1(1(0(0(0(1(1(0(1(1(0(0(1(1(1(0(0(1(0(1(0(0(0(1(1(0(1(1(1(0(1(1(0(1(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(1(0(0(1(1(0(0(1(1(0(0(0(0(0(0(1(0(0(1(1(1(1(1(0(1(0(0(0(0(0(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(1(1(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(11)
0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(0(1(1(0(0(0(1(0(0(1(1(1(0(0(0(0(1(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(1(0(0(1(1(0(0(1(1(0(0(0(0(0(0(1(0(0(1(1(1(1(1(0(1(0(0(0(0(0(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(1(1(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(12)
0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(0(1(1(0(0(0(1(0(0(1(1(1(0(0(0(0(1(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(0(1(1(1(1(1(0(0(1(0(0(0(1(0(1(1(1(0(1(0(1(1(1(0(0(0(1(0(1(1(0(1(1(0(1(0(0(1(1(0(1(0(1(0(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(13)
0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(0(1(1(0(0(0(1(0(0(1(1(1(0(0(0(0(1(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(0(1(1(0(0(0(1(0(0(1(1(1(0(0(0(0(1(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(14)
0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(0(1(1(0(0(0(1(0(0(1(1(1(0(0(0(0(1(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(1(0(0(0(0(0(1(1(0(1(0(0(1(0(0(0(0(1(1(0(0(1(0(0(1(1(0(0(1(1(1(0(1(0(1(1(1(0(1(0(0(1(0(1(0(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(15)
0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(0(1(1(0(0(0(1(0(0(1(1(1(0(0(0(0(1(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(0(1(0(1(1(0(0(0(0(1(0(1(1(0(1(0(0(0(1(1(1(1(0(1(0(1(0(0(1(1(1(1(1(1(0(0(0(1(0(0(1(0(0(1(1(0(0(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(16)
0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(0(1(1(0(0(0(1(0(0(1(1(1(0(0(0(0(1(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(0(1(1(0(0(0(1(0(0(1(1(1(0(0(0(0(1(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(17)
0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(0(1(1(0(0(0(1(0(0(1(1(1(0(0(0(0(1(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(0(1(1(1(1(1(0(0(1(0(0(0(1(0(1(1(1(0(1(0(1(1(1(0(0(0(1(0(1(1(0(1(1(0(1(0(0(1(1(0(1(0(1(0(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(18)
0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(0(1(1(0(0(0(1(0(0(1(1(1(0(0(0(0(1(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(1(0(0(0(0(0(1(1(0(1(0(0(1(0(0(0(0(1(1(0(0(1(0(0(1(1(0(0(1(1(1(0(1(0(1(1(1(0(1(0(0(1(0(1(0(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(19)
0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(0(1(1(0(0(0(1(0(0(1(1(1(0(0(0(0(1(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(0(1(1(0(0(0(1(0(0(1(1(1(0(0(0(0(1(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(20)
0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(1(0(0(1(0(0(0(1(0(0(1(1(1(0(0(0(1(1(0(1(1(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(0(1(1(1(1(1(0(0(1(0(0(0(1(0(1(1(1(0(1(0(1(1(1(0(0(0(1(0(1(1(0(1(1(0(1(0(0(1(1(0(1(0(1(0(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(21)
0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(1(0(0(1(0(0(0(1(0(0(1(1(1(0(0(0(1(1(0(1(1(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(0(1(1(1(1(1(0(0(1(0(0(0(1(0(1(1(1(0(1(0(1(1(1(0(0(0(1(0(1(1(0(1(1(0(1(0(0(1(1(0(1(0(1(0(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(22)
0(1(0(0(1(1(0(0(1(1(0(0(0(1(0(0(0(1(0(0(1(0(1(1(1(1(0(1(0(1(0(0(1(0(0(0(1(0(0(1(1(1(0(0(0(1(1(0(1(1(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(0(0(0(0(0(0(1(1(1(1(1(0(1(0(0(1(1(0(1(0(0(0(1(0(0(1(1(1(0(0(0(1(0(1(0(1(1(0(0(1(0(0(0(1(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(23)
0(1(0(0(1(1(0(1(0(1(1(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(0(0(1(0(1(1(0(1(0(1(1(0(0(1(1(0(1(0(0(0(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(0(1(1(1(1(1(0(0(1(0(0(0(1(0(1(1(1(0(1(0(1(1(1(0(0(0(1(0(1(1(0(1(1(0(1(0(0(1(1(0(1(0(1(0(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(24)
0(1(0(0(1(1(0(1(0(1(1(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(0(0(1(0(1(1(0(1(0(1(1(0(0(1(1(0(1(0(0(0(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(0(1(1(1(1(1(0(0(1(0(0(0(1(0(1(1(1(0(1(0(1(1(1(0(0(0(1(0(1(1(0(1(1(0(1(0(0(1(1(0(1(0(1(0(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(25)
0(1(0(0(1(1(0(1(0(1(1(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(0(0(1(0(1(1(0(1(0(1(1(0(0(1(1(0(1(0(0(0(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(0(1(1(1(1(1(0(0(1(0(0(0(1(0(1(1(1(0(1(0(1(1(1(0(0(0(1(0(1(1(0(1(1(0(1(0(0(1(1(0(1(0(1(0(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(26)
0(1(0(0(1(1(0(1(0(1(1(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(0(0(1(0(1(1(0(1(0(1(1(0(0(1(1(0(1(0(0(0(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(1(0(0(1(1(0(1(0(1(1(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(0(0(1(0(1(1(0(1(0(1(1(0(0(1(1(0(1(0(0(0(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(27)
0(1(0(0(1(1(0(1(0(1(1(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(0(0(1(0(1(1(0(1(0(1(1(0(0(1(1(0(1(0(0(0(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(1(0(0(0(0(0(1(1(0(1(0(0(1(0(0(0(0(1(1(0(0(1(0(0(1(1(0(0(1(1(1(0(1(0(1(1(1(0(1(0(0(1(0(1(0(0(1(1(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(28)
0(1(0(0(1(1(0(1(0(1(1(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(0(0(1(0(1(1(0(1(0(1(1(0(0(1(1(0(1(0(0(0(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(0(1(1(1(1(1(0(0(1(0(0(0(1(0(1(1(1(0(1(0(1(1(1(0(0(0(1(0(1(1(0(1(1(0(1(0(0(1(1(0(1(0(1(0(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(29)
0(1(0(0(1(1(0(1(0(1(1(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(0(0(1(0(1(1(0(1(0(1(1(0(0(1(1(0(1(0(0(0(0(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	0(1(0(0(1(1(0(0(1(1(0(0(0(0(0(0(1(0(0(1(1(1(1(1(0(1(0(0(0(0(0(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(1(1(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(30)
0(1(0(0(1(1(0(1(0(1(1(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(0(0(1(0(1(1(0(1(0(1(1(0(0(1(1(0(1(0(0(1(0(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(0(1(1(1(1(1(0(0(1(0(0(0(1(0(1(1(1(0(1(0(1(1(1(0(0(0(1(0(1(1(0(1(1(0(1(0(0(1(1(0(1(0(1(0(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(31)
0(1(0(0(1(1(0(1(0(1(1(1(1(1(0(1(0(1(0(0(0(0(0(0(0(1(0(1(0(0(1(0(1(1(0(1(0(1(1(0(0(1(1(0(1(0(0(1(0(0(1(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	→	1(0(1(1(1(1(1(0(0(1(0(0(0(1(0(1(1(1(0(1(0(1(1(1(0(0(0(1(0(1(1(0(1(1(0(1(0(0(1(1(0(1(0(1(0(0(0(1(1(0(0(...display limit reached...)))))))))))))))))))))))))))))))))))))))))))))))))))	(32)