Marcusovy t-contextuální gramatiky a vypouštěcí hierarchie a monotonie restartovacích automatů

Abstrakt

t-kontextuální gramatiky jsou zobecněním Marcusových kontextuálních gramatik, které vkládají t kontextů v každém derivačním kroku. Zde studujeme generativní kapacitu těchto gramatik a odpovdajících tříd restartovacích automatů.

Klíčová slova

• Marcus
• t-contextual
• grammars
• hierarchies
• monotonicity
• restarting
• automata