En informática , una gramática de gráficos lineales (también un sistema de reducción de gráficos de conexión o una gramática de gráficos de puertos [1] ) es una clase de gramática de gráficos en la que los nodos tienen varios puertos conectados entre sí por bordes y los bordes conectan exactamente dos puertos juntos. Las redes de interacción son una subclase especial de gramáticas de gráficos lineales en las que la reescritura es confluente .
Bawden introduce gráficos lineales en el contexto de un compilador para un fragmento del lenguaje de programación Scheme . [2] Bawden y Mairson (1998) describen el diseño de una implementación distribuida en la que el gráfico lineal se distribuye entre muchos nodos informáticos y puede migrar libremente para hacer posibles las reescrituras.