Półgrupa transformacji - Transformation semigroup

W Algebra , A półgrupa przetwarzania (lub kompozycja półgrupa ) jest zbiorem transformacji ( funkcje z zestawu do siebie), które są zamknięte w ramach kompozycji funkcji . Jeżeli obejmuje funkcję tożsamości , to monoid , zwany przetwarzania (lub kompozycji ) monoid . To jest półgrupowy odpowiednik grupy permutacji .

Półgrupa transformacji zbioru ma działanie tautologiczne półgrupy na tym zbiorze. Takie działania charakteryzują się wiernością, tj. Jeśli dwa elementy półgrupy mają taką samą akcję, to są równe.

Analogiem twierdzenie cayleya pokazuje, że każdy półgrupa mogą być realizowane jako półgrupa transformacji pewnego zbioru.

W teorii automatów niektórzy autorzy używają terminu półgrupa transformacji w odniesieniu do półgrupy działającej wiernie na zbiorze „stanów” różniącym się od zbioru podstawowego półgrupy. Istnieje zgodność między tymi dwoma pojęciami .

Półgrupy i monoidy transformacyjne

Półgrupa transformacja jest parą ( X , S ), gdzie X jest zbiorem i S jest półgrupa przekształceń X . Tu transformacja z X jest tylko funkcja z podzbioru X do X , niekoniecznie odwracalny, dlatego S jest tylko zestaw przemian X , która jest zamknięta na podstawie składu funkcji . Zbiór wszystkich funkcji cząstkowych na danym zbiorze podstawowym X tworzy regularną półgrupę zwaną półgrupą wszystkich przekształceń częściowych (lub półgrupą transformacji częściowej na X ), zwykle oznaczoną przez . ${\ displaystyle {\ mathcal {PT}} _ {X}}$

Jeśli S zawiera transformację tożsamości X , to nazywa się to monoidem transformacji . Oczywiście każda półgrupa transformacji S określa monoid transformacji M poprzez połączenie S z transformacją tożsamości. Monoid transformacji, którego elementy są odwracalne, jest grupą permutacji .

Zbiór wszystkich przekształceń X jest przekształceniem monoid zwany pełny monoid transformacja (lub półgrupa ) od X . Nazywana jest również symetryczny półgrupa z X i oznaczamy przez T _X . Zatem półgrupa przetwarzania (lub monoid) tylko subsemigroup (lub submonoid ) pełnej transformacji monoid z X .

Jeśli ( X , S ) jest transformacja półgrupa wówczas X mogą być wykonane na działanie półgrupa z S poprzez ocenę:

${\ Displaystyle s \ cdot x = s (x) {\ tekst {za}} s \ w S, x \ w X.}$

Jest to działanie monoidalne, jeśli S jest monoidem transformacji.

Cechą charakterystyczną półgrup transformacyjnych, jako działań, jest to, że są wierne , tj. Jeśli

${\ Displaystyle s \ cdot x = t \ cdot x {\ tekst {dla wszystkich}} x \ w X,}$

wtedy s = t . I odwrotnie, jeśli półgrupa S działa na zbiorze X o T ( s , x ) = a • x wtedy może określić, dla s ∈ S , przekształcenie T _a z X przez

${\ Displaystyle T_ {s} (x) = T (s, x). \,}$

Mapa wysyłania s z t _a to za pomocą wstrzyknięć czy i tylko wtedy, gdy ( X ,  T ) jest wierną, przy czym ten obraz mapy jest transformacja półgrupa izomorficzna S .

Reprezentacja Cayley

W teorii grup , twierdzenie cayleya zapewnia, że każda grupa G jest izomorficzny podgrupie symetryczna grupa o G (traktowane jako zbiór) tak, że G jest grupa permutacji . To twierdzenie uogólnia się bezpośrednio na monoidy: każdy monoid M jest monoidem transformacji swojego podstawowego zbioru, poprzez działanie podane przez mnożenie w lewo (lub w prawo). To działanie jest wierne, ponieważ jeśli ax = bx dla wszystkich x w M , to przyjmując x równe elementowi tożsamości, mamy a = b .

Dla półgrupa S bez (lewej lub prawej) elementu osobistego, weźmiemy X być odnośnego zestawu do monoid odpowiadającego S zrealizować S jako półgrupa transformacji X . W szczególności dowolna półgrupa skończona może być reprezentowana jako podgrupa przekształceń zbioru X z | X | ≤ | S | + 1, a jeśli S jest monoidem, mamy ostrzejsze ograniczenie | X | ≤ | S |, jak w przypadku grup skończonych .

W informatyce

W informatyce reprezentacje Cayleya można zastosować do poprawy asymptotycznej wydajności półgrup poprzez ponowne skojarzenie wielu złożonych mnożeń. Czynność wynikająca z mnożenia z lewej strony powoduje mnożenie z prawej strony i odwrotnie w przypadku czynności określonej przez mnożenie z prawej strony. Pomimo tych samych wyników dla dowolnej półgrupy, skuteczność asymptotyczna będzie się różnić. Dwa przykłady użytecznych monoidów transformacji uzyskanych w wyniku mnożenia w lewo to funkcjonalna wariacja struktury danych listy różnic i monadyczna transformacja Codensity (reprezentacja monady Cayleya , która jest monoidem w określonej kategorii funktorów monoidalnych ).

Monoid transformacyjny automatu

Niech M będzie deterministyczny automat z przestrzeni stanów S i alfabetu A . Słowa wolnej monoid A ^* indukować przemiany S dając początek morfizmu monoid od A ^* do pełnej przemiany monoid T _S . Obraz ten morfizmu jest półgrupa transformacja M .

Na język regularny The składniowym monoid jest izomorficzna z monoid transformacji z minimalnym automatu języka.

Zobacz też

• Semiautomaton
• Teoria Krohna-Rhodesa
• Półgrupa odwrotna symetryczna
• Zestaw dwuporządkowy
• Specjalne zajęcia półgrup
• Pierścień kompozycji

Bibliografia

• Clifford, AH; Preston, GB (1961). Algebraiczna teoria półgrup. Vol. Ja . Ankiety matematyczne. 7 . Providence, RI: American Mathematical Society . ISBN   978-0-8218-0272-4 . Zbl   0111.03403 .
• Howie, John M. (1995). Podstawy teorii półgrupy . Monografie Londyńskiego Towarzystwa Matematycznego. Nowa seria. 12 . Oxford: Clarendon Press . ISBN   978-0-19-851194-6 . Zbl   0835.20077 .
• Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev (2000), Monoids, Acts and Categories: with Applications to Wreath Products and Graphs , Expositions in Mathematics 29 , Walter de Gruyter, Berlin, ISBN   978-3-11-015248-7 .