Geodesic
Criterion for equational Noetherianity and complexity of the solvability problem for systems of equations over partially ordered sets
Prikladnaâ diskretnaâ matematika, no. 2 (2024), pp. 7-19

Voir la notice de l'article provenant de la source Math-Net.Ru

Results are presented concerning the main problem of algebraic geometry over partially ordered sets from a computational point of view, namely, the solvability problem for systems of equations over a partial order. This problem is solvable in polynomial time if the directed graph corresponding to the partial order is a adjusted interval digraph, and is NP-complete if the base of the directed graph corresponding to the partial order is a cycle of length at least 4. We also present a result characterizing the possibility of transition from infinite systems of equations over partial orders to finite systems. Algebraic systems with this property are called equationally Noetherian. A partially ordered set is equationally Noetherian if and only if any of its upper and lower cones with base are finitely defined.
Keywords: systems of equations, computational complexity, partially ordered set, poset, equationally Noetherian property, cones, solvability. 
@article{PDM_2024_2_a1,
     author = {A. Yu. Nikitin and N. D. Kudyk},
     title = {Criterion for equational {Noetherianity} and complexity of the solvability problem for systems of equations over partially ordered sets},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {7--19},
     publisher = {mathdoc},
     number = {2},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2024_2_a1/}
}
TY  - JOUR
AU  - A. Yu. Nikitin
AU  - N. D. Kudyk
TI  - Criterion for equational Noetherianity and complexity of the solvability problem for systems of equations over partially ordered sets
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2024
SP  - 7
EP  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2024_2_a1/
LA  - ru
ID  - PDM_2024_2_a1
ER  - 
%0 Journal Article
%A A. Yu. Nikitin
%A N. D. Kudyk
%T Criterion for equational Noetherianity and complexity of the solvability problem for systems of equations over partially ordered sets
%J Prikladnaâ diskretnaâ matematika
%D 2024
%P 7-19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2024_2_a1/
%G ru
%F PDM_2024_2_a1
A. Yu. Nikitin; N. D. Kudyk. Criterion for equational Noetherianity and complexity of the solvability problem for systems of equations over partially ordered sets. Prikladnaâ diskretnaâ matematika, no. 2 (2024), pp. 7-19. http://geodesic.mathdoc.fr/item/PDM_2024_2_a1/