Jumping Scattered Context Grammars

scattered context grammars, alternative derivation modes, generative power, computational completeness

Koncept skákajících gramatik s rozptýleným kontextem vychází z jejich klasických neskákajících verzí, pracují ovšem odlišně. Derivaci ve skákající gramatice dle pravidla (A1, A2, ..., An) -> (x1, x2, ..., xn) také provedeme tak, že z větné formy současně vymažeme A1, A2, ..., An a vložíme x1, x2, ..., xn, ovšem potenciálně na jiné pozice, než na kterých se vymazané neterminály nacházely. Článek představuje a studuje gramatiky s rozptýleným kontextem pracující v devíti různých módech skákajících derivací. Každý z nich poskytuje výpočetní úplnost, článek proto dokazuje, že rodina rekurzivně spočetných jazyků je charakterizována skákajícími gramatikami s rozptýleným kontextem pracujícími v libovolném z představených derivačních módů. V závěru navíc uvádíme několik otevřených problémů.