On the Minimization Problem for Sequential Programs
First-order program schemata is one of the simplest models of sequential imperative programs intended for solving verification and optimization problems. We consider the decidable relation of logical-thermal equivalence of these schemata and the problem of their size minimization while preserving lo...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2017-08-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/532 |
| _version_ | 1797877980315254784 |
|---|---|
| author | Vladimir A. Zakharov Shynar R. Zhailauova |
| author_facet | Vladimir A. Zakharov Shynar R. Zhailauova |
| author_sort | Vladimir A. Zakharov |
| collection | DOAJ |
| description | First-order program schemata is one of the simplest models of sequential imperative programs intended for solving verification and optimization problems. We consider the decidable relation of logical-thermal equivalence of these schemata and the problem of their size minimization while preserving logical-thermal equivalence. We prove that this problem is decidable. Further we show that the first-order program schemata supplied with logical-thermal equivalence and finite state deterministic transducers operating over substitutions are mutually translated into each other. This relationship implies that the equivalence checking problem and the minimization problem for these transducers are also decidable. In addition, on the basis of the discovered relationship, we have found a subclass of firstorder program schemata such that their minimization can be performed in polynomial time by means of known techniques for minimization of finite state transducers operating over semigroups. Finally, we demonstrate that in general case the minimization problem for finite state transducers over semigroups may have several non-isomorphic solutions. |
| first_indexed | 2024-04-10T02:26:32Z |
| format | Article |
| id | doaj.art-e0f88eb508854fa59a02e306045141f0 |
| institution | Directory Open Access Journal |
| issn | 1818-1015 2313-5417 |
| language | English |
| last_indexed | 2024-04-10T02:26:32Z |
| publishDate | 2017-08-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj.art-e0f88eb508854fa59a02e306045141f02023-03-13T08:07:29ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172017-08-0124441543310.18255/1818-1015-2017-4-415-433378On the Minimization Problem for Sequential ProgramsVladimir A. Zakharov0Shynar R. Zhailauova1Национальный исследовательский университет "Высшая школа экономики"Московский государственный университет им. М.В. ЛомоносоваFirst-order program schemata is one of the simplest models of sequential imperative programs intended for solving verification and optimization problems. We consider the decidable relation of logical-thermal equivalence of these schemata and the problem of their size minimization while preserving logical-thermal equivalence. We prove that this problem is decidable. Further we show that the first-order program schemata supplied with logical-thermal equivalence and finite state deterministic transducers operating over substitutions are mutually translated into each other. This relationship implies that the equivalence checking problem and the minimization problem for these transducers are also decidable. In addition, on the basis of the discovered relationship, we have found a subclass of firstorder program schemata such that their minimization can be performed in polynomial time by means of known techniques for minimization of finite state transducers operating over semigroups. Finally, we demonstrate that in general case the minimization problem for finite state transducers over semigroups may have several non-isomorphic solutions.https://www.mais-journal.ru/jour/article/view/532последовательная программаавтомат-преобразовательминимизацияподстановкаполугруппаэквивалентность |
| spellingShingle | Vladimir A. Zakharov Shynar R. Zhailauova On the Minimization Problem for Sequential Programs Моделирование и анализ информационных систем последовательная программа автомат-преобразователь минимизация подстановка полугруппа эквивалентность |
| title | On the Minimization Problem for Sequential Programs |
| title_full | On the Minimization Problem for Sequential Programs |
| title_fullStr | On the Minimization Problem for Sequential Programs |
| title_full_unstemmed | On the Minimization Problem for Sequential Programs |
| title_short | On the Minimization Problem for Sequential Programs |
| title_sort | on the minimization problem for sequential programs |
| topic | последовательная программа автомат-преобразователь минимизация подстановка полугруппа эквивалентность |
| url | https://www.mais-journal.ru/jour/article/view/532 |
| work_keys_str_mv | AT vladimirazakharov ontheminimizationproblemforsequentialprograms AT shynarrzhailauova ontheminimizationproblemforsequentialprograms |