Publikace na Matematicko-fyzikální fakulta |
2006
Abstrakt
Prezentujeme novou nekonečnou hierarchii tříd semilineárních jazyků, která je získána postupným uvolňováním slovosledných omezení u závislostních gramatik. Tato hierarchie začíná bezkontextovými jazyky.
Již dříve jsme ukázali, že jde o třídy jazyků rozpoznatelné v polynomiálním čase.