Open Problems
Poznámka: Stejné zvyklosti jako na stránce Klasifikace tříd jazyků. ?...buď = nebo < => open_problem!
Otevřené problémy v oblasti gramatik s řízeným přepisováním
- L(M,e) ? L(M); L(P,e) ? L(P)
- L(RC) ? L(RC,e) ? L(M,e)
- L(RC) ? L(M)
- L(FORbidding) ? L(FORbidding,e)
- CF(LIN) ? RE, CS(REG) ? RE
PS: CF(REG) = L(M)
Otevřené problémy v oblasti řízených automatů (Meduna, A., Kolář, D., 2000-2002)
- L(RegulatedDetPDA(REG)) ? L(NonDetPDA)
- L(RegulatedDetPDA(LIN)) ? L(NonDetPDA)/CS/RE
- L(RegulatedLBA(REG)) ? RE
Bláznivé myšlenky/dotazy
Když už tu máme výčet některých otevřených problémů, tak si přisadím svou troškou do mlýna a občas sem hodím i nějakou myšlenku nebo dotaz, tedy jakési moje "otevřené" problémy :-):
- Existuje efektivní automat pro LIN jazyky, který není pouze triviální modifikací PDA podle definice on-turn PDA?
- Jak by se zvýšila síla PDA (případně DetPDA), kdybych zavedl možnost zohlednit celkovou délku řetězce během jeho zpracovávání, případně kdybych dal k dispozici nějaký malý počet celočíselných čitačů? Důraz je kladen na získání větší síly při zachování determinismu (a to pouze v praktických případech, kdy je délka věty konečná a často známá dopředu).
Links to this Page