کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436554 690015 2006 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Message-passing automata are expressively equivalent to EMSO logic
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Message-passing automata are expressively equivalent to EMSO logic
چکیده انگلیسی

We study the expressiveness of finite message-passing automata with a priori unbounded FIFO channels and show them to capture exactly the class of MSC languages that are definable in existential monadic second-order logic interpreted over MSCs. Furthermore, we prove the monadic quantifier-alternation hierarchy over MSCs to be infinite and conclude that the class of MSC languages accepted by message-passing automata is not closed under complement.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 358, Issues 2–3, 7 August 2006, Pages 150-172