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)

Termination of R to be shown. 



   TRS
     ↳Removing Redundant Rules



Removing the following rules from R which fullfill a polynomial ordering:

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

where the Polynomial interpretation:
  POL(top(x1))=  1 + x1  
  POL(rec(x1))=  x1  
  POL(no(x1))=  1 + x1  
  POL(bot)=  0  
  POL(up(x1))=  x1  
  POL(check(x1))=  x1  
  POL(sent(x1))=  x1  
was used.

Not all Rules of R can be deleted, so we still have to regard a part of R. 


   TRS
     ↳RRRPolo
       →TRS2
         ↳Removing Redundant Rules



Removing the following rules from R which fullfill a polynomial ordering:

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

where the Polynomial interpretation:
  POL(top(x1))=  1 + x1  
  POL(rec(x1))=  1 + x1  
  POL(bot)=  0  
  POL(no(x1))=  x1  
  POL(up(x1))=  1 + x1  
  POL(check(x1))=  x1  
  POL(sent(x1))=  x1  
was used.

Not all Rules of R can be deleted, so we still have to regard a part of R. 


   TRS
     ↳RRRPolo
       →TRS2
         ↳RRRPolo
           →TRS3
             ↳Removing Redundant Rules



Removing the following rules from R which fullfill a polynomial ordering:

check(no(x)) -> no(check(x))
check(no(x)) -> no(x)

where the Polynomial interpretation:
  POL(top(x1))=  x1  
  POL(rec(x1))=  x1  
  POL(bot)=  0  
  POL(no(x1))=  1 + x1  
  POL(up(x1))=  x1  
  POL(check(x1))=  2·x1  
  POL(sent(x1))=  2·x1  
was used.

Not all Rules of R can be deleted, so we still have to regard a part of R. 


   TRS
     ↳RRRPolo
       →TRS2
         ↳RRRPolo
           →TRS3
             ↳RRRPolo
             ...
               →TRS4
                 ↳Removing Redundant Rules



Removing the following rules from R which fullfill a polynomial ordering:

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

where the Polynomial interpretation:
  POL(top(x1))=  1 + x1  
  POL(rec(x1))=  1 + x1  
  POL(bot)=  0  
  POL(no(x1))=  2·x1  
  POL(up(x1))=  1 + x1  
  POL(check(x1))=  x1  
  POL(sent(x1))=  x1  
was used.

Not all Rules of R can be deleted, so we still have to regard a part of R. 


   TRS
     ↳RRRPolo
       →TRS2
         ↳RRRPolo
           →TRS3
             ↳RRRPolo
             ...
               →TRS5
                 ↳Dependency Pair Analysis



R contains the following Dependency Pairs:

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

Furthermore, R contains four SCCs. 


   TRS
     ↳RRRPolo
       →TRS2
         ↳RRRPolo
           →TRS3
             ↳RRRPolo
             ...
               →DP Problem 1
                 ↳Modular Removal of Rules


Dependency Pair:

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


Rules:


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





We have the following set of usable rules: none
To remove rules and DPs from this DP problem we used the following monotonic and CE-compatible order: Polynomial ordering.
Polynomial interpretation:
  POL(up(x1))=  x1  
  POL(SENT(x1))=  x1  

We have the following set D of usable symbols: {SENT}
The following Dependency Pairs can be deleted as they contain symbols in their lhs which do not occur in D:

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

No Rules can be deleted.

After the removal, there are no SCCs in the dependency graph which results in no DP problems which have to be solved. 



   TRS
     ↳RRRPolo
       →TRS2
         ↳RRRPolo
           →TRS3
             ↳RRRPolo
             ...
               →DP Problem 2
                 ↳Modular Removal of Rules


Dependency Pairs:

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


Rules:


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





We have the following set of usable rules: none
To remove rules and DPs from this DP problem we used the following monotonic and CE-compatible order: Polynomial ordering.
Polynomial interpretation:
  POL(up(x1))=  x1  
  POL(REC(x1))=  x1  
  POL(sent(x1))=  x1  

We have the following set D of usable symbols: {REC}
The following Dependency Pairs can be deleted as they contain symbols in their lhs which do not occur in D:

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

No Rules can be deleted.

After the removal, there are no SCCs in the dependency graph which results in no DP problems which have to be solved. 



   TRS
     ↳RRRPolo
       →TRS2
         ↳RRRPolo
           →TRS3
             ↳RRRPolo
             ...
               →DP Problem 3
                 ↳Modular Removal of Rules


