کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9656889 | 686056 | 2005 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages](/preview/png/9656889.png)
چکیده انگلیسی
The growing context-sensitive languages have been classified through the shrinking two-pushdown automaton, the deterministic version of which characterizes the class of generalized Church-Rosser languages [Inform. Comput. 141 (1998) 1]. Exploiting this characterization we prove that the latter class coincides with the class of Church-Rosser languages that was introduced by McNaughton et al. [J. ACM 35 (1988) 324]. Based on this result several open problems of McNaughton et al. are solved. In addition, we show that shrinking two-pushdown automata and length-reducing two-pushdown automata are equivalent, both in the non-deterministic and the deterministic case, thus obtaining still another characterization of the growing context-sensitive languages and the Church-Rosser languages, respectively.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 197, Issues 1â2, 25 Februaryâ15 March 2005, Pages 1-21
Journal: Information and Computation - Volume 197, Issues 1â2, 25 Februaryâ15 March 2005, Pages 1-21
نویسندگان
Gundula Niemann, Friedrich Otto,