Term Rewriting System R:
[x]
rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)

Innermost Termination of R to be shown. 



   R
     ↳Dependency Pair Analysis



R contains the following Dependency Pairs:

REC(rec(x)) -> SENT(rec(x))
REC(sent(x)) -> SENT(rec(x))
REC(sent(x)) -> REC(x)
REC(no(x)) -> SENT(rec(x))
REC(no(x)) -> REC(x)
REC(bot) -> SENT(bot)
REC(up(x)) -> REC(x)
SENT(up(x)) -> SENT(x)
NO(up(x)) -> NO(x)
TOP(rec(up(x))) -> TOP(check(rec(x)))
TOP(rec(up(x))) -> CHECK(rec(x))
TOP(rec(up(x))) -> REC(x)
TOP(sent(up(x))) -> TOP(check(rec(x)))
TOP(sent(up(x))) -> CHECK(rec(x))
TOP(sent(up(x))) -> REC(x)
TOP(no(up(x))) -> TOP(check(rec(x)))
TOP(no(up(x))) -> CHECK(rec(x))
TOP(no(up(x))) -> REC(x)
CHECK(up(x)) -> CHECK(x)
CHECK(sent(x)) -> SENT(check(x))
CHECK(sent(x)) -> CHECK(x)
CHECK(rec(x)) -> REC(check(x))
CHECK(rec(x)) -> CHECK(x)
CHECK(no(x)) -> NO(check(x))
CHECK(no(x)) -> CHECK(x)

Furthermore, R contains six SCCs. 


   R
     ↳DPs
       →DP Problem 1
         ↳Forward Instantiation Transformation
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pair:

SENT(up(x)) -> SENT(x)


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

SENT(up(x)) -> SENT(x)
one new Dependency Pair is created:

SENT(up(up(x''))) -> SENT(up(x''))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
           →DP Problem 7
             ↳Forward Instantiation Transformation
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pair:

SENT(up(up(x''))) -> SENT(up(x''))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

SENT(up(up(x''))) -> SENT(up(x''))
one new Dependency Pair is created:

