A heuristic method for multi-block parallel decomposition of a system of partial Boolean functions
A heuristic method for multi-block parallel decomposition of a system of partial Boolean functions is described. The method minimizes the number of functions forming the required superposition. The restriction on the number of arguments of the obtained functions is imposed. The method involves the s...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
2018-12-01
|
| Series: | Informatika |
| Subjects: | |
| Online Access: | https://inf.grid.by/jour/article/view/472 |
| _version_ | 1797877320885731328 |
|---|---|
| author | Yu. V. Pottosin |
| author_facet | Yu. V. Pottosin |
| author_sort | Yu. V. Pottosin |
| collection | DOAJ |
| description | A heuristic method for multi-block parallel decomposition of a system of partial Boolean functions is described. The method minimizes the number of functions forming the required superposition. The restriction on the number of arguments of the obtained functions is imposed. The method involves the specification of functions by interval form i. e. in the form of a pair of ternary matrices. One of the matrices represents intervals of Boolean space of the arguments (matrix of intervals), the other one represents the values of the functions at these intervals (matrix of functions). The graphs of rows orthogonality of those matrices are considered. The problem of functions decomposition is reduced to covering the edge set of the rows orthogonality graph of the matrix of functions by complete bipartite subgraphs (bicliques) of the row orthogonality graph of the matrix of intervals. Every biclique is assigned with a disjunctive normal form (DNF) by a certain way, and only those bicliques are taken into consideration whose DNFs have terms with the ranks not more than the bounds of the number of arguments of the obtained functions. The bicliques that form the desired cover and the cover itself are constructed sequentially by certain rules. Every biclique is used to construct the function whose arguments are the variables from the term of minimum rank from the corresponding DNF. The obtained functions are given also in interval form. |
| first_indexed | 2024-04-10T02:15:16Z |
| format | Article |
| id | doaj.art-8a2644560bf04537b123010877549be3 |
| institution | Directory Open Access Journal |
| issn | 1816-0301 |
| language | Russian |
| last_indexed | 2024-04-10T02:15:16Z |
| publishDate | 2018-12-01 |
| publisher | The United Institute of Informatics Problems of the National Academy of Sciences of Belarus |
| record_format | Article |
| series | Informatika |
| spelling | doaj.art-8a2644560bf04537b123010877549be32023-03-13T08:32:20ZrusThe United Institute of Informatics Problems of the National Academy of Sciences of BelarusInformatika1816-03012018-12-01154109116445A heuristic method for multi-block parallel decomposition of a system of partial Boolean functionsYu. V. Pottosin0The United Institute of Informatics Problems, National Academy of Sciences of BelarusA heuristic method for multi-block parallel decomposition of a system of partial Boolean functions is described. The method minimizes the number of functions forming the required superposition. The restriction on the number of arguments of the obtained functions is imposed. The method involves the specification of functions by interval form i. e. in the form of a pair of ternary matrices. One of the matrices represents intervals of Boolean space of the arguments (matrix of intervals), the other one represents the values of the functions at these intervals (matrix of functions). The graphs of rows orthogonality of those matrices are considered. The problem of functions decomposition is reduced to covering the edge set of the rows orthogonality graph of the matrix of functions by complete bipartite subgraphs (bicliques) of the row orthogonality graph of the matrix of intervals. Every biclique is assigned with a disjunctive normal form (DNF) by a certain way, and only those bicliques are taken into consideration whose DNFs have terms with the ranks not more than the bounds of the number of arguments of the obtained functions. The bicliques that form the desired cover and the cover itself are constructed sequentially by certain rules. Every biclique is used to construct the function whose arguments are the variables from the term of minimum rank from the corresponding DNF. The obtained functions are given also in interval form.https://inf.grid.by/jour/article/view/472system of boolean functionsboolean function decompositioninterval representation of boolean functionscover problemcomplete bipartite subgraph |
| spellingShingle | Yu. V. Pottosin A heuristic method for multi-block parallel decomposition of a system of partial Boolean functions Informatika system of boolean functions boolean function decomposition interval representation of boolean functions cover problem complete bipartite subgraph |
| title | A heuristic method for multi-block parallel decomposition of a system of partial Boolean functions |
| title_full | A heuristic method for multi-block parallel decomposition of a system of partial Boolean functions |
| title_fullStr | A heuristic method for multi-block parallel decomposition of a system of partial Boolean functions |
| title_full_unstemmed | A heuristic method for multi-block parallel decomposition of a system of partial Boolean functions |
| title_short | A heuristic method for multi-block parallel decomposition of a system of partial Boolean functions |
| title_sort | heuristic method for multi block parallel decomposition of a system of partial boolean functions |
| topic | system of boolean functions boolean function decomposition interval representation of boolean functions cover problem complete bipartite subgraph |
| url | https://inf.grid.by/jour/article/view/472 |
| work_keys_str_mv | AT yuvpottosin aheuristicmethodformultiblockparalleldecompositionofasystemofpartialbooleanfunctions AT yuvpottosin heuristicmethodformultiblockparalleldecompositionofasystemofpartialbooleanfunctions |