In the research area of ILP (Inductive Logic Programming), the generation of new intermediate predicates is known to be a hard problem, which requires very large search spaces. In this paper we define the class of regular logic programs, having similar properties to the class of regular languages, and show an efficient algorithm which infers them using membership and equivalence queries. In particular, without requiring examples of intermediate predicates it can invent, such predicates dynamically and derive their definitions. The algorithm is based on the use of program schemata-ordered lists of the arguments appearing in the program clauses representing the target regular tree relation. Using program schemata we can extend Angluin's algorithm for inference of regular languages so that we can apply it to the inference of regular logic programs. The algorithm is realized with a routine for revising predicate decision trees and a new implementation of contradiction backtracking. The total running time of our algorithm is bounded to polynomial in the number of clauses m of the program presenting the target relation, and the maximum size w of user-provided counter examples.