En matemáticas, un monoide racional es un monoide , una estructura algebraica, para la cual cada elemento puede ser representado en una "forma normal" que puede ser calculada por 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 .
Definición
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 ∗ ). Dejar que φ es el mapa de la libre monoid A * a M determinado mediante la evaluación de una cadena como un producto en M . Decimos que L es un corte 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 .
A monoid cuasi-racional es uno para el que L es una relación racional : a monoid racional es uno para el que hay también una función racional 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.
Ejemplos de
- Un monoide finito es racional.
- Un grupo es un monoide racional si y solo si es finito.
- Un monoide libre finamente generado es racional.
- El monoid M4 generada por el conjunto {0, e , un , b , x , y } sujetos a relaciones en las que e es la identidad, 0 es un elemento absorbente , cada uno de unos y b conmuta con cada uno de x y y y hacha = bx , ay = by = bby , xx = xy = yx = yy = 0 es racional pero no automático.
- El Fibonacci monoid , el cociente de la monoide libre en dos generadores { a , b } * por la congruencia AAB = bba .
Relaciones de Green
La relación de Green para un monoide racional satisfacer D = J . [1]
Propiedades
El teorema de Kleene es válido para los 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.
Referencias
- ^ Sakarovitch (1987)
- Fichtner, Ina; Mathissen, Christian (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 los 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 .
- Hoffmann, Michael; Kuske, Dietrich; Otto, Friedrich; 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 los 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 Symeon Bozapalidis con motivo de su jubilación . Apuntes de conferencias en informática. 7020 . Berlín: Springer-Verlag . págs. 228-256. ISBN 978-3-642-24896-2. Zbl 1251.68135 .
- Pelletier, Maryse (1990). "Cierre booleano y sin ambigüedad de conjuntos racionales". En Paterson, Michael S. (ed.). Autómatas, lenguajes y programación, Proc. 17 ° Int. Coloq., Warwick / GB 1990 . Apuntes de conferencias en informática. 443 . págs. 512–525. Zbl 0765.68075 .
- Sakarovitch, Jacques (septiembre de 1987). "Multiplicaciones fáciles I. El reino del teorema de Kleene". Información y Computación . 74 (3): 173-197. doi : 10.1016 / 0890-5401 (87) 90020-4 . Zbl 0642.20043 .