Jumping Grammars

Modified grammars; discontinuous rewriting; generative power; jumping finite automata; semilinearity; finite index.

Článek zavádí a studuje skákající gramatiky, které představují gramatický protějšek nedávno zavedených skákajících automatů. Způsob práce těchto gramatiky odpovídá klasickým gramatikám až na způsob aplikace pravidel, kdy mohou při přepsání větné formy přeskočit oběma směry. Skákající gramatika tedy přepisuje řetězc z podle pravidla x -> y tak, že vybere libovolný výskyt x v z, smaže jej a vloží y na libovolnou pozici v přepisované větné formě, takže vložení může být provedeno na jinou pozici než pozici přepsaného x. Článek se soustředí na zkoumání generativní síly skákajících gramatik. Porovnává jejich sílu se skákajícími automaty a klasickými gramatikami.  Především se zaměřuje na různé bezkontextové varianty skákajících gramatik jako například regulární, pravě-lineární, lineární a bezkontextové s konečným indexem. Navíc studuje semilinearitu bezkontextovýh, kontextových a monotónních skákajících gramatik. Dokazuje také, že obecné skákajících gramatiky charakterizují třídu rekuzivně spočetných jazyků. V závěru článek formuluje několik otevřených problémů a navrhuje oblasti budoucího studia.