کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426479 686082 2014 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Patterns with bounded treewidth
ترجمه فارسی عنوان
الگوها با عرض درختی محدود
کلمات کلیدی
زبانهای الگو، مشکل عضویت درخت عرض اصطلاحات منظم گسترش یافته، مطابقت الگوی پارامتریک شده
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

A pattern is a string consisting of variables and terminal symbols, and its language is the set of all words that can be obtained by substituting arbitrary words for the variables. The membership problem for pattern languages, i.e., deciding on whether or not a given word is in the pattern language of a given pattern is NP-complete. We show that any parameter of patterns that is an upper bound for the treewidth of appropriate encodings of patterns as relational structures, if restricted, allows the membership problem for pattern languages to be solved in polynomial time. Furthermore, we identify new such parameters.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 239, December 2014, Pages 87–99
نویسندگان
, ,