Hierarchie slabě monotonních restartovacích automatů

Abstrakt

Je známo, že slabě monotonní restartovací automaty rozpoznávají právě všechny rostoucí kontextové jazyky. Zavádíme míru slabé monotonie a ukazujeme, že třídy jazyků, které takto dostaneme tvoří vlastní nekonečné hierarchie pro různé typy deterministických i nedeterministických restartovacích automatů bez pomocných symbolů.

Klíčová slova

• Hierarchies
• weakly
• monotone
• restarting
• automata