En matemáticas, un monoide racional es un monoide , una estructura algebraica, para la cual cada elemento puede representarse en una "forma normal" que puede calcularse mediante un transductor finito : la multiplicación en un monoide de este tipo es "fácil", en el sentido de que se puede describir mediante una función racional .
Definición
Considere un monoide M . Considere un par ( A , L ) donde A es un subconjunto finito de M que genera M como 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 cuerda como producto en M . Decimos que L es una sección transversal racional si φ induce una biyección entre L y M. 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 cual L es una relación racional : un monoide racional es aquel para el cual también existe una sección transversal de función racional de L. Dado que L es un subconjunto de un monoide libre, el teorema de Kleene se cumple y una función racional es aquella que puede ser instanciada por un transductor de estado finito.
Ejemplos
- Un monoide finito es racional.
- Un grupo es un monoide racional si y sólo si es finito.
- Un monoide libre generado finitamente es racional.
- El monoide M4 generado por el conjunto {0, e , a , b , x , y } sujeto a relaciones en las que e es la identidad, 0 es un elemento absorbente , cada uno de a y b conmuta con cada uno de x , y y ax = bx , ay = by = bby , xx = xy = yx = yy = 0 es racional pero no automático.
- El monoide de Fibonacci , el cociente del monoide libre en dos generadores { a , b } ∗ por la congruencia aab = bba .
Las relaciones de Green
Las relaciones de Green para un monoide racional satisfacen D = J. [1]
Propiedades
El teorema de Kleene es válido para monoides racionales: es decir, un subconjunto es un conjunto reconocible si y sólo 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 ellos implica que es un monoide de Kleene , es decir, un monoide en el que se cumple el teorema de Kleene.
Referencias
- Fichtner, Ina; Mathissen, cristiano (2002). "Transformaciones racionales y un teorema de Kleene para series de potencias sobre monoides racionales". En Gomes, Gracinda MS (ed.). Semigrupos, algoritmos, autómatas y lenguajes. Actas de talleres realizados en el Centro Internacional de Matemáticas, CIM, Coimbra, Portugal, mayo, junio y julio de 2001 . Singapur: World Scientific. págs. 94-111. Zbl 1350.68191.
- Hoffman, Michael; Kuske, Dietrich; Otto, Federico; Thomas, Richard M. (2002). "Algunos familiares de grupos automáticos e hiperbólicos". En Gomes, Gracinda MS (ed.). Semigrupos, algoritmos, autómatas y lenguajes. Actas de talleres realizados en el Centro Internacional de Matemáticas, CIM, Coimbra, Portugal, mayo, junio y julio de 2001 . Singapur: World Scientific. págs. 379–406. Zbl 1031.20047.
- Kuich, Werner (2011). "Sistemas algebraicos y autómatas pushdown". En Kuich, Werner (ed.). Fundamentos algebraicos en informática. Ensayos dedicados a Simeón Bozapalidis con motivo de su jubilación . Apuntes de conferencias sobre informática. vol. 7020. Berlín: Springer-Verlag . págs. 228–256. ISBN 978-3-642-24896-2. Zbl 1251.68135.
- Pelletier, Maryse (1990). "Cierre booleano e inequívoco de conjuntos racionales". En Paterson, Michael S. (ed.). Autómatas, lenguajes y programación, Proc. 17° Int. Coloq., Warwick/GB 1990 . Apuntes de conferencias sobre informática. vol. 443, págs. 512–525. Zbl 0765.68075.
- Sakarovitch, Jacques (septiembre de 1987). "Multiplicaciones fáciles I. El ámbito del teorema de Kleene". Información y Computación . 74 (3): 173–197. doi : 10.1016/0890-5401(87)90020-4 . Zbl 0642.20043.
