Aperiodisk halvgrupp
I matematik är en aperiodisk halvgrupp en halvgrupp S så att varje element x ∈ S är aperiodiskt, det vill säga för varje x finns det ett positivt heltal n så att x n = x n + 1 . En aperiodisk monoid är en aperiodisk halvgrupp som är en monoid .
Finita aperiodiska semigrupper
En finit halvgrupp är aperiodisk om och endast om den inte innehåller några icke-triviala undergrupper , så en synonym som används (endast?) i sådana sammanhang är gruppfri halvgrupp . När det gäller Greens relationer är en finit halvgrupp aperiodisk om och endast om dess H -relation är trivial. Dessa två karakteriseringar sträcker sig till gruppbundna semigrupper . [ citat behövs ]
Ett hyllat resultat av algebraisk automatteori tack vare Marcel-Paul Schützenberger hävdar att ett språk är stjärnfritt om och bara om dess syntaktiska monoid är ändlig och aperiodisk.
En konsekvens av Krohn–Rhodes-satsen är att varje ändlig aperiodisk monoid delar upp en kransprodukt av kopior av treelementet flip-flop monoid , bestående av ett identitetselement och två rätta nollor. Den tvåsidiga Krohn–Rhodes-satsen karakteriserar alternativt finita aperiodiska monoider som divisorer av itererade blockprodukter av kopior av tvåelementets semigitter .
Se även
- Straubing, Howard (1994). Finita automater, formell logik och kretskomplexitet . Framsteg i teoretisk datavetenskap. Basel: Birkhäuser. ISBN 3-7643-3719-2 . Zbl 0816.68086 .