Charles Explorer logo
🇬🇧

Generalized linear list automata

Publication at Faculty of Mathematics and Physics |
2005

Abstract

We present several subclasses of GLL-automata (Generalized Linear List automata), providing some variants and extensions of the Chomsky hierarchy. Our technical results include comparing the expressive power of automata having only move-to-the-right and delete-to-the-left operations with the class of (D)CFL ((deterministic) context-free languages); in particular we show an infinite hierarchy inside DCFL, defined by the increasing size of the read/write lookahead window.