Certification Problem

Input (TPDB SRS_Standard/ICFP_2010/212480)

The rewrite relation of the following TRS is considered.

Property / Task

Answer / Result

Proof (by matchbox @ termCOMP 2023)

1 String Reversal

1.1 Dependency Pair Transformation

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

1.1.1 Monotonic Reduction Pair Processor with Usable Rules

1.1.1.1 Dependency Graph Processor

The dependency pairs are split into 2 components.

• The 1^st component contains the pair

  1#(3(0(3(x1))))	→	1#(x1)	(214)
  1#(4(2(4(0(x1)))))	→	1#(x1)	(173)
  1#(4(2(0(x1))))	→	1#(x1)	(176)
  1#(3(0(x1)))	→	1#(x1)	(210)

  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

  [4(x1)]	=	x1 + 1
  [3(x1)]	=	x1 + 1
  [2(x1)]	=	x1 + 1
  [0(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#(3(0(3(x1))))	→	1#(x1)	(214)
  1#(4(2(4(0(x1)))))	→	1#(x1)	(173)
  1#(4(2(0(x1))))	→	1#(x1)	(176)
  1#(3(0(x1)))	→	1#(x1)	(210)

  and no rules could be deleted.

  1.1.1.1.1.1 Dependency Graph Processor

  The dependency pairs are split into 0 components.

• The 2^nd component contains the pair

  1#(0(3(3(x1))))

  →

  1#(0(x1))

  (220)

  1.1.1.1.2 Monotonic Reduction Pair Processor with Usable Rules

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

  [3(x1)]	=	x1 + 1
  [0(x1)]	=	x1 + 0
  [1#(x1)]	=	x1 + 0

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

  1#(0(3(3(x1))))

  →

  1#(0(x1))

  (220)

  and no rules could be deleted.

  1.1.1.1.2.1 Dependency Graph Processor

  The dependency pairs are split into 0 components.