Sistema de suma de vectores

Lenguaje de modelado matemático

Un sistema de suma de vectores ( VAS ) es uno de varios lenguajes de modelado matemático para la descripción de sistemas distribuidos . Los sistemas de suma de vectores fueron introducidos por Richard M. Karp y Raymond E. Miller en 1969, ^[1] y generalizados a sistemas de suma de vectores con estados ( VASS ) por John E. Hopcroft y Jean-Jacques Pansiot en 1979. ^[2] Ambos VAS y VASS son equivalentes en muchos aspectos a las redes de Petri introducidas anteriormente por Carl Adam Petri .

Ejemplo de suma de vectores con estados. En este VASS, por ejemplo, se puede llegar a q(1,2) desde p(0,0), pero no se puede llegar a q(0,0) desde p(0,0).

La accesibilidad en los sistemas de suma de vectores es completa de Ackermann (y, por tanto, no elemental ). ^{[3] [4]}

Definición informal

Un sistema de suma de vectores consta de un conjunto finito de vectores enteros . Un vector inicial se considera los valores iniciales de varios contadores y los vectores del VAS se consideran actualizaciones. Es posible que estos contadores nunca caigan por debajo de cero. Más precisamente, dado un vector inicial con valores no negativos, los vectores del VAS se pueden sumar componentes, dado que cada vector intermedio tiene valores no negativos. Un sistema de suma de vectores con estados es un VAS equipado con estados de control. Más precisamente, es un gráfico dirigido finito con arcos etiquetados por vectores enteros . VASS tiene la misma restricción de que los valores del contador nunca deben caer por debajo de cero.

Definiciones formales y terminología básica.

• Un VAS es un conjunto finito para algunos . ${\displaystyle V\subseteq \mathbb {Z} ^{d}}$ ${\displaystyle d\geq 1}$
• Un VASS es un gráfico dirigido finito tal que para algunos . ${\displaystyle (Q,T)}$ ${\displaystyle T\subseteq Q\times \mathbb {Z} ^{d}\times Q}$ ${\displaystyle d>0}$

Transiciones

• Sea un VAS. Dado un vector , se puede alcanzar el vector , en una transición, si y . ${\displaystyle V\subseteq \mathbb {Z} ^{d}}$ ${\displaystyle u\in \mathbb {N} ^{d}}$ ${\displaystyle u+v}$ ${\displaystyle v\in V}$ ${\displaystyle u+v\in \mathbb {N} ^{d}}$
• Sea un VASS. Dada una configuración , se puede alcanzar la configuración , en una transición, si y . ${\displaystyle (Q,T)}$ ${\displaystyle (p,u)\in Q\times \mathbb {N} ^{d}}$ ${\displaystyle (q,u+v)}$ ${\displaystyle (p,v,q)\in T}$ ${\displaystyle u+v\in \mathbb {N} ^{d}}$

Ver también

• Red de Petri
• Máquina de estados finitos
• Máquina de estados finitos comunicante
• Redes de procesos de Kahn
• Cálculo de procesos
• modelo de actor
• Teoría de la traza

Referencias

1. Karp, Richard M.; Miller, Raymond E. (mayo de 1969). "Esquemas de programas paralelos". Revista de Ciencias de la Computación y de Sistemas . 3 (2): 147–195. doi : 10.1016/S0022-0000(69)80011-5 .
2. Hopcroft, John E.; Pansiot, Jean-Jacques (1979). "Sobre el problema de accesibilidad de sistemas de suma de vectores de 5 dimensiones". Informática Teórica . 8 (2): 135-159. doi :10.1016/0304-3975(79)90041-0. hdl : 1813/6102 .
3. Czerwiński, Wojciech; Orlikowski, Lukasz (2021). La accesibilidad en los sistemas de suma de vectores es completa según Ackermann . 2021 62º Simposio Anual del IEEE sobre Fundamentos de la Informática (FOCS). arXiv : 2104.13866 .
4. Leroux, Jérôme (2021). "El problema de accesibilidad de las redes de Petri no es primitivo recursivo" . 2021 62º Simposio Anual del IEEE sobre Fundamentos de la Informática (FOCS). arXiv : 2104.12695 .