Racionální monoid - Rational monoid
V matematice, a racionální monoid je monoidní, algebraická struktura, pro kterou může být každý prvek reprezentován v „normální formě“, kterou lze vypočítat pomocí a konečný převodník: multiplikace v takovém monoidu je „snadná“ v tom smyslu, že ji lze popsat pomocí a racionální funkce.
Definice
Zvažte monoid M. Zvažte pár (A,L) kde A je konečná podmnožina M který generuje M jako monoid a L je jazyk na A (tj. podmnožina sady všech řetězců A∗). Nechat φ být mapou z volný monoid A∗ na M dán hodnocením řetězce jako produktu v M. Říkáme to L je racionální průřez -li φ vyvolává bijekci mezi L a M. Říkáme, že (A,L) je racionální struktura pro M pokud navíc jádro z φ, považována za podmnožinu produktu monoid A∗×A∗ je racionální množina.
A kvazi-racionální monoid je ten, pro který L je racionální vztah: a racionální monoid je ten, pro který existuje také racionální funkce průřez L. Od té doby L je podmnožinou volného monoidu, Kleeneova věta drží a racionální funkce je jen ta, kterou lze vytvořit pomocí převodníku konečného stavu.
Příklady
- Konečný monoid je racionální.
- A skupina je racionální monoid, právě když je konečný.
- Konečně vygenerovaný bezplatný monoid je racionální.
- Monoid M4 generovaný množinou {0,E, A,b, X,y} s výhradou vztahů, ve kterých E je identita, 0 je absorpční prvek, každý z A a b dojíždí s každým z X a y a sekera = bx, ano = podle = bby, xx = xy = yx = yy = 0 je racionální, ale ne automatické.
- The Fibonacciho monoid, kvocient volného monoidu na dvou generátorech {A,b}∗ shodou aab = bba.
Greenovy vztahy
The Greenovy vztahy pro racionální uspokojení monoidů D = J.[1]
Vlastnosti
Kleeneova věta platí pro racionální monoidy: to znamená, že podmnožina je rozpoznatelná množina právě tehdy, pokud jde o racionální množinu.
Racionální monoid nemusí být nutně automatický a naopak. Racionální monoid je však asynchronně automatický a hyperbolický.
Racionální monoid je a regulátor monoid a a kvazi-racionální monoid: každý z nich znamená, že se jedná o Kleene monoid, tj. Monoid, ve kterém platí Kleeneova věta.
Reference
- ^ Sakarovitch (1987)
- Fichtner, Ina; Mathissen, Christian (2002). "Racionální transformace a Kleeneova věta pro energetické řady nad racionálními monoidy". V Gomes, Gracinda M. S. (ed.). Poloskupiny, algoritmy, automaty a jazyky. Sborník workshopů konaných v Mezinárodním středisku matematiky, CIM, Coimbra, Portugalsko, květen, červen a červenec 2001. Singapur: World Scientific. str. 94–111. Zbl 1350.68191.
- Hoffmann, Michael; Kuske, Dietrich; Otto, Friedrich; Thomas, Richard M. (2002). "Někteří příbuzní automatických a hyperbolických skupin". V Gomes, Gracinda M. S. (ed.). Poloskupiny, algoritmy, automaty a jazyky. Sborník workshopů konaných v Mezinárodním středisku matematiky, CIM, Coimbra, Portugalsko, květen, červen a červenec 2001. Singapur: World Scientific. 379–406. Zbl 1031.20047.
- Kuich, Werner (2011). "Algebraické systémy a posunovací automaty". V Kuich, Werner (ed.). Algebraické základy v informatice. Eseje věnované Symeonovi Bozapalidisovi u příležitosti jeho odchodu do důchodu. Přednášky z informatiky. 7020. Berlín: Springer-Verlag. str. 228–256. ISBN 978-3-642-24896-2. Zbl 1251.68135.
- Pelletier, Maryse (1990). Msgstr "Booleovské uzavření a jednoznačnost racionálních množin". V Paterson, Michael S. (ed.). Automaty, jazyky a programování, Proc. 17. Int. Colloq., Warwick / GB 1990. Přednášky z informatiky. 443. str. 512–525. Zbl 0765.68075.
- Sakarovitch, Jacques (září 1987). „Snadné násobení I. říše Kleeneovy věty“. Informace a výpočet. 74 (3): 173–197. doi:10.1016/0890-5401(87)90020-4. Zbl 0642.20043.
Další čtení
![]() | Tato část je prázdná. Můžete pomoci přidávat k tomu. (Srpna 2014) |