کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
11002451 | 1441438 | 2018 | 24 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Verifying minimum spanning tree algorithms with Stone relation algebras
ترجمه فارسی عنوان
بررسی حداقل الگوریتم درخت درختی با جبر های رابطه سنگ
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study a generalisation of relation algebras in which the underlying Boolean algebra structure is replaced with a Stone algebra. Many theorems of relation algebras generalise with no or small changes. Weighted graphs represented as matrices over extended real numbers form an instance. Relational concepts and methods can thus be applied to weighted graphs. We formally specify the problem of computing minimum spanning forests and express Kruskal's algorithm in relation-algebraic terms. We give a total-correctness proof of the algorithm. All results are formally verified in Isabelle/HOL. This paper is an extended version of [40].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Logical and Algebraic Methods in Programming - Volume 101, December 2018, Pages 132-150
Journal: Journal of Logical and Algebraic Methods in Programming - Volume 101, December 2018, Pages 132-150
نویسندگان
Walter Guttmann,