Learning analysis by reduction from positive data

Abstract

Analysis by reduction is a linguistically motivated method for checking correctness of a sentence. It can be modelled by restarting automata.

In this paper we propose a method for learning of restarting automata which are strictly locally testable SLT-R-automata. The method is based on the concept of identification in the limit from positive examples only.

Also we characterize the class of languages accepted by SLT-R-automata with respect to the Chomsky hierarchy.

Keywords

• Learning
• analysis
• reduction
• positive
• data