Publikace na Matematicko-fyzikální fakulta |
2005
Abstrakt
Je známo, že používání pomocných symbolů nezvyšuje rozpoznávací schopnosti deterministických jednosměrných (pravě-)monotonních automatů. Ukazujeme, že to samé platí pro deterministické dvou-cestné restartovací automaty, které jsou pravě-levě-monotonní.
Navíc ukazujeme transformaci automatů tohoto typu na kontextuální gramatiky s regulární selekcí.