SENT(up(up(up(x'''')))) -> SENT(up(up(x'''')))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
           →DP Problem 7
             ↳FwdInst
             ...
               →DP Problem 8
                 ↳Polynomial Ordering
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pair:

SENT(up(up(up(x'''')))) -> SENT(up(up(x'''')))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




The following dependency pair can be strictly oriented:

SENT(up(up(up(x'''')))) -> SENT(up(up(x'''')))


There are no usable rules for innermost that need to be oriented.

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(up(x1))=  1 + x1  
  POL(SENT(x1))=  1 + x1  

resulting in one new DP problem. 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
           →DP Problem 7
             ↳FwdInst
             ...
               →DP Problem 9
                 ↳Dependency Graph
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pair:


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.


   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳Forward Instantiation Transformation
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pair:

NO(up(x)) -> NO(x)


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

NO(up(x)) -> NO(x)
one new Dependency Pair is created:

NO(up(up(x''))) -> NO(up(x''))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
           →DP Problem 10
             ↳Forward Instantiation Transformation
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pair:

NO(up(up(x''))) -> NO(up(x''))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

NO(up(up(x''))) -> NO(up(x''))
one new Dependency Pair is created:

NO(up(up(up(x'''')))) -> NO(up(up(x'''')))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
           →DP Problem 10
             ↳FwdInst
             ...
               →DP Problem 11
                 ↳Polynomial Ordering
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pair:

NO(up(up(up(x'''')))) -> NO(up(up(x'''')))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




The following dependency pair can be strictly oriented:

NO(up(up(up(x'''')))) -> NO(up(up(x'''')))


There are no usable rules for innermost that need to be oriented.

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(NO(x1))=  1 + x1  
  POL(up(x1))=  1 + x1  

resulting in one new DP problem. 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
           →DP Problem 10
             ↳FwdInst
             ...
               →DP Problem 12
                 ↳Dependency Graph
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pair:


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.


   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳Forward Instantiation Transformation
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pair:

REC(up(x)) -> REC(x)


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

REC(up(x)) -> REC(x)
one new Dependency Pair is created:

REC(up(up(x''))) -> REC(up(x''))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
           →DP Problem 13
             ↳Forward Instantiation Transformation
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pair:

REC(up(up(x''))) -> REC(up(x''))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

REC(up(up(x''))) -> REC(up(x''))
one new Dependency Pair is created:

REC(up(up(up(x'''')))) -> REC(up(up(x'''')))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
           →DP Problem 13
             ↳FwdInst
             ...
               →DP Problem 14
                 ↳Polynomial Ordering
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pair:

REC(up(up(up(x'''')))) -> REC(up(up(x'''')))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




The following dependency pair can be strictly oriented:

REC(up(up(up(x'''')))) -> REC(up(up(x'''')))


There are no usable rules for innermost that need to be oriented.

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(up(x1))=  1 + x1  
  POL(REC(x1))=  1 + x1  

resulting in one new DP problem. 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
           →DP Problem 13
             ↳FwdInst
             ...
               →DP Problem 15
                 ↳Dependency Graph
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pair:


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.


   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳Forward Instantiation Transformation
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pairs:

REC(no(x)) -> REC(x)
REC(sent(x)) -> REC(x)


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

REC(sent(x)) -> REC(x)
two new Dependency Pairs are created:

REC(sent(sent(x''))) -> REC(sent(x''))
REC(sent(no(x''))) -> REC(no(x''))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
           →DP Problem 16
             ↳Forward Instantiation Transformation
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pairs:

REC(sent(no(x''))) -> REC(no(x''))
REC(sent(sent(x''))) -> REC(sent(x''))
REC(no(x)) -> REC(x)


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

REC(no(x)) -> REC(x)
three new Dependency Pairs are created:

REC(no(no(x''))) -> REC(no(x''))
REC(no(sent(sent(x'''')))) -> REC(sent(sent(x'''')))
REC(no(sent(no(x'''')))) -> REC(sent(no(x'''')))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
           →DP Problem 16
             ↳FwdInst
             ...
               →DP Problem 17
                 ↳Forward Instantiation Transformation
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pairs:

REC(no(sent(no(x'''')))) -> REC(sent(no(x'''')))
REC(sent(sent(x''))) -> REC(sent(x''))
REC(no(sent(sent(x'''')))) -> REC(sent(sent(x'''')))
REC(no(no(x''))) -> REC(no(x''))
REC(sent(no(x''))) -> REC(no(x''))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

REC(sent(sent(x''))) -> REC(sent(x''))
two new Dependency Pairs are created:

REC(sent(sent(sent(x'''')))) -> REC(sent(sent(x'''')))
REC(sent(sent(no(x'''')))) -> REC(sent(no(x'''')))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
           →DP Problem 16
             ↳FwdInst
             ...
               →DP Problem 18
                 ↳Forward Instantiation Transformation
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pairs:

REC(sent(sent(no(x'''')))) -> REC(sent(no(x'''')))
REC(sent(sent(sent(x'''')))) -> REC(sent(sent(x'''')))
REC(no(sent(sent(x'''')))) -> REC(sent(sent(x'''')))
REC(no(no(x''))) -> REC(no(x''))
REC(sent(no(x''))) -> REC(no(x''))
REC(no(sent(no(x'''')))) -> REC(sent(no(x'''')))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

REC(sent(no(x''))) -> REC(no(x''))
three new Dependency Pairs are created:

REC(sent(no(no(x'''')))) -> REC(no(no(x'''')))
REC(sent(no(sent(sent(x''''''))))) -> REC(no(sent(sent(x''''''))))
REC(sent(no(sent(no(x''''''))))) -> REC(no(sent(no(x''''''))))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
           →DP Problem 16
             ↳FwdInst
             ...
               →DP Problem 19
                 ↳Forward Instantiation Transformation
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pairs:

REC(sent(no(sent(no(x''''''))))) -> REC(no(sent(no(x''''''))))
REC(sent(no(sent(sent(x''''''))))) -> REC(no(sent(sent(x''''''))))
REC(no(sent(no(x'''')))) -> REC(sent(no(x'''')))
REC(sent(sent(sent(x'''')))) -> REC(sent(sent(x'''')))
REC(no(sent(sent(x'''')))) -> REC(sent(sent(x'''')))
REC(no(no(x''))) -> REC(no(x''))
REC(sent(no(no(x'''')))) -> REC(no(no(x'''')))
REC(sent(sent(no(x'''')))) -> REC(sent(no(x'''')))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

REC(no(no(x''))) -> REC(no(x''))
three new Dependency Pairs are created:

REC(no(no(no(x'''')))) -> REC(no(no(x'''')))
REC(no(no(sent(sent(x''''''))))) -> REC(no(sent(sent(x''''''))))
REC(no(no(sent(no(x''''''))))) -> REC(no(sent(no(x''''''))))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
           →DP Problem 16
             ↳FwdInst
             ...
               →DP Problem 20
                 ↳Forward Instantiation Transformation
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pairs:

REC(no(no(sent(no(x''''''))))) -> REC(no(sent(no(x''''''))))
REC(sent(no(sent(sent(x''''''))))) -> REC(no(sent(sent(x''''''))))
REC(sent(sent(no(x'''')))) -> REC(sent(no(x'''')))
REC(sent(sent(sent(x'''')))) -> REC(sent(sent(x'''')))
REC(no(sent(sent(x'''')))) -> REC(sent(sent(x'''')))
REC(no(no(sent(sent(x''''''))))) -> REC(no(sent(sent(x''''''))))
REC(no(no(no(x'''')))) -> REC(no(no(x'''')))
REC(sent(no(no(x'''')))) -> REC(no(no(x'''')))
REC(no(sent(no(x'''')))) -> REC(sent(no(x'''')))
REC(sent(no(sent(no(x''''''))))) -> REC(no(sent(no(x''''''))))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

REC(no(sent(sent(x'''')))) -> REC(sent(sent(x'''')))
two new Dependency Pairs are created:

REC(no(sent(sent(sent(x''''''))))) -> REC(sent(sent(sent(x''''''))))
REC(no(sent(sent(no(x''''''))))) -> REC(sent(sent(no(x''''''))))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
           →DP Problem 16
             ↳FwdInst
             ...
               →DP Problem 21
                 ↳Forward Instantiation Transformation
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pairs:

REC(sent(no(sent(no(x''''''))))) -> REC(no(sent(no(x''''''))))
REC(no(sent(sent(no(x''''''))))) -> REC(sent(sent(no(x''''''))))
REC(sent(no(sent(sent(x''''''))))) -> REC(no(sent(sent(x''''''))))
REC(sent(sent(no(x'''')))) -> REC(sent(no(x'''')))
REC(sent(sent(sent(x'''')))) -> REC(sent(sent(x'''')))
REC(no(sent(sent(sent(x''''''))))) -> REC(sent(sent(sent(x''''''))))
REC(no(no(sent(sent(x''''''))))) -> REC(no(sent(sent(x''''''))))
REC(no(no(no(x'''')))) -> REC(no(no(x'''')))
REC(sent(no(no(x'''')))) -> REC(no(no(x'''')))
REC(no(sent(no(x'''')))) -> REC(sent(no(x'''')))
REC(no(no(sent(no(x''''''))))) -> REC(no(sent(no(x''''''))))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

REC(no(sent(no(x'''')))) -> REC(sent(no(x'''')))
three new Dependency Pairs are created:

REC(no(sent(no(no(x''''''))))) -> REC(sent(no(no(x''''''))))
REC(no(sent(no(sent(sent(x'''''''')))))) -> REC(sent(no(sent(sent(x'''''''')))))
REC(no(sent(no(sent(no(x'''''''')))))) -> REC(sent(no(sent(no(x'''''''')))))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
           →DP Problem 16
             ↳FwdInst
             ...
               →DP Problem 22
                 ↳Polynomial Ordering
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pairs:

REC(no(sent(no(sent(no(x'''''''')))))) -> REC(sent(no(sent(no(x'''''''')))))
REC(no(sent(no(sent(sent(x'''''''')))))) -> REC(sent(no(sent(sent(x'''''''')))))
REC(no(no(sent(no(x''''''))))) -> REC(no(sent(no(x''''''))))
REC(no(sent(sent(no(x''''''))))) -> REC(sent(sent(no(x''''''))))
REC(sent(no(sent(sent(x''''''))))) -> REC(no(sent(sent(x''''''))))
REC(sent(sent(no(x'''')))) -> REC(sent(no(x'''')))
REC(sent(sent(sent(x'''')))) -> REC(sent(sent(x'''')))
REC(no(sent(sent(sent(x''''''))))) -> REC(sent(sent(sent(x''''''))))
REC(no(no(sent(sent(x''''''))))) -> REC(no(sent(sent(x''''''))))
REC(no(no(no(x'''')))) -> REC(no(no(x'''')))
REC(sent(no(no(x'''')))) -> REC(no(no(x'''')))
REC(no(sent(no(no(x''''''))))) -> REC(sent(no(no(x''''''))))
REC(sent(no(sent(no(x''''''))))) -> REC(no(sent(no(x''''''))))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




The following dependency pairs can be strictly oriented:

REC(no(sent(no(sent(no(x'''''''')))))) -> REC(sent(no(sent(no(x'''''''')))))
REC(no(sent(no(sent(sent(x'''''''')))))) -> REC(sent(no(sent(sent(x'''''''')))))
REC(no(no(sent(no(x''''''))))) -> REC(no(sent(no(x''''''))))
REC(no(sent(sent(no(x''''''))))) -> REC(sent(sent(no(x''''''))))
REC(no(sent(sent(sent(x''''''))))) -> REC(sent(sent(sent(x''''''))))
REC(no(no(sent(sent(x''''''))))) -> REC(no(sent(sent(x''''''))))
REC(no(no(no(x'''')))) -> REC(no(no(x'''')))
REC(no(sent(no(no(x''''''))))) -> REC(sent(no(no(x''''''))))


Additionally, the following usable rules for innermost can be oriented:

sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(no(x1))=  1 + x1  
  POL(up(x1))=  0  
  POL(REC(x1))=  1 + x1  
  POL(sent(x1))=  x1  

resulting in one new DP problem. 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
           →DP Problem 16
             ↳FwdInst
             ...
               →DP Problem 23
                 ↳Dependency Graph
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pairs:

REC(sent(no(sent(sent(x''''''))))) -> REC(no(sent(sent(x''''''))))
REC(sent(sent(no(x'''')))) -> REC(sent(no(x'''')))
REC(sent(sent(sent(x'''')))) -> REC(sent(sent(x'''')))
REC(sent(no(no(x'''')))) -> REC(no(no(x'''')))
REC(sent(no(sent(no(x''''''))))) -> REC(no(sent(no(x''''''))))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




Using the Dependency Graph the DP problem was split into 1 DP problems.


   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
           →DP Problem 16
             ↳FwdInst
             ...
               →DP Problem 24
                 ↳Polynomial Ordering
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pair:

REC(sent(sent(sent(x'''')))) -> REC(sent(sent(x'''')))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




The following dependency pair can be strictly oriented:

REC(sent(sent(sent(x'''')))) -> REC(sent(sent(x'''')))


Additionally, the following usable rule for innermost can be oriented:

sent(up(x)) -> up(sent(x))


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(up(x1))=  0  
  POL(REC(x1))=  1 + x1  
  POL(sent(x1))=  1 + x1  

resulting in one new DP problem. 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
           →DP Problem 16
             ↳FwdInst
             ...
               →DP Problem 25
                 ↳Dependency Graph
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst


Dependency Pair:


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.


   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳Forward Instantiation Transformation
       →DP Problem 6
         ↳FwdInst


Dependency Pair:

CHECK(up(x)) -> CHECK(x)


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

CHECK(up(x)) -> CHECK(x)
one new Dependency Pair is created:

CHECK(up(up(x''))) -> CHECK(up(x''))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
           →DP Problem 26
             ↳Forward Instantiation Transformation
       →DP Problem 6
         ↳FwdInst


Dependency Pair:

CHECK(up(up(x''))) -> CHECK(up(x''))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

CHECK(up(up(x''))) -> CHECK(up(x''))
one new Dependency Pair is created:

CHECK(up(up(up(x'''')))) -> CHECK(up(up(x'''')))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
           →DP Problem 26
             ↳FwdInst
             ...
               →DP Problem 27
                 ↳Polynomial Ordering
       →DP Problem 6
         ↳FwdInst


Dependency Pair:

CHECK(up(up(up(x'''')))) -> CHECK(up(up(x'''')))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




The following dependency pair can be strictly oriented:

CHECK(up(up(up(x'''')))) -> CHECK(up(up(x'''')))


There are no usable rules for innermost that need to be oriented.

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(up(x1))=  1 + x1  
  POL(CHECK(x1))=  1 + x1  

resulting in one new DP problem. 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
           →DP Problem 26
             ↳FwdInst
             ...
               →DP Problem 28
                 ↳Dependency Graph
       →DP Problem 6
         ↳FwdInst


Dependency Pair:


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.


   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳Forward Instantiation Transformation


Dependency Pairs:

CHECK(no(x)) -> CHECK(x)
CHECK(sent(x)) -> CHECK(x)


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

CHECK(sent(x)) -> CHECK(x)
two new Dependency Pairs are created:

CHECK(sent(sent(x''))) -> CHECK(sent(x''))
CHECK(sent(no(x''))) -> CHECK(no(x''))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst
           →DP Problem 29
             ↳Forward Instantiation Transformation


Dependency Pairs:

CHECK(sent(no(x''))) -> CHECK(no(x''))
CHECK(sent(sent(x''))) -> CHECK(sent(x''))
CHECK(no(x)) -> CHECK(x)


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

CHECK(no(x)) -> CHECK(x)
three new Dependency Pairs are created:

CHECK(no(no(x''))) -> CHECK(no(x''))
CHECK(no(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))
CHECK(no(sent(no(x'''')))) -> CHECK(sent(no(x'''')))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst
           →DP Problem 29
             ↳FwdInst
             ...
               →DP Problem 30
                 ↳Forward Instantiation Transformation


Dependency Pairs:

CHECK(no(sent(no(x'''')))) -> CHECK(sent(no(x'''')))
CHECK(sent(sent(x''))) -> CHECK(sent(x''))
CHECK(no(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))
CHECK(no(no(x''))) -> CHECK(no(x''))
CHECK(sent(no(x''))) -> CHECK(no(x''))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

CHECK(sent(sent(x''))) -> CHECK(sent(x''))
two new Dependency Pairs are created:

CHECK(sent(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))
CHECK(sent(sent(no(x'''')))) -> CHECK(sent(no(x'''')))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst
           →DP Problem 29
             ↳FwdInst
             ...
               →DP Problem 31
                 ↳Forward Instantiation Transformation


Dependency Pairs:

CHECK(sent(sent(no(x'''')))) -> CHECK(sent(no(x'''')))
CHECK(sent(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))
CHECK(no(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))
CHECK(no(no(x''))) -> CHECK(no(x''))
CHECK(sent(no(x''))) -> CHECK(no(x''))
CHECK(no(sent(no(x'''')))) -> CHECK(sent(no(x'''')))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

CHECK(sent(no(x''))) -> CHECK(no(x''))
three new Dependency Pairs are created:

CHECK(sent(no(no(x'''')))) -> CHECK(no(no(x'''')))
CHECK(sent(no(sent(sent(x''''''))))) -> CHECK(no(sent(sent(x''''''))))
CHECK(sent(no(sent(no(x''''''))))) -> CHECK(no(sent(no(x''''''))))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst
           →DP Problem 29
             ↳FwdInst
             ...
               →DP Problem 32
                 ↳Forward Instantiation Transformation


Dependency Pairs:

CHECK(sent(no(sent(no(x''''''))))) -> CHECK(no(sent(no(x''''''))))
CHECK(sent(no(sent(sent(x''''''))))) -> CHECK(no(sent(sent(x''''''))))
CHECK(no(sent(no(x'''')))) -> CHECK(sent(no(x'''')))
CHECK(sent(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))
CHECK(no(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))
CHECK(no(no(x''))) -> CHECK(no(x''))
CHECK(sent(no(no(x'''')))) -> CHECK(no(no(x'''')))
CHECK(sent(sent(no(x'''')))) -> CHECK(sent(no(x'''')))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

CHECK(no(no(x''))) -> CHECK(no(x''))
three new Dependency Pairs are created:

CHECK(no(no(no(x'''')))) -> CHECK(no(no(x'''')))
CHECK(no(no(sent(sent(x''''''))))) -> CHECK(no(sent(sent(x''''''))))
CHECK(no(no(sent(no(x''''''))))) -> CHECK(no(sent(no(x''''''))))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst
           →DP Problem 29
             ↳FwdInst
             ...
               →DP Problem 33
                 ↳Forward Instantiation Transformation


Dependency Pairs:

CHECK(no(no(sent(no(x''''''))))) -> CHECK(no(sent(no(x''''''))))
CHECK(sent(no(sent(sent(x''''''))))) -> CHECK(no(sent(sent(x''''''))))
CHECK(sent(sent(no(x'''')))) -> CHECK(sent(no(x'''')))
CHECK(sent(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))
CHECK(no(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))
CHECK(no(no(sent(sent(x''''''))))) -> CHECK(no(sent(sent(x''''''))))
CHECK(no(no(no(x'''')))) -> CHECK(no(no(x'''')))
CHECK(sent(no(no(x'''')))) -> CHECK(no(no(x'''')))
CHECK(no(sent(no(x'''')))) -> CHECK(sent(no(x'''')))
CHECK(sent(no(sent(no(x''''''))))) -> CHECK(no(sent(no(x''''''))))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

CHECK(no(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))
two new Dependency Pairs are created:

CHECK(no(sent(sent(sent(x''''''))))) -> CHECK(sent(sent(sent(x''''''))))
CHECK(no(sent(sent(no(x''''''))))) -> CHECK(sent(sent(no(x''''''))))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst
           →DP Problem 29
             ↳FwdInst
             ...
               →DP Problem 34
                 ↳Forward Instantiation Transformation


Dependency Pairs:

CHECK(sent(no(sent(no(x''''''))))) -> CHECK(no(sent(no(x''''''))))
CHECK(no(sent(sent(no(x''''''))))) -> CHECK(sent(sent(no(x''''''))))
CHECK(sent(no(sent(sent(x''''''))))) -> CHECK(no(sent(sent(x''''''))))
CHECK(sent(sent(no(x'''')))) -> CHECK(sent(no(x'''')))
CHECK(sent(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))
CHECK(no(sent(sent(sent(x''''''))))) -> CHECK(sent(sent(sent(x''''''))))
CHECK(no(no(sent(sent(x''''''))))) -> CHECK(no(sent(sent(x''''''))))
CHECK(no(no(no(x'''')))) -> CHECK(no(no(x'''')))
CHECK(sent(no(no(x'''')))) -> CHECK(no(no(x'''')))
CHECK(no(sent(no(x'''')))) -> CHECK(sent(no(x'''')))
CHECK(no(no(sent(no(x''''''))))) -> CHECK(no(sent(no(x''''''))))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

CHECK(no(sent(no(x'''')))) -> CHECK(sent(no(x'''')))
three new Dependency Pairs are created:

CHECK(no(sent(no(no(x''''''))))) -> CHECK(sent(no(no(x''''''))))
CHECK(no(sent(no(sent(sent(x'''''''')))))) -> CHECK(sent(no(sent(sent(x'''''''')))))
CHECK(no(sent(no(sent(no(x'''''''')))))) -> CHECK(sent(no(sent(no(x'''''''')))))

The transformation is resulting in one new DP problem: 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst
           →DP Problem 29
             ↳FwdInst
             ...
               →DP Problem 35
                 ↳Polynomial Ordering


Dependency Pairs:

CHECK(no(sent(no(sent(no(x'''''''')))))) -> CHECK(sent(no(sent(no(x'''''''')))))
CHECK(no(sent(no(sent(sent(x'''''''')))))) -> CHECK(sent(no(sent(sent(x'''''''')))))
CHECK(no(no(sent(no(x''''''))))) -> CHECK(no(sent(no(x''''''))))
CHECK(no(sent(sent(no(x''''''))))) -> CHECK(sent(sent(no(x''''''))))
CHECK(sent(no(sent(sent(x''''''))))) -> CHECK(no(sent(sent(x''''''))))
CHECK(sent(sent(no(x'''')))) -> CHECK(sent(no(x'''')))
CHECK(sent(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))
CHECK(no(sent(sent(sent(x''''''))))) -> CHECK(sent(sent(sent(x''''''))))
CHECK(no(no(sent(sent(x''''''))))) -> CHECK(no(sent(sent(x''''''))))
CHECK(no(no(no(x'''')))) -> CHECK(no(no(x'''')))
CHECK(sent(no(no(x'''')))) -> CHECK(no(no(x'''')))
CHECK(no(sent(no(no(x''''''))))) -> CHECK(sent(no(no(x''''''))))
CHECK(sent(no(sent(no(x''''''))))) -> CHECK(no(sent(no(x''''''))))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




The following dependency pairs can be strictly oriented:

CHECK(no(sent(no(sent(no(x'''''''')))))) -> CHECK(sent(no(sent(no(x'''''''')))))
CHECK(no(sent(no(sent(sent(x'''''''')))))) -> CHECK(sent(no(sent(sent(x'''''''')))))
CHECK(no(no(sent(no(x''''''))))) -> CHECK(no(sent(no(x''''''))))
CHECK(no(sent(sent(no(x''''''))))) -> CHECK(sent(sent(no(x''''''))))
CHECK(no(sent(sent(sent(x''''''))))) -> CHECK(sent(sent(sent(x''''''))))
CHECK(no(no(sent(sent(x''''''))))) -> CHECK(no(sent(sent(x''''''))))
CHECK(no(no(no(x'''')))) -> CHECK(no(no(x'''')))
CHECK(no(sent(no(no(x''''''))))) -> CHECK(sent(no(no(x''''''))))


Additionally, the following usable rules for innermost can be oriented:

sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(no(x1))=  1 + x1  
  POL(up(x1))=  0  
  POL(CHECK(x1))=  1 + x1  
  POL(sent(x1))=  x1  

resulting in one new DP problem. 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst
           →DP Problem 29
             ↳FwdInst
             ...
               →DP Problem 36
                 ↳Dependency Graph


Dependency Pairs:

CHECK(sent(no(sent(sent(x''''''))))) -> CHECK(no(sent(sent(x''''''))))
CHECK(sent(sent(no(x'''')))) -> CHECK(sent(no(x'''')))
CHECK(sent(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))
CHECK(sent(no(no(x'''')))) -> CHECK(no(no(x'''')))
CHECK(sent(no(sent(no(x''''''))))) -> CHECK(no(sent(no(x''''''))))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




Using the Dependency Graph the DP problem was split into 1 DP problems.


   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst
           →DP Problem 29
             ↳FwdInst
             ...
               →DP Problem 37
                 ↳Polynomial Ordering


Dependency Pair:

CHECK(sent(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




The following dependency pair can be strictly oriented:

CHECK(sent(sent(sent(x'''')))) -> CHECK(sent(sent(x'''')))


Additionally, the following usable rule for innermost can be oriented:

sent(up(x)) -> up(sent(x))


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(up(x1))=  0  
  POL(CHECK(x1))=  1 + x1  
  POL(sent(x1))=  1 + x1  

resulting in one new DP problem. 



   R
     ↳DPs
       →DP Problem 1
         ↳FwdInst
       →DP Problem 2
         ↳FwdInst
       →DP Problem 3
         ↳FwdInst
       →DP Problem 4
         ↳FwdInst
       →DP Problem 5
         ↳FwdInst
       →DP Problem 6
         ↳FwdInst
           →DP Problem 29
             ↳FwdInst
             ...
               →DP Problem 38
                 ↳Dependency Graph


Dependency Pair:


Rules:


rec(rec(x)) -> sent(rec(x))
rec(sent(x)) -> sent(rec(x))
rec(no(x)) -> sent(rec(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
sent(up(x)) -> up(sent(x))
no(up(x)) -> up(no(x))
top(rec(up(x))) -> top(check(rec(x)))
top(sent(up(x))) -> top(check(rec(x)))
top(no(up(x))) -> top(check(rec(x)))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
check(rec(x)) -> rec(check(x))
check(no(x)) -> no(check(x))
check(no(x)) -> no(x)


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.

Innermost Termination of R successfully shown.
Duration:
0:02 minutes