abstract
- We survey two existing algorithms for the inference of finite-state tree automata from membership queries and a finite positive sample or equivalence queries, and we suggest a correction for one of them which we deem necessary in order to ensure its termination. We present two algorithms for the same two settings when the underlying description is not a deterministic but a residual canonical finite-state automaton. To this end, we adapt all necessary notions to the residual tree case. From our completed perspective, we discuss the terms on which those four algorithms can be considered to be of polynomial complexity, and also where there may be hidden exponentiality.