DECISION-PROBLEMS FOR PATTERNS

Authors
JIANG T SALOMAA A SALOMAA K YU S
Citation
T. Jiang et al., DECISION-PROBLEMS FOR PATTERNS, Journal of computer and system sciences, 50(1), 1995, pp. 53-63
Citations number
16
Categorie Soggetti
System Science","Computer Science Hardware & Architecture","Computer Science Theory & Methods
Journal title
Journal of computer and system sciences → ACNP
ISSN journal
00220000
Volume
50
Issue
1
Year of publication
1995
Pages
53 - 63
Database
ISI
SICI code
0022-0000(1995)50:1<53:DFP>2.0.ZU;2-T
Abstract
We settle an open problem, the inclusion problem for pattern languages . This is the first known case where inclusion is undecidable for gene rative devices having a trivially decidable equivalence problem. The s tudy of patterns goes back to the seminal work of Thue and is importan t also, for instance, in recent work concerning inductive inference an d learning. Our results concern both erasing and nonerasing patterns. (C) 1995 Academic Press, Inc.