Lecture Notes in Computer Science, 2002, Volume 2484/2002, 754-758, DOI: 10.1007/3-540-45790-9_3

Inferring Subclasses of Regular Languages Faster Using RPNI and Forbidden Configurations

Antonio Cano, José Ruiz and Pedro García

View Related Documents

Abstract

Many varieties of regular languages have characterizations in terms of forbidden-patterns of their accepting finite automata. The use of patterns while inferring languages belonging to those families through the RPNI-Lang algorithm help to avoid overgeneralization in the same way as negative samples do. The aim of this paper is to describe and prove the convergence of a modification of the RPNI-Lang algorithm that we call FCRPNI. Preliminary experiments done seem to show that the convergence when we use FCRPNI for some subfamilies of regular languages is achieved faster than when we use just the RPNI algorithm.

Keywords  Variety of languages - grammatical inference - forbidden configurations

Work partially supported by the Spanish CICYT under contract TIC2000-1153

Fulltext Preview

Image of the first page of the fulltext document