Rationell monoid

I matematik är en rationell monoid en monoid , en algebraisk struktur, för vilken varje element kan representeras i en "normal form" som kan beräknas av en finit omvandlare : multiplikation i en sådan monoid är "lätt", i den meningen att det kan beskrivas med en rationell funktion .

Definition

Betrakta en monoid M . Betrakta ett par ( A , L ) där A är en finit delmängd av M som genererar M som en monoid, och L är ett språk på A (det vill säga en delmängd av mängden av alla strängar A ^∗ ). Låt φ vara kartan från den fria monoiden A ^∗ till M som ges genom att utvärdera en sträng som en produkt i M . Vi säger att L är ett rationellt tvärsnitt om φ inducerar en bijektion mellan L och M . Vi säger att ( A , L ) är en rationell struktur för M om dessutom kärnan av φ , sedd som en delmängd av produktmonoiden A ^∗ × A ^∗ är en rationell mängd .

En kvasirationell monoid är en för vilken L är en rationell relation : en rationell monoid är en för vilken det också finns ett rationellt funktionstvärsnitt av L . Eftersom L är en delmängd av en fri monoid, gäller Kleenes teorem och en rationell funktion är bara en funktion som kan instansieras av en finita tillståndsgivare.

Exempel

En finit monoid är rationell.
En grupp är en rationell monoid om och bara om den är ändlig.
En ändligt genererad fri monoid är rationell.
Monoiden M4 genererad av mängden {0, e , a , b , x , y } föremål för relationer där e är identiteten, 0 är ett absorberande element , var och en av a och b pendlar med var och en av x och y och axe = bx , ay = by = bby , xx = xy = yx = yy = 0 är rationell men inte automatisk.
Fibonacci- monoiden , kvoten av den fria monoiden på två generatorer { a , b } ^∗ genom kongruensen aab = bba .

Greens relationer

De grönas relationer för en rationell monoid uppfyller D = J .

Egenskaper

Kleenes teorem gäller för rationella monoider: det vill säga en delmängd är en igenkännbar mängd om och bara om den är en rationell mängd.

En rationell monoid är inte nödvändigtvis automatisk , och vice versa. En rationell monoid är emellertid asynkront automatisk och hyperbolisk.

En rationell monoid är en regulatormonoid och en kvasirationell monoid : var och en av dessa antyder att det är en Kleene monoid , det vill säga en monoid i vilken Kleenes sats gäller.

Fichtner, Ina; Mathissen, Christian (2002). "Rationella transformationer och ett Kleene-teorem för maktserier över rationella monoider". I Gomes, Gracinda MS (red.). Semigrupper, algoritmer, automater och språk. Proceedings of workshops som hölls vid International Centre of Mathematics, CIM, Coimbra, Portugal, maj, juni och juli 2001 . Singapore: World Scientific. s. 94–111. Zbl 1350.68191 .
Hoffmann, Michael; Kuske, Dietrich; Otto, Friedrich; Thomas, Richard M. (2002). "Några släktingar till automatiska och hyperboliska grupper". I Gomes, Gracinda MS (red.). Semigrupper, algoritmer, automater och språk. Proceedings of workshops som hölls vid International Centre of Mathematics, CIM, Coimbra, Portugal, maj, juni och juli 2001 . Singapore: World Scientific. s. 379–406. Zbl 1031.20047 .
Kuich, Werner (2011). "Algebraiska system och pushdown-automater". I Kuich, Werner (red.). Algebraiska grunder inom datavetenskap. Uppsatser tillägnade Symeon Bozapalidis med anledning av hans pensionering . Föreläsningsanteckningar i datavetenskap. Vol. 7020. Berlin: Springer-Verlag . s. 228–256. ISBN 978-3-642-24896-2 . Zbl 1251.68135 .
Pelletier, Maryse (1990). "Boolesk stängning och entydighet av rationella uppsättningar". I Paterson, Michael S. (red.). Automater, språk och programmering, Proc. 17:e Int. Colloq., Warwick/GB 1990 . Föreläsningsanteckningar i datavetenskap. Vol. 443. s. 512–525. Zbl 0765.68075 .
Sakarovitch, Jacques (september 1987). "Enkla multiplikationer I. The realm of Kleenes theorem" . Information och beräkning . 74 (3): 173–197. doi : 10.1016/0890-5401(87)90020-4 . Zbl 0642.20043 .