Certification Problem

Input (TPDB SRS_Standard/ICFP_2010/157388)

The rewrite relation of the following TRS is considered.

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

Property / Task

Answer / Result

Proof (by matchbox @ termCOMP 2023)

1 String Reversal

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

1.1 Dependency Pair Transformation

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

1.1.1 Monotonic Reduction Pair Processor with Usable Rules

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

1.1.1.1 Dependency Graph Processor

The dependency pairs are split into 1 component.

• The 1^st component contains the pair

  1#(1(2(3(4(x1)))))	→	1#(x1)	(351)
  1#(1(5(3(4(x1)))))	→	1#(x1)	(320)
  1#(1(5(1(4(x1)))))	→	1#(x1)	(330)

  1.1.1.1.1 Monotonic Reduction Pair Processor with Usable Rules

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

  [5(x1)]	=	x1 + 1
  [4(x1)]	=	x1 + 1
  [3(x1)]	=	x1 + 1
  [2(x1)]	=	x1 + 1
  [1(x1)]	=	x1 + 1
  [1#(x1)]	=	x1 + 0

  having no usable rules (w.r.t. the implicit argument filter of the reduction pair), the pairs

  1#(1(2(3(4(x1)))))	→	1#(x1)	(351)
  1#(1(5(3(4(x1)))))	→	1#(x1)	(320)
  1#(1(5(1(4(x1)))))	→	1#(x1)	(330)

  and no rules could be deleted.

  1.1.1.1.1.1 Dependency Graph Processor

  The dependency pairs are split into 0 components.