Clearing restarting automata. (English) Zbl 1214.68190

Černo, Peter; Mráz, František

Fundam. Inform. 104, No. 1-2, 17-54 (2010).

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.

MSC:

68Q45	Formal languages and automata
68Q42	Grammars and rewriting systems

Keywords:

analysis by reduction; clearing restarting automata; formal languages; grammatical inference