کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9656892 | 686056 | 2005 | 35 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The equational theory of regular words
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The equational theory of regular words The equational theory of regular words](/preview/png/9656892.png)
چکیده انگلیسی
Courcelle introduced the study of regular words, i.e., words isomorphic to frontiers of regular trees. Heilbrunner showed that a nonempty word is regular iff it can be generated from the singletons by the operations of concatenation, omega power, omega-op power, and the infinite family of shuffle operations. We prove that the algebra of nonempty regular words on the set A, equipped with these operations, is freely generated by A in a variety which is axiomatizable by an infinite collection of some natural equations. We also show that this variety has no finite equational basis and that its equational theory is decidable in polynomial time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 197, Issues 1â2, 25 Februaryâ15 March 2005, Pages 55-89
Journal: Information and Computation - Volume 197, Issues 1â2, 25 Februaryâ15 March 2005, Pages 55-89
نویسندگان
Stephen L. Bloom, Zoltán Ãsik,