On Leaf Permutative Theories and Occurrence Permutation Groups
Abstract Leaf permutative theories contain variable-permuting equations, so that rewriting a term may lead to an exponential number of terms which are only permutations of it. In [1] Avenhaus and Plaisted propose to represent such sets by stratified terms, and to deduce directly with these. Our aim is to use computational group theory to analyse the complexity of the corresponding problems, and hopefully devise better algorithms than [1]. In order to express stratified sets as orbits, we adopt a representation of terms based on occurrences , which can conveniently be permuted. An algorithm solving a basic equivalence problem is presented.