18 results
Search Results
2. On Algorithmic Methods of Analysis of Two-Colorings of Hypergraphs.
- Author
-
Lebedeva, A.
- Subjects
- *
ALGORITHMS , *HYPERGRAPHS , *PROBLEM solving , *NUMBER theory , *MATHEMATICAL analysis - Abstract
Abstract. This paper deals with an extremal problem concerning hypergraph colorings. Let k be an integer. The problem is to find the value m( n) equal to the minimum number of edges in an n-uniform hypergraph not admitting two-colorings of the vertex set such that every edge of the hypergraph contains at least k vertices of each color. In this paper, we obtain upper bounds of m( n) for small k and n, the exact value of m(8), and a lower bound for m(7). [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
3. Periodic Residually Finite Groups with Abelian Subgroups of Finite Ranks.
- Author
-
Chubarova, E.
- Subjects
- *
GROUP theory , *FINITE element method , *ALGORITHMS , *NUMBER theory , *MATHEMATICAL analysis - Abstract
In this paper, the investigation of groups with additional finiteness conditions is continued. Criteria of residual finiteness and of almost local solvability of a periodic F* -group are obtained. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
4. The Structure of Finite Distributive Lattices.
- Author
-
Shmatkov, V.
- Subjects
- *
FINITE element method , *LATTICE theory , *ALGORITHMS , *NUMBER theory , *MATHEMATICAL analysis - Abstract
This paper is devoted to the structure that describes the construction of finite distributive lattices. From the viewpoint of application, we consider algorithms of construction and enumeration of distributive lattices and partially ordered sets for finite distributive lattices: A formula for finding the maximum anti-chain with respect to nonintersection is given, it is shown that elements of the lattice can be split into pairs according to comparison, the point of the maximum number of elements in the lattices is considered, and the structure of lattice congruence is described. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
5. To solving problems of algebra for two-parameter matrices. X.
- Author
-
Kublanovskaya, V.
- Subjects
- *
PROBLEM solving , *MATRICES (Mathematics) , *FACTORIZATION , *ALGORITHMS , *POLYNOMIALS , *BASIS (Linear algebra) , *MATHEMATICAL analysis - Abstract
The paper considers conditions under which rank factorizations of a two-parameter polynomial matrix can be affected with the use of unimodular matrices, as in the one-parameter case. Algorithms for computing such factorizations and a minimal basis of the null space of the corresponding matrix are presented. Also an algorithm for inverting unimodular two-parameter polynomial matrices is suggested. Bibliography: 4 titles. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
6. Cycle detection algorithms and their applications.
- Author
-
Nesterenko, A.
- Subjects
- *
ALGORITHMS , *NUMBER theory , *FACTORIZATION , *COMPUTATIONAL complexity , *MATHEMATICAL analysis , *PROOF theory - Abstract
This paper considers several cycle detection algorithms. Proofs of their correctness are given, bounds for complexity are obtained, some number theory applications like the factorization of integers and the discrete log problem are examined. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
7. Fast algorithms for implementation of the Green's function.
- Author
-
Yunakovsky, A.
- Subjects
- *
GREEN'S functions , *ALGORITHMS , *HELMHOLTZ equation , *OPERATOR theory , *PERIODIC functions , *MATHEMATICAL analysis - Abstract
This paper is devoted to new fast algorithms for implementation of the Green's function for the Helmholtz operator in high-frequency regions in periodic and helical structures. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
8. Permutation binomials and their groups.
- Author
-
Vasilev, N. and Rybalkin, M.
- Subjects
- *
PERMUTATION groups , *FINITE fields , *ALGORITHMS , *GENERALIZATION , *PROBLEM solving , *MATHEMATICAL functions , *MATHEMATICAL analysis - Abstract
This paper is devoted to studying the properties of permutation binomials over finite fields and the possibility to use permutation binomials as encryption functions. We present an algorithm for enumeration of permutation binomials. Using this algorithm, all permutation binomials for finite fields up to order 15000 were generated. Using this data, we investigate the groups generated by the permutation binomials and discover that over some finite fields $$ {{\mathbb F}_q} $$, every bijective function on [1.. q − 1] can be represented as a composition of binomials. We study the problem of generating permutation binomials over large prime fields. We also prove that a generalization of RSA using permutation binomials is not secure. Bibliography: 9 titles. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
9. Constructing a spanning tree with many leaves.
- Author
-
Gravin, N.
- Subjects
- *
SPANNING trees , *MAXIMA & minima , *SET theory , *POLYNOMIALS , *NUMBER theory , *ALGORITHMS , *MATHEMATICAL analysis - Abstract
It was shown by Griggs and Wu that a graph of minimal degree 4 on n vertices has a spanning tree with at least $$ \frac{2}{5} $$ n leaves, which is asymptomatically the best possible bound for this class of graphs. In this paper, we present a polynomial time algorithm that finds in any graph with k vertices of degree greater than or equal to 4 and k′ vertices of degree 3 a spanning tree with $$ \left[ {\frac{2}{5} \cdot k + \frac{2}{{15}} \cdot k'} \right] $$ leaves. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
10. Quantization in discrete dynamical systems.
- Author
-
Kornyak, V.
- Subjects
- *
GROUP theory , *MATHEMATICAL models , *AUTOMORPHISMS , *MATHEMATICAL analysis , *ALGORITHMS - Abstract
We consider a class of discrete dynamical models allowing a quantum description. Our approach to quantization consists in the introduction of a gauge connection with values in an n-dimensional unitary representation of some group (of internal symmetries) Γ; elements of the connection are interpreted as amplitudes of quantum transitions. The standard quantization is a special case of this construction: Feynman’s path amplitude e i ∫ Ldt can be interpreted as a parallel transport with values in the (1-dimensional) fundamental representation of the group Γ= U(1). If we take a finite group as the quantizing group Γ, all our manipulations – in contrast to the standard quantization – remain within the framework of constructive discrete mathematics, requiring no more than the ring of algebraic integers. On the other hand, the standard quantization can be approximated by taking 1-dimensional representations of sufficiently large finite groups. The models considered in this paper are defined on regular graphs with transitive groups of automorphisms (space symmetries). The vertices of the graphs take values in finite sets of local states. The evolution of the models proceeds in discrete time steps. We assume that one-time-step quantum transitions are allowed only within neighborhoods of the graph vertices. Simple illustrations are given. An essential part of our study was carried out with the help of a program in C implementing computer algebra and computational group theory algorithms that we develop now. Bibliography: 4 titles. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
11. Correct and self-adjoint problems with cubic operators.
- Author
-
Parasidis, I., Tsekrekos, P., and Lokkas, T.
- Subjects
- *
MATHEMATICAL analysis , *ALGEBRA , *ALGORITHMS , *BOUNDARY value problems , *DIFFERENTIAL equations - Abstract
In this paper, we present a simple method to prove the correctness and self-adjointness of operators B3 corresponding to some boundary problems. We also give the unique solutions for these problems. The algorithm is easy to implement via computer algebra systems. In our examples, Derive and Mathematica were used. Bibliography: 10 titles. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
12. A reference point technique to compute nondominated solutions in MOLFP.
- Author
-
Costa, J. P. and Alves, M. J.
- Subjects
- *
LINEAR programming , *MATHEMATICAL programming , *ALGORITHMS , *MATHEMATICAL optimization , *MATHEMATICAL analysis - Abstract
This paper presents a new technique to compute nondominated solutions in multiobjective linear-fractional programming (MOLFP) by using reference points. The basic idea consists in dividing the nondominated region approximately through the “middle” making two subregions, which are then analyzed in order to try to discard one of them. The process is repeated with the remaining region(s), and it ends when the regions become so small that the differences among their nondominated solutions are lower than a predefined margin of error. The results of several tests carried out to evaluate the performance of the technique are reported. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
13. To solving multiparameter problems of algebra. 10. Computing zeros of a scalar polynomial.
- Author
-
Kublanovskaya, V.
- Subjects
- *
ALGEBRA , *POLYNOMIALS , *MATHEMATICAL variables , *ALGORITHMS , *MATHEMATICAL analysis - Abstract
The paper considers the problem of computing zeros of scalar polynomials in several variables. The zeros of a polynomial are subdivided into the regular (eigen-and mixed) zeros and the singular ones. An algorithm for computing regular zeros, based on a decomposition of a given polynomial into a product of primitive polynomials, is suggested. The algorithm is applied to solving systems of nonlinear algebraic equations. Bibliography: 5 titles. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
14. Filling the gap between the Gerschgorin and Brualdi theorems.
- Author
-
Kolotilina, L.
- Subjects
- *
MATRICES (Mathematics) , *MATHEMATICAL analysis , *ALGORITHMS , *DIFFERENTIAL equations , *EIGENVALUES - Abstract
The paper presents new diagonal dominance type nonsingularity conditions for n × n matrices formulated in terms of circuits of length not exceeding a fixed number r ≥ 0 and simple paths of length r in the digraph of the matrix. These conditions are intermediate between the diagonal dominance conditions in terms of all paths of length r and Brualdi’s diagonal dominance conditions, involving all the circuits. For r = 0, the new conditions reduce to the standard row diagonal dominance conditions $$\left| {a_{ii} } \right| \geqslant \sum\limits_{j \ne i} {\left| {a_{ij} } \right|} $$ , i = 1, ..., n, whereas for r = n they coincide with the Brualdi circuit conditions. Thus, they connect the classical Lévy-Desplanques theorem and the Brualdi theorem, yielding a family of sufficient nonsingularity conditions. Further, for irreducible matrices satisfying the new diagonal dominance conditions with nonstrict inequalities, the singularity/nonsingularity problem is solved. Also the new sufficient diagonal dominance conditions are extended to the so-called mixed conditions, simultaneously involving the deleted row and column sums of an arbitrary finite set of matrices diagonally conjugated to a given one, which, in the simplest nontrivial case, reduce to the old-known Ostrowski conditions $$\left| {a_{ii} } \right| > \left( {\sum\limits_{j \ne i} {\left| {a_{ij} } \right|} } \right)^\alpha \left( {\sum\limits_{j \ne i} {\left| {a_{ji} } \right|} } \right)^{1 - \alpha } $$ , i = 1, ..., n, 0 ≤ α ≤ 1. The nonsingularity conditions obtained are used to provide new eigenvalue inclusion sets, depending on r, which, as r varies from 0 to n, serve as a bridge connecting the union of Gerschgorin’s disks with the Brualdi inclusion set. Bibliography: 16 titles. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
15. Object search. Dynamics. Geometry. Graphics.
- Author
-
Shikin, E. and Berezin, S.
- Subjects
- *
DYNAMICS , *PLANE geometry , *MATHEMATICS education , *MATHEMATICAL analysis , *ALGORITHMS , *GRAPHICAL modeling (Statistics) - Abstract
The paper describes certain geometric methods for solution of the search problem of several searching and several evading objects in the plane. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
16. To solving multiparameter problems of algebra. 7. The PG-q factorization method and its applications.
- Author
-
Kublanovskaya, V.
- Subjects
- *
ALGEBRA , *MATHEMATICAL analysis , *POLYNOMIALS , *MATRICES (Mathematics) , *ALGORITHMS , *FACTORIZATION - Abstract
The paper continues the development of rank-factorization methods for solving certain algebraic problems for multi-parameter polynomial matrices and introduces a new rank factorization of a q-parameter polynomial m × n matrix F of full row rank (called the PG-q factorization) of the form F = PG, where $$P = \prod\limits_{k = 1}^{q - 1} {\prod\limits_{i = 1}^{n_k } {\nabla _i^{(k)} } } $$ is the greatest left divisor of F; Δ i is a regular (q-k)-parameter polynomial matrix the characteristic polynomial of which is a primitive polynomial over the ring of polynomials in q-k-1 variables, and G is a q-parameter polynomial matrix of rank m. The PG-q algorithm is suggested, and its applications to solving some problems of algebra are presented. Bibliography: 6 titles. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
17. To Solving Multiparameter Problems of Algebra. 4. The AB-Algorithm and its Applications.
- Author
-
Kublanovskaya, V.
- Subjects
- *
FACTORIZATION , *ALGORITHMS , *MATRICES (Mathematics) , *SPECTRUM analysis , *MATHEMATICAL analysis , *POLYNOMIALS , *FACTOR analysis , *FACTORS (Algebra) - Abstract
The paper continues the investigation of methods for factorizing q-parameter polynomial matrices and considers their applications to solving multiparameter problems of algebra. An extension of the AB-algorithm, suggested earlier as a method for solving spectral problems for matrix pencils of the form A - λB, to the case of q-parameter (q ≥ 1) polynomial matrices of full rank is proposed. In accordance with the AB-algorithm, a finite sequence of q-parameter polynomial matrices such that every subsequent matrix provides a basis of the null-space of polynomial solutions of its transposed predecessor is constructed. A certain rule for selecting specific basis matrices is described. Applications of the AB-algorithm to computing complete polynomials of a q-parameter polynomial matrix and exhausting them from the regular spectrum of the matrix, to constructing irreducible factorizations of rational matrices satisfying certain assumptions, and to computing “free” bases of the null-spaces of polynomial solutions of an arbitrary q-parameter polynomial matrix are considered. Bibliography: 7 titles. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
18. Upper Bounds on Height of Terms in a Solution of a Semiunification Problem.
- Author
-
Zhizhkun, V. B.
- Subjects
- *
GROUP theory , *ALGORITHMS , *EQUATIONS , *SEMIGROUPS (Algebra) , *MATHEMATICAL functions , *MATHEMATICAL analysis - Abstract
In this paper, we investigate a decidable case of the term semiunification problem. In our case, the arity of any functional symbol in terms equals one (with a possible exception for outer symbols of terms, for which no restrictions are imposed). We propose an algorithm constructing the most general solution of the semiunification problem. In addition, we prove an upper bound on the height of this solution; this upper bound is linear with respect to heights of terms in the initial problem. Our method reduces the problem for terms to a special system of equations in free semigroups and solves the latter system. Bibliography: 10 titles. [ABSTRACT FROM AUTHOR]
- Published
- 2003
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.