Quels algorithmes existent pour résoudre les systèmes linéaires de nombres naturels?

Je regarde le problème suivant:

Étant donné les vecteurs à dimensions des nombres naturels v 1 , … , v m et un vecteur d'entrée u , u est-il une combinaison linéaire des v i avec des coefficients de nombres naturels?$n$$v_1, \ldots, v_m$$u$$u$$v_i$

c'est-à-dire qu'il y a où u = t 1 v 1 + ⋯ + t m v m ?$t_1, \ldots, t_m \in \mathbb{N}$$u = t_1 v_1 + \dots + t_m v_m$

Évidemment, la version en nombre réel de ce problème peut être résolue en utilisant l'élimination gaussienne. Je me demande, la version entière de ce problème a-t-elle été étudiée? Quels algorithmes existent pour le résoudre?

Notez que cela utilise des nombres naturels, mais pas l'arithmétique modulaire, donc c'est quelque peu distinct du théorème des restes chinois et des systèmes comme ça. En outre, cela semble lié aux équations diophantiennes, mais je me demande ce qui a été fait dans le cas où seuls les entiers non négatifs sont pris en compte? Cela rappelle également un problème de sous-ensemble multidimensionnel, généralisé pour nous permettre de prendre un nombre arbitraire de copies de chaque vecteur. Il semble également lié au test pour savoir si est un élément du réseau généré par v 1 , … , v m , sauf que nous n'autorisons ici que des combinaisons linéaires avec des coefficients non négatifs.$u$$v_1,\dots,v_m$

Pour toute personne intéressée, cela est motivé par la recherche d'un vecteur Parikh dans un ensemble linéaire, comme dans le théorème de Parikh .

En particulier, je suis intéressé par un algorithme qui pourrait résoudre le problème en utilisant uniquement des opérations de nombres naturels, en évitant d'entrer dans les nombres réels / à virgule flottante.

$S = \{s_1,\ldots,s_n\}, T$$S$$T$$v_1,\ldots,v_{2n},u$$1 \leq i \leq n$$v_i$$v_{i,i} = 1$$v_{i,n+1} = s_i$$v_{n+i}$$v_{n+i,i} = 1$$u=1,\ldots,1,T$$v_1,\ldots,v_{2n}$$1,\ldots,1,\ast$$v_i,v_{n+i}$$S$