3.05/1.94 MAYBE 3.14/1.95 We consider the system theBenchmark. 3.14/1.95 3.14/1.95 Alphabet: 3.14/1.95 3.14/1.95 0 : [] --> nat 3.14/1.95 app : [list * list] --> list 3.14/1.95 cons : [nat * list] --> list 3.14/1.95 head : [list] --> nat 3.14/1.95 hrepeat : [nat * list -> list * list] --> list 3.14/1.95 hshuffle : [list] --> list 3.14/1.95 nil : [] --> list 3.14/1.95 reverse : [list] --> list 3.14/1.95 s : [nat] --> nat 3.14/1.95 shuffle : [list] --> list 3.14/1.95 tail : [list] --> list 3.14/1.95 uhalf : [nat] --> nat 3.14/1.95 3.14/1.95 Rules: 3.14/1.95 3.14/1.95 app(nil, x) => x 3.14/1.95 app(cons(x, y), z) => cons(x, app(y, z)) 3.14/1.95 reverse(nil) => nil 3.14/1.95 reverse(cons(x, y)) => app(reverse(y), cons(x, nil)) 3.14/1.95 shuffle(nil) => nil 3.14/1.95 shuffle(cons(x, y)) => cons(x, shuffle(reverse(y))) 3.14/1.95 uhalf(0) => 0 3.14/1.95 uhalf(s(0)) => s(0) 3.14/1.95 uhalf(s(s(x))) => s(uhalf(x)) 3.14/1.95 hrepeat(0, f, x) => x 3.14/1.95 hrepeat(s(x), f, y) => hrepeat(uhalf(x), f, f y) 3.14/1.95 tail(cons(x, y)) => y 3.14/1.95 head(cons(x, y)) => x 3.14/1.95 hshuffle(x) => hrepeat(head(x), /\y.shuffle(y), tail(x)) 3.14/1.95 3.14/1.95 This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). 3.14/1.95 3.14/1.95 EOF