О минимизации схем программ относительно логико-термальной эквивалентности
This book constitutes the refereed proceedings of the 13th International Haifa Verification Conference, HVC 2017, held in Haifa, Israel in November 2017. The 13 revised full papers presented together with 4 poster and 5 tool demo papers were carefully reviewed and selected from 45 submissions. They are dedicated to advance the state of the art and state of the practice in verification and testing and are discussing future directions of testing and verification for hardware, software, and complex hybrid systems.
We consider single machine scheduling problems. N jobs that must be processed on the machine are given. Machine is ready to star processing since time 0 and can handle only one job at a time. Preemptions are not allowed. Each job $j$ is characterized by processing time $p_j$, due date $d_j$, and release date $r_j$. Our goal is to construct a schedule of processing that minimizes total tardiness of the jobs. We propose a new approach to construct approximate solutions with guaranteed absolute error for the problem. The approach consists in finding an instance of the problem, closest to a given instance in certain metric and using its optimal schedule as an approximate solution for the given instance. The approach can be generalized to scheduling problems with other objective functions.
Finite state transducers over semigroups can be regarded as a formal model of sequential reactive programs. In this paper we introduce a uniform tech- nique for checking eectively functionality, k-valuedness, equivalence and inclusion for this model of computation in the case when a semigroup these transducers op- erate over is embeddable in a decidable group.