Dependency Pairs:

CHECK(sent(x)) -> CHECK(x)
CHECK(up(x)) -> CHECK(x)
CHECK(rec(x)) -> CHECK(x)


Rules:


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





We have the following set of usable rules: none
To remove rules and DPs from this DP problem we used the following monotonic and CE-compatible order: Polynomial ordering.
Polynomial interpretation:
  POL(rec(x1))=  x1  
  POL(up(x1))=  x1  
  POL(CHECK(x1))=  x1  
  POL(sent(x1))=  x1  

We have the following set D of usable symbols: {CHECK}
The following Dependency Pairs can be deleted as they contain symbols in their lhs which do not occur in D:

CHECK(sent(x)) -> CHECK(x)
CHECK(up(x)) -> CHECK(x)
CHECK(rec(x)) -> CHECK(x)

No Rules can be deleted.

After the removal, there are no SCCs in the dependency graph which results in no DP problems which have to be solved. 



   TRS
     ↳RRRPolo
       →TRS2
         ↳RRRPolo
           →TRS3
             ↳RRRPolo
             ...
               →DP Problem 4
                 ↳Modular Removal of Rules


Dependency Pair:

TOP(sent(up(x))) -> TOP(check(rec(x)))


Rules:


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





We have the following set of usable rules:

check(rec(x)) -> rec(check(x))
check(up(x)) -> up(check(x))
check(sent(x)) -> sent(check(x))
rec(bot) -> up(sent(bot))
rec(up(x)) -> up(rec(x))
rec(sent(x)) -> sent(rec(x))
sent(up(x)) -> up(sent(x))
To remove rules and DPs from this DP problem we used the following monotonic and CE-compatible order: Polynomial ordering.
Polynomial interpretation:
  POL(rec(x1))=  x1  
  POL(bot)=  0  
  POL(up(x1))=  x1  
  POL(check(x1))=  x1  
  POL(TOP(x1))=  1 + x1  
  POL(sent(x1))=  x1  

We have the following set D of usable symbols: {bot, rec, up, check, TOP, sent}
No Dependency Pairs can be deleted.
1 non usable rules have been deleted.

The result of this processor delivers one new DP problem.



   TRS
     ↳RRRPolo
       →TRS2
         ↳RRRPolo
           →TRS3
             ↳RRRPolo
             ...
               →DP Problem 5
                 ↳Narrowing Transformation


Dependency Pair:

TOP(sent(up(x))) -> TOP(check(rec(x)))


Rules:


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





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

TOP(sent(up(x))) -> TOP(check(rec(x)))
four new Dependency Pairs are created:

TOP(sent(up(x''))) -> TOP(rec(check(x'')))
TOP(sent(up(bot))) -> TOP(check(up(sent(bot))))
TOP(sent(up(up(x'')))) -> TOP(check(up(rec(x''))))
TOP(sent(up(sent(x'')))) -> TOP(check(sent(rec(x''))))

The transformation is resulting in one new DP problem: 



   TRS
     ↳RRRPolo
       →TRS2
         ↳RRRPolo
           →TRS3
             ↳RRRPolo
             ...
               →DP Problem 6
                 ↳Negative Polynomial Order


Dependency Pairs:

TOP(sent(up(sent(x'')))) -> TOP(check(sent(rec(x''))))
TOP(sent(up(up(x'')))) -> TOP(check(up(rec(x''))))
TOP(sent(up(x''))) -> TOP(rec(check(x'')))


Rules:


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





The following Dependency Pair can be strictly oriented using the given order.

TOP(sent(up(up(x'')))) -> TOP(check(up(rec(x''))))


Moreover, the following usable rules (regarding the implicit AFS) are oriented.

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


Used ordering:
Polynomial Order with Interpretation:

POL( TOP(x1) ) = x1

POL( sent(x1) ) = 1

POL( check(x1) ) = x1

POL( up(x1) ) = 0

POL( rec(x1) ) = 1


This results in one new DP problem. 


   TRS
     ↳RRRPolo
       →TRS2
         ↳RRRPolo
           →TRS3
             ↳RRRPolo
             ...
               →DP Problem 7
                 ↳Semantic Labelling


Dependency Pairs:

TOP(sent(up(sent(x'')))) -> TOP(check(sent(rec(x''))))
TOP(sent(up(x''))) -> TOP(rec(check(x'')))


Rules:


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





