Certification Problem

Input (TPDB TRS_Equational/AProVE_AC_04/AC53)

The rewrite relation of the following equational TRS is considered.

Associative symbols: times

Commutative symbols: times

Property / Task

Answer / Result

Proof (by NaTT @ termCOMP 2023)

1 AC Dependency Pair Transformation

• The following set of (strict) dependency pairs is constructed for the TRS.

  fac#(s(x))	→	p#(s(x))	(6)
  fac#(s(x))	→	fac#(p(s(x)))	(7)

  Finiteness for these DPs in combination with the equational DPs is proven as follows.

  1.1 Dependency Graph Processor

  The dependency pairs are split into 1 component.

  • The 1^st component contains the pair

    fac#(s(x))

    →

    fac#(p(s(x)))

    (7)

    1.1.1 AC Reduction Pair Processor with Usable Rules

    Using the argument filter

    π(fac#)

    =

    1

    in combination with the following Weighted Path Order with the following precedence and status

    prec(s)	=	1		status(s)	=	[1]		list-extension(s)	=	Lex
    prec(p#)	=	0		status(p#)	=	[]		list-extension(p#)	=	Lex
    prec(p)	=	0		status(p)	=	[]		list-extension(p)	=	Lex
    prec(0)	=	0		status(0)	=	[]		list-extension(0)	=	Lex
    prec(times)	=	0		status(times)	=	[]		list-extension(times)	=	Lex
    prec(fac)	=	0		status(fac)	=	[]		list-extension(fac)	=	Lex

    and the following Max-polynomial interpretation

    [s(x1)]	=	x1 + 7720
    [p#(x1)]	=	1
    [p(x1)]	=	x1 + 0
    [0]	=	0
    [times(x1, x2)]	=	0
    [fac(x1)]	=	1

    together with the usable rule

    p(s(x))

    →

    x

    (1)

    (w.r.t. the implicit argument filter of the reduction pair), the pair

    fac#(s(x))

    →

    fac#(p(s(x)))

    (7)

    could be deleted.

    1.1.1.1 Dependency Graph Processor

    The dependency pairs are split into 0 components.