Learning of context-sensitive languages described by augmented regular expressions

Abstract

Recently augmented regular expressions (AREs) have been proposed as a formalism to describe and recognize a non-trivial class of context-sensitive languages (CSLs). AREs augment the expressive power of regular expressions (REs) by including a set of constraints, that involve the number of instances in a string of the operands of the star operations of an RE. Although it has been demonstrated that not all the CSLs can be described by AREs, the class of representable objects includes planar shapes with symmetries, which is important for pattern recognition tasks. In this paper a general method to infer AREs from string examples is presented. The method consists of a regular grammatical inference step, aimed at obtaining a regular superset of the target language, followed by a constraint induction process, which reduces the extension of the inferred language attempting to discover the maximal number of context relations. Hence, this approach avoids the difficulty of learning context-sensitive grammars.