Consistency Problem for One-Variable Patterns is Polynomially Decidable
Hiroshi Sakamoto, 坂本, 比呂志 · Kyushu University Institutional Repository (QIR) (Kyushu University) · 1998
The present paper deals with the decision problem for the class of one-variable patterns, called the consistency problem. Although this problem is obviously in NP, its tractability is unknown. We prove the consistency problem to be decidable in P. 1 Introduction A pattern is a string from a constant alphabet 6 and a variable alphabet X. The language generated by a pattern ß is the set of all constant strings obtained by substituting nonempty strings for the variables of ß [1]. A pattern ß is said to be a k-variable pattern if at most k different x i 2 X appears in ß. The language generated by a pattern ß is denoted by L(ß). A string w is called a positive example of a pattern ß if w 2 L(ß). In particular, a pattern ß is called descriptive for a finite set S of strings if S ` L(ß) and for any other pattern ß 0 such that S ` L(ß 0 ), L(ß 0 ) 6` L(ß). The problem of finding a descriptive pattern from a given set is referred as to the pattern inference from positive data. The pr...