zbMATH — the first resource for mathematics

Clearing restarting automata. (English) Zbl 1214.68190
Summary: 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.

68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems
Full Text: DOI