Алгоритмы проверки некоторых свойств n-квазигрупп
Programming and Computer Software. 2022. № 1. С. 40-53.
Galatenko A. V., Панкратьев А. Е., Staroverov V.
Research target: Mathematics Computer Science
, , , Математические заметки 2022 Т. 111 № 1 С. 8-14
In the paper, it is proved that almost all quasigroups are strongly polynomially complete, i.e., are not isotopic to quasigroups that are not polynomially complete. ...
Added: October 24, 2022
, , , Lobachevskii Journal of Mathematics 2020 Vol. 41 No. 8 P. 1444-1453
Polynomial completeness of an operation guarantees that deciding solvability of equations over this operation is an NP-complete problem. Thus this property is beneficial from the viewpoint of cryptographic applications. We propose an algorithm for verification of polynomial completeness of quasigroups and analyse efficiency of its serial and parallel implementations. ...
Added: October 23, 2020
, , et al., Чебышевский сборник 2021 Т. 22 № 2 С. 76-89
Quasigroup-based cryptoalgorithms are being actively studied in the framework of theoreticprojects; besides that, a number of quasigroup-based algorithms took part in NIST contestsfor selection of cryptographic standards. From the viewpoint of security it is highly desirableto use quasigroups without proper subquasigroups (otherwise transformations can degrade).We propose algorithms that take a quasigroup specified by the Cayley ...
Added: June 16, 2021
, , , Lobachevskii Journal of Mathematics 2020 Vol. 41 No. 2 P. 194-203
We propose a construction that allows generating large families of Latin squares, i.e., Cayley tables of finite quasigroups. This construction generalizes proper families of functions over Abelian groups introduced by Nosov and Pankratiev. We also show that all quasigroups generated by the original construction contain at least one subquasigroup, while the generalized construction generates quasigroups ...
Added: October 7, 2020
, , , Алгебра и логика 2018 Т. 57 № 5 С. 509-521
We formulate a polynomial completeness criterion for quasigroups of prime order, and show that verification of polynomial completeness may require time polynomial in order. The obtained results are generalized to n-quasigroups for any n≥3. In conclusion, simple corollaries are given on the share of polynomially complete quasigroups among all quasigroups, and on the cycle structure of ...
Added: October 7, 2020
, , Дискретная математика 2018 Т. 30 № 4 С. 3-11
The complexity of decision of the polynomial (functional) completeness of a finite quasigroup is investigated. It is shown that the polynomial conpleteness of a finite quasigroup can be decided in polynomial time with respect to the order of the quasigroup. ...
Added: October 7, 2020
, , , Lobachevskii Journal of Mathematics 2022 Vol. 43 No. 3 P. 571-581
Proper families of functions are a convenient framework for specification of large parametric families of quasigroups and 𝑛-quasigroups. We propose two methods for generation of proper families. The first method uses proper families of the order 𝑚 to construct proper families of the order 𝑚+1. The second method allows generating uniform distribution on the set ...
Added: October 24, 2022
Formal Concept Analysis: 16th International Conference, ICFCA 2021, Strasbourg, France, June 29 – July 2, 2021, Proceedings
This book constitutes the proceedings of the 16th International Conference on Formal Concept Analysis, ICFCA 2021, held in Strasbourg, France, in June/July 2021. The 14 full papers and 5 short papers presented in this volume were carefully reviewed and selected from 32 submissions. The book also contains four invited contributions in full paper length. The research part ...
Added: July 10, 2021
Сценарное моделирование движения беспилотных транспортных средств в искусственной дорожной сети с использованием FLAME GPU
, , Искусственные общества 2021 Т. 16 № 1 С. 1-23
This article presents a model of the ground autonomous vehicles (AVs) motion in the Artificial Road Network (ARN) belonging to the "Manhattan Lattice" type with the implementation of the large-scale agent-based modeling framework FLAME GPU. The most important scenarios of the traffic situation development are investigated, in particular, which are associated with reducing visibility on ...
Added: April 1, 2021
, , Дискретная математика 2017 Т. 29 № 3 С. 114-125
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. Предлагается новый способ редукции графов. С его помощью получено новое доказательство NP-полноты задачи о независимом множестве в классе планарных графов и доказана NP-полнота данной задачи в классе плоских графов, имеющих только треугольные внутренние грани, с максимальной степенью ...
Added: September 7, 2017
Lanham : University Press of America, 2012
The history of logic and analytic philosophy in Central and Eastern Europe is still known to very few people. As an exception to the rule, only two scientific schools became internationally popular: the Vienna Circle and the Lvov-Warsaw School. Nevertheless, the countries included in this region have not only joint history, but also joint cultural ...
Added: February 13, 2013
Пермь : Пермский государственный национальный исследовательский университет, 2020
В сборнике представлены статьи участников Всероссийской научно-практической конференции молодых ученых с международным участием «Математика и междисциплинарные исследования – 2020». На конференцию было прислано более ста статей из различных регионов России, а также из ближнего и дальнего зарубежья. По итогам работы экспертной комиссии для публикации было отобрано шестьдесят две статьи. Каждая статья оценивалась группой экспертов в той области, которая рассматривается автором. Представленные ...
Added: December 10, 2020
, , et al., Всероссийский криминологический журнал 2015 Т. 9 № 3 С. 423-430
Modern criminalists do not share a common opinion regarding the choice of parameters which could be used to work out a system of characteristics to differentiate a maniac killer from an ordinary person. This hinders the development of efficient software for investigation purposes. The paper describes the experience of developing a neural network that can ...
Added: October 1, 2015
, , , Журнал Новой экономической ассоциации 2021 Т. 2 № 50 С. 12-34
. The problem of analysis of pairwise connections between stocks of financial market by observations on stock returns is considered. Such problem arise in stock market network analysis. It is assumed that joint distribution of stock returns belongs to the wide class of elliptical distributions. Classical Pearson correlation, Fechner correlation and Kendall correlation are used ...
Added: June 17, 2021
Agent-based modelling of interactions between air pollutants and greenery using a case study of Yerevan, Armenia
, , , Environmental Modelling and Software 2019 Vol. 116 P. 7-25
Urban greenery such as trees can effectively reduce air pollution in a natural and eco-friendly way. However, how to spatially locate and arrange greenery in an optimal way remains as a challenging task. We developed an agent-based model of air pollution dynamics to support the optimal allocation and configuration of tree clusters in a city. The Pareto ...
Added: February 24, 2019
, , Сибирский журнал индустриальной математики 2013 Т. XVI № 4 С. 111-120
The paper considers the problem of determining the rate of cooling of metal during solidification at the intersection of the liquidus temperature under intense heat sink from the surface. The solution to this problem it is necessary to determine the process conditions, the boundary and initial conditions for which it is possible to get new ...
Added: November 17, 2013
, , Information Processing Letters 2012 Т. 112 № 3 С. 72-76
In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. A pseudo-polynomial time solution algorithm is proposed for a special case of this problem. Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number of tardy jobs on a single ...
Added: November 24, 2012
, , et al., ACM Transactions on Computation Theory 2018 Vol. 10 No. 2 P. 1-32
The H-free Edge Deletion problem asks, for a given graph G and integer k, whether it is possible to delete at most k edges from G to make it H-free—that is, not containing H as an induced subgraph. The H-free Edge Completion problem is defined similarly, but we add edges instead of deleting them. The study of these two problem families has recently been the subject of intensive studies from the point of ...
Added: October 30, 2018
Algorithms and methods for solving scheduling problems and other extremum problems on large-scale graphs
, , et al., Journal of Mathematical Sciences 2005 Vol. 128 No. 6 P. 3487-3495
Added: January 27, 2014
The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
, Discrete Mathematics 2015 Vol. 338 No. 11 P. 1860-1865
We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. ...
Added: April 7, 2014
P. : Université Paris 13 - Paris Sorbonne Cité, 2013
In this workshop we will bring together participants who have solutions for one or more of the following problems: How can mutual understanding be optimized with the help of technology in hospitals where both patients and professionals have varying language skills, cultural backgrounds and cognitive capacities? Can domain ontologies, natural language processing tools, multilingual knowledge-based ...
Added: December 18, 2014
, Дискретная математика 1991 Т. 3 № 3 С. 35-45
Added: October 17, 2014
, Journal of Applied and Industrial Mathematics 2020 Vol. 14 No. 4 P. 706-721
The edge coloring problem for a graph is to minimize the number of colors that are sufficient to color all edges of the graph so that all adjacent edges receive distinct colors. The computational complexity of the problem is known for all graph classes defined by forbidden subgraphs with at most 6 edges. We improve ...
Added: January 30, 2021
, , et al., Journal of Mathematical Sciences 2009 Vol. 163 No. 5 P. 469-486
Sequential and parallel implementations of the F4 algorithm for computing Gr¨obner bases of polynomial ideals are discussed. ...
Added: October 1, 2014