کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430552 | 688030 | 2015 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
String shuffle: Circuits and graphs
ترجمه فارسی عنوان
زدن رشته: مدار و نمودار
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
زدن رشته، پیچیدگی مدار، مرزهای پایین، مونگ
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that shuffle, the problem of determining whether a string w can be composed from an order preserving shuffle of strings x and y , is not in AC0AC0, but it is in AC1AC1. The fact that shuffle is not in AC0AC0 is shown by a reduction of parity to shuffle and invoking the seminal result of Furst et al., while the fact that it is in AC1AC1 is implicit in the results of Mansfield. Together, the two results provide a lower and upper bound on the complexity of this combinatorial problem. We also explore an interesting relationship between graphs and the shuffle problem, namely what types of graphs can be represented with strings exhibiting the anti-Monge condition.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 31, March 2015, Pages 120–128
Journal: Journal of Discrete Algorithms - Volume 31, March 2015, Pages 120–128
نویسندگان
Neerja Mhaskar, Michael Soltys,