کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
438261 690246 2008 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The computable kernel of Abstract State Machines
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The computable kernel of Abstract State Machines
چکیده انگلیسی

Abstract State Machines (ASMs) were introduced as “a computation model that is more powerful and more universal than standard computation models”, by Yuri Gurevich in 1985. ASMs gained much attention as a specification method. It is extremely flexible because any mathematical structure may serve as a state. Gurevich characterized the expressive power of ASMs in terms of intuitively convincing postulates.The core result of this paper shows that the next-state function M of an Abstract State Machine M can be described on a symbolic level, notwithstanding the generality of the model: The successor state of a state S is fully specified by the equivalence ∼S induced by S on the terms over the signature of M. Consequently, is computable in case ∼S is decidable. Furthermore, this result implies a notion of computability for general structures, e.g. for algorithms operating on real numbers.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 409, Issue 1, 6 December 2008, Pages 126-136