Publikace na Matematicko-fyzikální fakulta |
2005
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ů.