We introduce the definition of local structures as description of computations to recognize strings and characterize families of Chomsky's hierarchy in terms of projection of frontiers of local sets of structures. Then we consider particular grid structures we call bounded-grids and study the corresponding family of string languages by proving some closure properties and giving several examples.
Giammarresi, D. (2003). Computing languages by (bounded) local sets, 2710, 304-315 [10.1007/3-540-45007-6_24].
Computing languages by (bounded) local sets
GIAMMARRESI, DORA
2003-01-01
Abstract
We introduce the definition of local structures as description of computations to recognize strings and characterize families of Chomsky's hierarchy in terms of projection of frontiers of local sets of structures. Then we consider particular grid structures we call bounded-grids and study the corresponding family of string languages by proving some closure properties and giving several examples.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
