Racjonalny monoid - Rational monoid
W matematyce wymierny monoid jest monoidem , strukturą algebraiczną, w której każdy element może być reprezentowany w „postaci normalnej”, która może być obliczona przez skończony przetwornik : mnożenie w takim monoidzie jest „łatwe”, w tym sensie, że można go opisać funkcją wymierną .
Definicja
Rozważmy monoid M . Rozważmy parę ( A , L ), gdzie A jest skończonym podzbiorem M generującym M jako monoid, a L jest językiem na A (to jest podzbiorem zbioru wszystkich łańcuchów A ∗ ). Niech φ będzie odwzorowaniem wolnego monoidu A ∗ na M, danym przez obliczenie łańcucha jako iloczynu w M . Mówimy, że L jest przekrojem wymiernym, jeśli φ indukuje bijekcję między L i M . Mówimy, że ( , L ) jest racjonalne struktury dla M jeśli dodatkowo jądra z cp , widziane jako podzbiór produktu monoid * x * jest racjonalne zestaw .
Quasi racjonalne monoid to taka, dla której L jest racjonalny stosunek : a racjonalne monoid to taka, dla której istnieje również funkcja wymierna przekrój L . Ponieważ L jest podzbiorem wolnego monoidu, twierdzenie Kleene'a jest prawdziwe, a funkcja wymierna to tylko taka, która może być skonkretyzowana przez skończony przetwornik stanu.
Przykłady
- Skończony monoid jest racjonalny.
- Grupa jest racjonalne monoid wtedy i tylko wtedy, gdy jest skończony.
- Skończenie wygenerowany wolny monoid jest racjonalny.
- Monoid M4 generowane przez zbioru {0, e , , b , x , y } zastrzeżeniem stosunkach, w którym e jest tożsamość 0 jest elementem absorbującym , każdy z a i b dojazdy z każdym z X i Y i ax = bx , ay = by = bby , xx = xy = yx = yy = 0 jest racjonalne, ale nie automatyczne.
- Fibonacciego monoid iloraz wolnej monoid dwóch generatorów { , b } * o zbieżność AAB = BBA .
Relacje Greena
The Relacje Greena dla racjonalnego monoid usatysfakcjonować D = J .
Nieruchomości
Twierdzenie Kleene'a obowiązuje dla wymiernych monoidów: to znaczy, że podzbiór jest zbiorem rozpoznawalnym wtedy i tylko wtedy, gdy jest zbiorem wymiernym.
Racjonalny monoid niekoniecznie jest automatyczny i na odwrót. Jednak racjonalny monoid jest asynchronicznie automatyczny i hiperboliczny .
Wymierny monoid jest monoidem regulatorowym i quasi-racjonalnym monoidem : każdy z nich implikuje, że jest monoidem Kleene'a , to znaczy monoidem, w którym zachodzi twierdzenie Kleene'a.
Bibliografia
- Fichtnera, Inę; Mathissen, Chrześcijanin (2002). „Przekształcenia racjonalne i twierdzenie Kleene dla szeregów potęgowych nad racjonalnymi monoidami”. W Gomes, Gracinda MS (red.). Półgrupy, algorytmy, automaty i języki. Materiały z warsztatów przeprowadzonych w Międzynarodowym Centrum Matematyki, CIM, Coimbra, Portugalia, maj, czerwiec i lipiec 2001 . Singapur: Światowy Naukowy. s. 94-111. Zbl 1350.68191 .
- Hoffmann, Michael; Kuske, Dietrich; Ottona, Fryderyka; Thomas, Richard M. (2002). „Niektórzy krewni grup automatycznych i hiperbolicznych”. W Gomes, Gracinda MS (red.). Półgrupy, algorytmy, automaty i języki. Materiały z warsztatów przeprowadzonych w Międzynarodowym Centrum Matematyki, CIM, Coimbra, Portugalia, maj, czerwiec i lipiec 2001 . Singapur: Światowy Naukowy. s. 379-406. Zbl 1031.20047 .
- Kuich, Werner (2011). „Systemy algebraiczne i automaty pushdown”. W Kuich, Werner (red.). Podstawy algebraiczne w informatyce. Eseje dedykowane Symeonowi Bozapalidisowi z okazji jego przejścia na emeryturę . Notatki z wykładów z informatyki. 7020 . Berlin: Springer-Verlag . s. 228-256. Numer ISBN 978-3-642-24896-2. Zbl 1251.68135 .
- Pelletiera, Maryse (1990). „Zamknięcie logiczne i jednoznaczność zbiorów wymiernych”. W Paterson, Michael S. (red.). Automaty, języki i programowanie, Proc. 17. Międzyn. Colloq., Warwick/GB 1990 . Notatki z wykładów z informatyki. 443 . s. 512-525. Zbl 0765.68075 .
- Sakarowicz, Jacques (wrzesień 1987). „Łatwe mnożenia I. Dziedzina twierdzenia Kleene” . Informacje i obliczenia . 74 (3): 173-197. doi : 10.1016/0890-5401(87)90020-4 . Zbl 0642.20043 .