BEST_CASE(Omega(n^1),?)

Solution:
---------

  "Cons" :: ["__ANY_TYPE__"(0) x "list"(1)] -(1)-> "list"(1)
  "Cons" :: ["__ANY_TYPE__"(0) x "list"(0)] -(0)-> "list"(0)
  "Nil" :: [] -(0)-> "list"(1)
  "Nil" :: [] -(0)-> "list"(0)
  "Pair" :: ["__ANY_TYPE__"(0) x "__ANY_TYPE__"(0)] -(0)-> "pair"(0)
  "foldr#3" :: ["list"(0) x "list"(0) x "list"(1)] -(1)-> "list"(0)
  "main" :: ["list"(1) x "list"(0)] -(2)-> "list"(0)
  "product_ms_ns" :: ["list"(0)] -(0)-> "list"(0)
  "product_ms_ns_2" :: ["__ANY_TYPE__"(0)] -(0)-> "list"(0)


Cost Free Signatures:
---------------------




Base Constructors:
------------------
  "\"Cons\"_list" :: ["__ANY_TYPE__"(0) x "list"(1)] -(1)-> "list"(1)
  "\"Nil\"_list" :: [] -(0)-> "list"(1)
  "\"Pair\"_pair" :: ["__ANY_TYPE__"(0) x "__ANY_TYPE__"(8)] -(1)-> "pair"(1)
  "\"product_ms_ns\"_list" :: ["list"(0)] -(1)-> "list"(1)
  "\"product_ms_ns_2\"_list" :: ["__ANY_TYPE__"(0)] -(1)-> "list"(1)



Parsed Typed Term Rewrite System:
---------------------------------

(STRATEGY
 INNERMOST)
(VAR
 "v8" "v12" "v40" "v14" "v56" "v6" "v3" "v2" "v1")
(DATATYPES
   "list" = µX.< "Nil", "product_ms_ns_2"("__ANY_TYPE__"), "Cons"("__ANY_TYPE__", X), "product_ms_ns"(X) >
   "pair" = < "Pair"("__ANY_TYPE__", "__ANY_TYPE__") >)
(SIGNATURES
   "foldr#3" :: ["list" x "list" x "list"] --> "list"
   "main" :: ["list" x "list"] --> "list")
(RULES
 "foldr#3"("v8","v12","Nil"()) -> "v12"
 "foldr#3"("product_ms_ns_2"("v40"),"v14","Cons"("v56","v6")) -> "Cons"("Pair"("v40","v56"),"foldr#3"("product_ms_ns_2"("v40"),"v14","v6"))
 "foldr#3"("product_ms_ns"("v3"),"Nil"(),"Cons"("v2","v1")) -> "foldr#3"("product_ms_ns_2"("v2"),"foldr#3"("product_ms_ns"("v3"),"Nil"(),"v1"),"v3")
 "main"("v2","v1") -> "foldr#3"("product_ms_ns"("v1"),"Nil"(),"v2"))


BEST_CASE(Omega(n^1),?)