کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952102 1442015 2017 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Automaton semigroups: New constructions results and examples of non-automaton semigroups
ترجمه فارسی عنوان
نیمه گروه های اتومات: نتایج ساختارهای جدید و نمونه های نیمه گروه های غیر اتومات
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper studies the class of automaton semigroups from two perspectives: closure under constructions, and examples of semigroups that are not automaton semigroups. We prove that (semigroup) free products of finite semigroups always arise as automaton semigroups, and that the class of automaton monoids is closed under forming wreath products with finite monoids. We also consider closure under certain kinds of Rees matrix constructions, strong semilattices, and small extensions. Finally, we prove that no subsemigroup of (N,+) arises as an automaton semigroup. (Previously, (N,+) itself was the unique example of a semigroup having the 'general' properties of automaton semigroups (such as residual finiteness, solvable word problem, etc.) but that was known not to arise as an automaton semigroup.)
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 674, 25 April 2017, Pages 1-15
نویسندگان
, ,