Klasické výsledky

• RE < All_Languages
• L(TS) = L0 = RE
• L(LBA) = CS
• L(NonDetPDA) = L(CFG) = CF
• L(DetPDA) < CF
• L(LIN) < CF
• L(regular_expression) = L(FA) = REG
• L(FIN) < REG

Zažité výsledky (v oblasti gramatik s řízeným přepisováním)

• L0 = L(M,e,ac) = L(P,e,ac) = L(RC,e,ac)
• L2 = CF < L(M) = L(P) < L(M,ac) = L(P,ac) = L(RC,ac) < CS = L1
• L2 = CF < L(FORbidding) < CS = L1
• L2 = CF < L(RC) = L(PERmitting) < L(M,ac) < CS = L1
• L2 = CF < L(M,e) = L(P,e) < RE = L0

• CF(REG) = L(M) < RE

• L(Queue_Grammar) = RE (1983: Kleijn & Rozenberg)

Zažité výsledky (v oblasti L systémů)

• 0L < CS (s FIN, REG, CF se pouze protínají)
• CF < E0L = EP0L < ET0L = EPT0L < CS < RE
• CF < E0L < FE0L(1) = FEP0L(1) = FET0L(1) = FEPT0L(1) = ET0L < CS
• CS = FEP0L(2) = FEP0L
• CS <= FEPT0L(2) = FEPT0L < RE = FE0L(2) = FE0L
  • Porovnejme verze s/bez F:
    • E0L < ET0L versus FE0L(1) = FET0L(1) = ET0L
    • E0L = EP0L versus FEP0L < FE0L

Další výsledky

• L(Kánonická/Nejlevější derivace maticové gramatiky typu 1) =označme= L(1M) = CF < L(M) < RE (proof: G. Paun ??)
• L(2M) = RE
• CF = L(1M) < L(3M)

Nové výsledky

• 2002: L(Maticová gramatika bez kontroly výskytů je pro jednoprvkovou abecedu) = REG
• 2000-2002: v oblasti řízených automatů (Meduna, A., Kolář, D., 2000-2002)
  • RPDA(REG) = CF
  • RPDA(LIN) = RE
• 1995: Meduna, A.
  • GCC(2) = GCC = L1, GCC(2, e) = GCC(e) = L0, tj. vyšší stupeň už nezvýší mocnost GCC.
  • SM: CFG over string monoid (větné formy jsou řetězce nad konečným jazykem nad (N U T))
    • empty_set = SM(0, e) = SM(0)
    • CF = SM(1, e) = SM(1)
    • CS = SM(2)
    • RE = SM(2, e)