Using Semantic Labelling, the DP problem could be transformed. The following model was found:
TOP(x0)=  0
sent(x0)=  x0
up(x0)=  x0
rec(x0)=  x0
check(x0)=  1
bot=  0

From the dependency graph we obtain 1 (labeled) SCCs which each result in correspondingDP problem.


   TRS
     ↳RRRPolo
       →TRS2
         ↳RRRPolo
           →TRS3
             ↳RRRPolo
             ...
               →DP Problem 8
                 ↳Modular Removal of Rules


Dependency Pairs:

TOP1(sent1(up1(x''))) -> TOP1(rec1(check1(x'')))
TOP1(sent1(up1(sent1(x'')))) -> TOP1(check1(sent1(rec1(x''))))


Rules:


check0(rec0(x)) -> rec1(check0(x))
check0(up0(x)) -> up1(check0(x))
check0(sent0(x)) -> sent1(check0(x))
rec0(bot) -> up0(sent0(bot))
rec0(up0(x)) -> up0(rec0(x))
rec0(sent0(x)) -> sent0(rec0(x))
rec1(up1(x)) -> up1(rec1(x))
rec1(sent1(x)) -> sent1(rec1(x))
check1(rec1(x)) -> rec1(check1(x))
check1(up1(x)) -> up1(check1(x))
check1(sent1(x)) -> sent1(check1(x))
sent0(up0(x)) -> up0(sent0(x))
sent1(up1(x)) -> up1(sent1(x))





We have the following set of usable rules:

rec1(up1(x)) -> up1(rec1(x))
rec1(sent1(x)) -> sent1(rec1(x))
check1(rec1(x)) -> rec1(check1(x))
check1(up1(x)) -> up1(check1(x))
check1(sent1(x)) -> sent1(check1(x))
sent1(up1(x)) -> up1(sent1(x))
To remove rules and DPs from this DP problem we used the following monotonic and CE-compatible order: Polynomial ordering.
Polynomial interpretation:
  POL(rec_1(x1))=  x1  
  POL(up_1(x1))=  x1  
  POL(sent_1(x1))=  x1  
  POL(check_1(x1))=  x1  
  POL(TOP_1(x1))=  1 + x1  

We have the following set D of usable symbols: {rec1, up1, sent1, check1, TOP1}
No Dependency Pairs can be deleted.
7 non usable rules have been deleted.

The result of this processor delivers one new DP problem.



   TRS
     ↳RRRPolo
       →TRS2
         ↳RRRPolo
           →TRS3
             ↳RRRPolo
             ...
               →DP Problem 9
                 ↳Modular Removal of Rules


Dependency Pairs:

TOP1(sent1(up1(sent1(x'')))) -> TOP1(check1(sent1(rec1(x''))))
TOP1(sent1(up1(x''))) -> TOP1(rec1(check1(x'')))


Rules:


rec1(up1(x)) -> up1(rec1(x))
rec1(sent1(x)) -> sent1(rec1(x))
sent1(up1(x)) -> up1(sent1(x))
check1(rec1(x)) -> rec1(check1(x))
check1(up1(x)) -> up1(check1(x))
check1(sent1(x)) -> sent1(check1(x))





We have the following set of usable rules:

check1(rec1(x)) -> rec1(check1(x))
check1(up1(x)) -> up1(check1(x))
check1(sent1(x)) -> sent1(check1(x))
rec1(up1(x)) -> up1(rec1(x))
rec1(sent1(x)) -> sent1(rec1(x))
sent1(up1(x)) -> up1(sent1(x))
To remove rules and DPs from this DP problem we used the following monotonic and CE-compatible order: Polynomial ordering.
Polynomial interpretation:
  POL(rec_1(x1))=  x1  
  POL(up_1(x1))=  1 + x1  
  POL(sent_1(x1))=  x1  
  POL(check_1(x1))=  x1  
  POL(TOP_1(x1))=  1 + x1  

We have the following set D of usable symbols: {rec1, up1, sent1, check1, TOP1}
The following Dependency Pairs can be deleted as the lhs is strictly greater than the corresponding rhs:

TOP1(sent1(up1(sent1(x'')))) -> TOP1(check1(sent1(rec1(x''))))
TOP1(sent1(up1(x''))) -> TOP1(rec1(check1(x'')))

No Rules can be deleted.

After the removal, there are no SCCs in the dependency graph which results in no DP problems which have to be solved.


Termination of R successfully shown.
Duration:
0:17 minutes