(STRATEGY
    INNERMOST)

(VAR
    x2 x1 x4 x8 x6 x16)
(RULES
    cond_prefix_s1_s2_2(True(),x2,x1) -> prefix#2(x2,x1)
    cond_prefix_s1_s2_2(False(),x2,x1) -> False()
    prefix#2(Nil(),x2) -> True()
    prefix#2(Cons(x4,x2),Nil()) -> False()
    prefix#2(Cons(x8,x6),Cons(x4,x2)) -> cond_prefix_s1_s2_2(eq#2(x8,x4),x6,x2)
    eq#2(0(),0()) -> True()
    eq#2(0(),S(x16)) -> False()
    eq#2(S(x16),0()) -> False()
    eq#2(S(x4),S(x2)) -> eq#2(x4,x2)
    main(x2,x1) -> prefix#2(x2,x1))