انجمن کامپیوتر ایران

در این مقاله به بررسی تصمیم‌پذیری رابطه شبیه‌سازی دوتایی پیش‌ترتیبی بین سیستم‌های بلادرنگ همروند پرداخته می‌شود. رابطه شبیه‌سازی دوتایی پیش‌ترتیبی یک رابطه هم‌ارزی است که برای مقایسه سرعت عملکرد بین دو سیستم بلادرنگ مبتنی بر مدل خودکارهای زمان‌دار کاربرد دارد. تصمیم‌پذیری رابطه شبیه‌سازی دوتایی پیش‌ترتیبی قبلا برای سیستم‌ها و مؤلفه‌های بلادرنگ ترتیبی، با استفاده از گراف ارزش‌دهی منطقه نتیجه شده است. از آنجا که اغلب سیستم‌های بلادرنگ موجود در طبیعت ماهیت همروندی دارند، در این مقاله به فرض همروندی سیستم‌های بلادرنگ با استفاده از تکنیک دست‌تکانی، تصمیم‌پذیری رابطه شبیه‌سازی دوتایی پیش‌ترتیبی با استقرای ریاضی نشان داده می‌شود. نتایج نشان می‌دهد که رابطه شبیه‌سازی دوتایی پیش‌ترتیبی تحت ترکیب موازی با هر خودکار زمان‌دار دیگر بسته نیست. این رابطه با شرط وجود رابطه شبیه‌سازی دوتایی قوی بین گراف‌های ارزش‌دهی منطقه؛ حاصل از ترکیب موازی دو فرایند زمانی و همچنین برقراری تابع تعویض ترتیبی بین گره‌های مشابه دو گراف منطقه برقرار است.