کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875428 1441952 2018 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Two equational theories of partial words
ترجمه فارسی عنوان
دو نظریه معادل از کلمات جزئی
کلمات کلیدی
نظریه های معادن، انواع، سفارشات جزئی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Partial words are in our terminology isomorphism classes of labeled partial orders. We consider two structures. Starting with the partial orders reduced to a unique element, the first one is defined as the closure under the three operations of series product, parallel product and ω-power (ω-series product of the same partial word) and the second one as the closure under the three operations of series product, parallel product and ω-product (ω-series product of possibly different partial words). We show that the two equational theories can be axiomatized by an infinite collection of simple identities, and that no finite axiomatization exists. We characterize the free algebras in the corresponding varieties as algebras of certain partial words subject to order and graph theoretic conditions. We also show that the first equational theory is decidable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 737, 15 August 2018, Pages 19-39
نویسندگان
, ,