monoide racional


En matemáticas, un monoide racional es un monoide , una estructura algebraica, para la cual cada elemento se puede representar en una "forma normal" que se puede calcular mediante un transductor finito : la multiplicación en tal monoide es "fácil", en el sentido de que se puede describir mediante una función racional .

Considere un monoide M . Considere un par ( A , L ) donde A es un subconjunto finito de M que genera M como un monoide, y L es un lenguaje en A (es decir, un subconjunto del conjunto de todas las cadenas A ). Sea φ el mapa del monoide libre A a M dado al evaluar una cadena como un producto en M . Decimos que L es una sección transversal racional si φ induce una biyección entre L ym _ Decimos que ( A , L ) es una estructura racional para M si además el núcleo de φ , visto como un subconjunto del producto monoide A × A es un conjunto racional .

Un monoide cuasi-racional es aquel para el que L es una relación racional : un monoide racional es aquel para el que también existe una función racional de sección transversal de L. Dado que L es un subconjunto de un monoide libre, el teorema de Kleene se cumple y una función racional es solo una que puede ser instanciada por un transductor de estado finito.

El teorema de Kleene se cumple para monoides racionales: es decir, un subconjunto es un conjunto reconocible si y solo si es un conjunto racional.

Un monoide racional no es necesariamente automático , y viceversa. Sin embargo, un monoide racional es asincrónicamente automático e hiperbólico .

Un monoide racional es un monoide regulador y un monoide cuasi-racional : cada uno de estos implica que es un monoide de Kleene , es decir, un monoide en el que se cumple el teorema de Kleene.