RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2020 Volume 32, Issue 2, Pages 61–70 (Mi dm1602)

This article is cited in 5 papers

On the degree of restrictions of $q$-valued logic vector functions to linear manifolds

V. G. Ryabov

NP «GST»

Abstract: We obtain estimates for the probability that for a randomly selected $k$-dimensional $n$-place $q$-valued logic vector function there exists a linear manifold of fixed dimension such that the degree of the restriction of the function to this manifold is not larger than the given value. The asymptotics of the number of manifolds on which the restrictions are affine is obtained. It is shown that if $n \to \infty$ and $k\leq n/q$, then for almost all $k$-dimensional $n$-place vector functions the maximum dimension of a manifold on which the restriction is affine lies in the interval $[\lfloor \log_q \frac{n}{k}+\log_q \log_q \frac{n}{k} \rfloor, \lceil \log_q \frac{n}{k}+\log_q \log_q \frac{n}{k} \rceil]$, while the analogous parameter for the case of fixed variables lies in the range $[\lfloor \log_q \frac{n}{k} \rfloor, \lceil \log_q \frac{n}{k} \rceil]$.

Keywords: $q$-valued logic, vector function, restriction, manifold, degree.

UDC: 519.716.325+519.1:519.21

Received: 09.12.2019
Revised: 13.05.2020

DOI: 10.4213/dm1602


 English version:
Discrete Mathematics and Applications, 2021, 31:2, 127–134

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024