Abstract
Restarting automata were introduced as a model for analysis by reduction, which is a linguistically motivated method for checking correctness of a sentence. We propose a new restricted version of restarting automata called clearing restarting automata with a very simple definition but simultaneously with interesting properties with respect to their possible applications.
The new model can be learned very efficiently from positive examples and its stronger version can be used to learn effectively a large class of languages. We relate the class of languages recognized by clearing restarting automata to the Chomsky hierarchy.