Affiliations: Department of Computer Science, Charles University, Faculty of Mathematics and Physics, Malostranské nám. 25, 118 00 PRAHA 1, Czech Republic. [email protected] | Department of Computer Science, Charles University, Faculty of Mathematics and Physics, Malostranské nám. 25, 118 00 PRAHA 1, Czech Republic. [email protected]
Note: [] Address for correspondence: Department of Computer Science, Charles University, Faculty of Mathematics and Physics, Malostranské nám. 25, 118 00 PRAHA 1, Czech Republic
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.
