6533b7d7fe1ef96bd126826d

RESEARCH PRODUCT

Learning a class of regular expressions via restricted subset queries

Efim Kinber

subject

Loop (topology)CombinatoricsDiscrete mathematicsClass (set theory)Regular languageStructure (category theory)Regular expressionSubclassExpression (mathematics)MathematicsTarget expression

description

A wide class of regular expressions non-representable as unions of “smaller” expressions is shown to be polynomial-time learnable via restricted subset queries from arbitrary representative examples “reflecting” the loop structure and a way the input example is obtained from the unknown expression. The corresponding subclass of regular expressions of loop depth at most 1 is shown to be learnable from representative examples via membership queries. A wide class of expressions with loops A+ of arbitrary loop depth is shown to be learnable via restricted subset queries from arbitrary examples.

yearjournalcountryeditionlanguage
1992-01-01
https://doi.org/10.1007/3-540-56004-1_16