En informática , una máquina de estados finitos comunicante es una máquina de estados finitos etiquetada con operaciones de "recepción" y "envío" sobre algún alfabeto de canales. Fueron introducidos por Brand y Zafiropulo, [1] y pueden usarse como modelo de procesos concurrentes como las redes de Petri . Las máquinas de estados finitos de comunicación se utilizan con frecuencia para modelar un protocolo de comunicación, ya que permiten detectar errores importantes en el diseño del protocolo, incluidos los límites, los puntos muertos y las recepciones no especificadas. [2]
La ventaja de comunicar máquinas de estados finitos es que permiten decidir muchas propiedades en los protocolos de comunicación, más allá del nivel de solo detectar tales propiedades. Esta ventaja descarta la necesidad de asistencia humana o restricción en general. [1]
La comunicación de máquinas de estados finitos puede ser más poderosa que las máquinas de estados finitos en situaciones en las que el retardo de propagación no es despreciable (de modo que varios mensajes pueden estar en tránsito al mismo tiempo) y en situaciones en las que es natural describir las partes del protocolo y el medio de comunicación. como entidades separadas. [1]
Comunicación de la máquina de estado jerárquica
Las máquinas de estado jerárquicas son máquinas de estados finitos cuyos estados mismos pueden ser otras máquinas. Dado que una máquina de estados finitos comunicante se caracteriza por la concurrencia, el rasgo más notable en una máquina de estados jerárquica comunicante es la coexistencia de la jerarquía y la concurrencia. Esto se ha considerado muy adecuado ya que significa una interacción más fuerte dentro de la máquina.
Sin embargo, se demostró que la coexistencia de la jerarquía y la concurrencia cuesta intrínsecamente la inclusión del lenguaje, la equivalencia del lenguaje y toda la universalidad. [3]
Definición
Protocolo
Para un entero positivo arbitrario , un protocolo [1] : 3 con proceso (s) es un cuádruple con:
- , una secuencia de conjuntos finitos disjuntos. Cada conjunto se utiliza para representar un proceso, y cada elemento de representa un posible estado del -th proceso.
- (con ), una secuencia que representa el estado inicial de cada proceso.
- , una secuencia finita de conjuntos finitos disjuntos de modo que cada conjunto representa los posibles mensajes que se pueden enviar desde el proceso procesar . Si, luego esta vacio.
- es una secuencia de funciones de transición. Cada función modela la transición que se puede realizar emitiendo o recibiendo cualquier mensaje. Con respecto al proceso, el símbolo se utiliza para anotar un mensaje que se puede recibir y un mensaje que se puede enviar.
Estado global
Un estado global es un par dónde
- es una colección ordenada de estados de modo que cada representa un estado del -th proceso.
- es un matriz tal que cada es una subsecuencia de .
El estado global inicial es un par dónde
- se define como un matriz tal que para todos , es igual a la palabra vacía, .
Paso
Hay dos tipos de pasos, pasos en los que se reciben los mensajes y pasos en los que se envían los mensajes.
Un paso en el que el recibir un mensaje enviado previamente por el -th proceso es un par de la forma Cuándo , con . Del mismo modo, un par en el que un mensaje es enviado por el-th proceso al -th uno es un par de la forma Cuándo
Correr
Una corrida es una secuencia de estados globales tal que un paso relaciona un estado con el siguiente, y tal que el primer estado es inicial.
Se dice que un estado global es accesible si existe una ejecución que pasa por este estado.
Problemas
Se ha demostrado con la introducción del concepto mismo que cuando dos máquinas de estados finitos se comunican con un solo tipo de mensajes, se pueden decidir e identificar la limitación, los interbloqueos y el estado de recepción no especificado, mientras que este no es el caso cuando las máquinas se comunican con dos. o más tipos de mensajes. Más tarde, se demostró además que cuando solo una máquina de estados finitos se comunica con un solo tipo de mensaje mientras la comunicación de su socio no está restringida, aún podemos decidir e identificar los límites, los puntos muertos y el estado de recepción no especificado. [2]
Se ha demostrado además que cuando la relación de prioridad de mensaje está vacía, la limitación, los interbloqueos y el estado de recepción no especificado pueden decidirse incluso bajo la condición en la que hay dos o más tipos de mensajes en la comunicación entre máquinas de estados finitos. [4]
Los límites, los puntos muertos y el estado de recepción no especificado son todos decidibles en tiempo polinomial (lo que significa que un problema particular puede resolverse en una cantidad de tiempo manejable, no infinita) ya que los problemas de decisión con respecto a ellos son espacios de registro no deterministas completos. [2]
Extensiones
Algunas extensiones consideradas son:
- tener una notación para indicar que algunos estados pueden no recibir ningún mensaje,
- los mensajes se reciben en diferentes órdenes, como FILO,
- algunos mensajes pueden perderse,
Sistema de canales
Un sistema de canales es esencialmente una versión de la comunicación de la máquina de estados finitos en la que la máquina no se divide en procesos distintos. Por lo tanto, hay un solo estado de estado y no hay restricciones sobre qué sistema puede leer / escribir en cualquier canal.
Formalmente, dado un protocolo , su sistema de canales asociado es , dónde es el conjunto de y de .
Referencias
- ^ a b c d D. Brand y P. Zafiropulo. Sobre la comunicación de máquinas de estados finitos. Revista de la ACM, 30 (2): 323-342, 1983.
- ↑ a b c Rosier, Louis E; Gouda, Mohamed G. Decidir el progreso de una clase de máquinas comunicantes de estados finitos. Austin: Universidad de Texas en Austin, 1983.
- ^ Alur, Rajeev; Kannan, Sampath; Yannakakis, Mihalis. "Comunicando máquinas de estado jerárquicas", Autómatas, Lenguajes y Programación. Praga: ICALP, 1999
- ^ Gouda, Mohamed G; Rosier, Louis E. "Comunicando máquinas de estados finitos con canales prioritarios", Autómatas, Lenguajes y Programación. Amberes: ICALP, 1984