Aplicación de bases de Gröbner en el problema de alcanzabilidad de estados de sistemas de eventos discretos modelados por redes de Petri

• Guelvis Mata ^[1] ; Abdul Lugo ^[2] ; Germalis Rojas ^[1]
  1. [1] Universidad de Los Andes

     Universidad de Los Andes

     Colombia

     
  2. [2] Universidad Politécnica Territorial del Oeste de Sucre
• Localización: Lecturas matemáticas, ISSN-e 0120-1980, Vol. 37, Nº. 1, 2016, págs. 5-23
• Idioma: español
• Títulos paralelos:
  • Application of Gröbner bases to the problem of reachability of states of discrete-event systems modeled by Petri nets
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    El centro de este trabajo es un enfoque alternativo para el problema de alcanzabilidad de estados en los sistemas de eventos discretos, fundamentado en la teoría de bases de Gröbner. En efecto, en este artículo expresamos procedimientos de bases de Gröbner dirigidos bajo la consideración de monomiales para representar marcaciones, transiciones y dinámica en una red de Petri reiniciable, con el objetivo de resolver el problema de alcanzabilidad de estados. Más precisamente, dado un estado inicial y otro estado arbitrario representados como productos de potencias, y dada una red de Petri representada como un conjunto de polinomios en varias variables, la alcanzabilidad del estado arbitrario desde el estado inicial es una congruencia módulo un ideal polinomial.

  • English

    The focus of this work is an alternative approach to the problem of reachability of states in discrete-event systems, based on the theory of Gröbner bases. Indeed, in this article we express procedures of Gröbner bases routed under the consideration of monomials to represent markings, transitions and dynamics in a reversible Petri net, in order to solve the problem of reachability of states. More precisely, given an initial state and other arbitrary state, represented as products of powers, and given a Petri net represented as a set of polynomials in multiple variables, the reachability of the arbitrary state from the initial state is a congruence modulus a polynomial ideal.