Un sistema de adición de vectores (VAS) es uno de varios lenguajes de modelado matemático para la descripción de sistemas distribuidos . Los sistemas de adición de vectores fueron introducidos por Richard M. Karp y Raymond E. Miller en 1969, [1] y generalizados a los sistemas de adición 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 .
Definición informal
Un sistema de adición de vectores consta de un conjunto finito de vectores enteros . Un vector inicial se ve como los valores iniciales de múltiples contadores y los vectores del VAS se ven como 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 de la EVA se pueden sumar por componentes, dado que cada vector intermedio tiene valores no negativos. Un sistema de adición de vectores con estados es un sistema de alarma para vehículos 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 .
- Un VASS es un gráfico dirigido finito tal que para algunos .
Transiciones
- Dejar ser un VAS. Dado un vector, el vector se puede alcanzar , en una transición, si y .
- Dejar ser un VASS. Dada una configuración , La configuración se puede alcanzar , en una transición, si y .
Ver también
Referencias
- ^ Karp, Richard M .; Miller, Raymond E. (mayo de 1969). "Esquemas de programas paralelos". Revista de Ciencias de la Computación y Sistemas . 3 (2): 147-195. doi : 10.1016 / S0022-0000 (69) 80011-5 .
- ^ Hopcroft, John E .; Pansiot, Jean-Jacques (1979). "Sobre el problema de la accesibilidad para los sistemas de adición de vectores de 5 dimensiones". Informática Teórica . 8 (2): 135-159. doi : 10.1016 / 0304-3975 (79) 90041-0 . hdl : 1813/6102 .