АЛГОРИТМИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ ОБМЕЖЕНЬ З ЦІЛИМИ КОЕФІЦІЄНТАМИ У МНОЖИНІ {0, 1}

АЛГОРИТМИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ ОБМЕЖЕНЬ З ЦІЛИМИ КОЕФІЦІЄНТАМИ У МНОЖИНІ {0, 1}

The basic concepts of linear homogeneous and inhomogeneous equations and inequalities in the domain {0, 1}, are considered the properties of the TSS-algorithm, which may be applied in solving those systems are described. The procedures for clearing the sets of solutions and determining the linearly...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2025
Hauptverfasser: Kryvyi, S.L., Antonyuk, V.T.
Format: Artikel
Sprache:English
Veröffentlicht: V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2025
Schlagworte:
базис множини розв’язків
незалежні множини вершин
пастки та дедлоки мереж Петрі
системи діофантових рівнянь
нерівностей
Online Zugang:https://jais.net.ua/index.php/files/article/view/664
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Problems of Control and Informatics

Institution

Problems of Control and Informatics
id oai:ojs2.jais.net.ua:article-664
record_format ojs
institution Problems of Control and Informatics
baseUrl_str
datestamp_date 2025-10-09T15:01:42Z
collection OJS
language English
topic базис множини розв’язків
незалежні множини вершин
пастки та дедлоки мереж Петрі
системи діофантових рівнянь
нерівностей
spellingShingle базис множини розв’язків
незалежні множини вершин
пастки та дедлоки мереж Петрі
системи діофантових рівнянь
нерівностей
Kryvyi, S.L.
Antonyuk, V.T.
АЛГОРИТМИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ ОБМЕЖЕНЬ З ЦІЛИМИ КОЕФІЦІЄНТАМИ У МНОЖИНІ {0, 1}
topic_facet basis of the set of solutions
independent sets of vertices
traps and deadlocks of Petri nets
systems of Diophantine equations
inequalities
базис множини розв’язків
незалежні множини вершин
пастки та дедлоки мереж Петрі
системи діофантових рівнянь
нерівностей
format Article
author Kryvyi, S.L.
Antonyuk, V.T.
author_facet Kryvyi, S.L.
Antonyuk, V.T.
author_sort Kryvyi, S.L.
title АЛГОРИТМИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ ОБМЕЖЕНЬ З ЦІЛИМИ КОЕФІЦІЄНТАМИ У МНОЖИНІ {0, 1}
title_short АЛГОРИТМИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ ОБМЕЖЕНЬ З ЦІЛИМИ КОЕФІЦІЄНТАМИ У МНОЖИНІ {0, 1}
title_full АЛГОРИТМИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ ОБМЕЖЕНЬ З ЦІЛИМИ КОЕФІЦІЄНТАМИ У МНОЖИНІ {0, 1}
title_fullStr АЛГОРИТМИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ ОБМЕЖЕНЬ З ЦІЛИМИ КОЕФІЦІЄНТАМИ У МНОЖИНІ {0, 1}
title_full_unstemmed АЛГОРИТМИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ ОБМЕЖЕНЬ З ЦІЛИМИ КОЕФІЦІЄНТАМИ У МНОЖИНІ {0, 1}
title_sort алгоритми розв’язання систем лінійних обмежень з цілими коефіцієнтами у множині {0, 1}
title_alt ALGORITHMS FOR SOLVING THE SYSTEMS OF LINEAR CONSTRAINTS WITH INTEGER COEFFICIENTS IN THE SET {0, 1}
description The basic concepts of linear homogeneous and inhomogeneous equations and inequalities in the domain {0, 1}, are considered the properties of the TSS-algorithm, which may be applied in solving those systems are described. The procedures for clearing the sets of solutions and determining the linearly dependent equations of the system during the process of the TSS-algorithm are shown. Based on the basic concepts and properties, a memory effective modification of the TSS-algorithm for solving systems of linear homogeneous equations and inequalities with integer coefficients in {0, 1} is offered. A description of the proposed algorithm using pseudo-code and an estimate of the time complexity are given. Algorithms for solving a separate class of systems of linear homogeneous equations and inequalities whose coefficients belong to the set {– 1, 0, 1} are considered. A series of theorems that prove the correctness of the proposed algorithms are given. It is described their application to the following problems: finding sets of independent vertices of an undirected graph; finding deadlocks and traps in the Petri net; analysis of a set of clauses for inconsistency. For the task of finding sets of independent vertices of an undirected graph, a detailed description of reducing the problem to a system of linear inequalities is given, two solution algorithms are proposed, as well as a modification of the second algorithm. Examples are presented with a detailed explanation of the solution via each of the algorithms and their time characteristics of work are described. For problems of finding deadlocks and traps in the Petri net, a method for reducing it to systems of linear inequalities with coefficients in the set {– 1, 0, 1} and solutions in the set {0, 1} is proposed. An example with the solution explanation and time characteristics of the work of the offered algorithm is described. The algorithm for analyzing the set of clauses for inconsistency is presented in a pseudo-code form. In addition to checking for the inconsistency of a given set of clauses, it allows you to find the minimal inconsistent subsets of clauses if they exist. The operation of the algorithm is illustrated with examples and time characteristics of the algorithm are described.
publisher V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
publishDate 2025
url https://jais.net.ua/index.php/files/article/view/664
work_keys_str_mv AT kryvyisl algorithmsforsolvingthesystemsoflinearconstraintswithintegercoefficientsintheset01
AT antonyukvt algorithmsforsolvingthesystemsoflinearconstraintswithintegercoefficientsintheset01
AT kryvyisl algoritmirozvâzannâsistemlíníjnihobmeženʹzcílimikoefícíêntamiumnožiní01
AT antonyukvt algoritmirozvâzannâsistemlíníjnihobmeženʹzcílimikoefícíêntamiumnožiní01
first_indexed 2025-10-30T02:49:34Z
last_indexed 2025-10-30T02:49:34Z
_version_ 1847373410182627328
spelling oai:ojs2.jais.net.ua:article-6642025-10-09T15:01:42Z ALGORITHMS FOR SOLVING THE SYSTEMS OF LINEAR CONSTRAINTS WITH INTEGER COEFFICIENTS IN THE SET {0, 1} АЛГОРИТМИ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ ОБМЕЖЕНЬ З ЦІЛИМИ КОЕФІЦІЄНТАМИ У МНОЖИНІ {0, 1} Kryvyi, S.L. Antonyuk, V.T. basis of the set of solutions independent sets of vertices traps and deadlocks of Petri nets systems of Diophantine equations, inequalities базис множини розв’язків незалежні множини вершин пастки та дедлоки мереж Петрі системи діофантових рівнянь, нерівностей The basic concepts of linear homogeneous and inhomogeneous equations and inequalities in the domain {0, 1}, are considered the properties of the TSS-algorithm, which may be applied in solving those systems are described. The procedures for clearing the sets of solutions and determining the linearly dependent equations of the system during the process of the TSS-algorithm are shown. Based on the basic concepts and properties, a memory effective modification of the TSS-algorithm for solving systems of linear homogeneous equations and inequalities with integer coefficients in {0, 1} is offered. A description of the proposed algorithm using pseudo-code and an estimate of the time complexity are given. Algorithms for solving a separate class of systems of linear homogeneous equations and inequalities whose coefficients belong to the set {– 1, 0, 1} are considered. A series of theorems that prove the correctness of the proposed algorithms are given. It is described their application to the following problems: finding sets of independent vertices of an undirected graph; finding deadlocks and traps in the Petri net; analysis of a set of clauses for inconsistency. For the task of finding sets of independent vertices of an undirected graph, a detailed description of reducing the problem to a system of linear inequalities is given, two solution algorithms are proposed, as well as a modification of the second algorithm. Examples are presented with a detailed explanation of the solution via each of the algorithms and their time characteristics of work are described. For problems of finding deadlocks and traps in the Petri net, a method for reducing it to systems of linear inequalities with coefficients in the set {– 1, 0, 1} and solutions in the set {0, 1} is proposed. An example with the solution explanation and time characteristics of the work of the offered algorithm is described. The algorithm for analyzing the set of clauses for inconsistency is presented in a pseudo-code form. In addition to checking for the inconsistency of a given set of clauses, it allows you to find the minimal inconsistent subsets of clauses if they exist. The operation of the algorithm is illustrated with examples and time characteristics of the algorithm are described. Розглянуто базові поняття систем лінійних однорідних і неоднорідних рівнянь і нерівностей в області {0, 1}, до розв’язання яких застосовується TSS-алгоритм, та властивості цього алгоритму. Описано процедури чистки множин розв’язків тавизначено лінійно залежні рівняння системи при роботі TSS-алгоритму. На основі базових понять і властивостей пропонується достатньо економна відносно пам’яті модифікація TSS-алгоритму для чисельного розв’язання системлiнiйних однорiдних рiвнянь i нерiвностей з цiлими коефiцiєнтами в областi {0, 1}. Наводиться опис запропонованого алгоритму за допомогою псевдокоду і оцiнка часової складностi запропонованого алгоритму . Розглянуто алгоритми розв’язання окремого класу систем лiнiйних однорiдних рiвнянь i нерiвностей, коефiцiєнти яких належать множинi {– 1, 0, 1}. Наведено ряд теорем, що доводять правильність пропонованих алгоритмів. Описано їх застосування до розв’язання наступних задач: пошуку множин незалежних вершин неорiєнтованого графа; пошуку дедлокiв i пасток в мережi Петрi; аналiзу множини диз'юнктiв на суперечність/несуперечність. Для задачі пошуку множин незалежних вершин неорієнтованого графа наведено детальний опис зведення задачі до системи лінійних однорідних нерівностей, запропоновано два алгоритми розв’язання, а також модифiкацiя другого алгоритму. Наведено приклади з детальним поясненням виконання кожного з алгоритмів, а також описано їх часові характеристики роботи. Для задач пошуку дедлоків і пасток в мережі Петрі запропоновано спосіб зведення до систем лінійних нерівностей з коефіцієнтами в множинi {– 1, 0, 1} та розв’язками в множині {0, 1}. Наведено приклад з поясненням розв’язання і часовi характеристики роботи запропонованого алгоритму. Алгоритм для аналізу множини диз’юнктів на суперечність представлений у вигляді псевдокоду. Окрім перевірки на суперечність заданої множини диз’юнктів, він дозволяє знаходити мінімальні суперечні підмножини диз’юнктів, якщо вони існують. Робота алгоритму ілюструється на прикладах з часовими характеристиками. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2025-10-09 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/664 10.1615/JAutomatInfScien.v51.i7.10 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 64 № 4 (2019): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 5-25 International Scientific Technical Journal "Problems of Control and Informatics; Том 64 № 4 (2019): International Scientific and Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 5-25 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 64 No. 4 (2019): International Scientific and Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 5-25 2786-6505 2786-6491 en https://jais.net.ua/index.php/files/article/view/664/731 https://creativecommons.org/licenses/by-nc-nd/4.0

Ähnliche Einträge