Abstract | ||
---|---|---|
A pattern is a string of constant symbols and variable symbols. The language of a pattern p is the set of all strings obtained by substituting any non-empty constant string for each variable symbol in p. A regular pattern has at most one occurrence of each variable symbol. In this paper, we consider polynomial time inference from positive data for the class of extended regular pattern languages which are sets of all strings obtained by substituting any (possibly empty) constant string, instead of non-empty string. Our inference machine uses MINL calculation which finds a minimal language containing a given finite set of strings. The relation between MINL calculation for the class of extended regular pattern languages and the longest common subsequence problem is also discussed. |
Year | DOI | Venue |
---|---|---|
1982 | 10.1007/3-540-11980-9_19 | Proceedings of RIMS Symposium on Software Science and Engineering |
Keywords | Field | DocType |
extended regular pattern languages,polynomial time inference,pattern language,polynomial time,longest common subsequence | Generalized star height problem,Discrete mathematics,Combinatorics,Finite set,Longest common subsequence problem,Inference,Symbol,Time complexity,Mathematics | Conference |
ISBN | Citations | PageRank |
3-540-11980-9 | 103 | 11.34 |
References | Authors | |
4 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
takeshi shinohara | 1 | 103 | 12.69 |
takeshi | 2 | 103 | 11.34 |