Inductive inference on pattern languages and regular pattern languages

Date

1983

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

A pattern is a concatenation of constants and variables. The language of a pattern is the set of strings obtained by substituting nonempty constant strings for the variables in the pattern. The pattern finding problem is to find, for a given set of strings, a minimal pattern language which contains this set. The one-variable pattern-finding problem was first studied by Angluin. We apply a well-known equation in number theory to improve the upper bound of her algorithm. We also extend Angluin's algorithm to the two-variable case. We show that the problem of finding the intersection of pattern automata, the critical part of the algorithm, is NP-complete. We present a modification of the algorithm and discuss its plausibility. We extend the patterns to regular patterns and investigate the relationship among pattern languages, regular languages, context-free languages, and regular pattern languages. The closure properties for pattern languages and regular pattern languages are also discussed. The inductive inference problem for regular pattern languages is considered. We show that regular pattern languages are not inferrable from positive data.

Description

Keywords

Formal languages, Machine theory

Citation