Learning String Patterns and Tree Patterns from Examples
Abstract
A (string) pattern is a non-null string over an alphabet and a set of variables. A pattern language is the set of all strings obtained by substituting non-null constant strings for variables in a pattern. We investigate learning pattern languages in three new directions. First we prove that to decide whether there is a string pattern consistent with given positive and negative samples is NP-hard. Thus it is not polynomial-time learnable under Valiant's probabilistic learning model unless RP = NP. Then we discuss extensions of examples and string patterns: incomplete examples and tree patterns. We prove that to decide whether there is a common k-variable string pattern for given incomplete positive examples is NP-complete for any fixed integer k ≳ 2. We give polynomial-time algorithms to find common k-variable tree patterns for non-associative, non-commutative constant trees for any fixed integer k ≳ 1. We also prove that to decide whether there is a common k-variable tree pattern for associative, commutative constant trees is NP-complete for any fixed integer k ≳2.
Cite
Text
Ko et al. "Learning String Patterns and Tree Patterns from Examples." International Conference on Machine Learning, 1990. doi:10.1016/B978-1-55860-141-3.50049-3Markdown
[Ko et al. "Learning String Patterns and Tree Patterns from Examples." International Conference on Machine Learning, 1990.](https://mlanthology.org/icml/1990/ko1990icml-learning/) doi:10.1016/B978-1-55860-141-3.50049-3BibTeX
@inproceedings{ko1990icml-learning,
title = {{Learning String Patterns and Tree Patterns from Examples}},
author = {Ko, Ker-I and Marron, Assaf and Tzeng, Wen-Guey},
booktitle = {International Conference on Machine Learning},
year = {1990},
pages = {384-391},
doi = {10.1016/B978-1-55860-141-3.50049-3},
url = {https://mlanthology.org/icml/1990/ko1990icml-learning/}
}