We introduce the definition of string language $S$ recognized via picture language $P$ and prove that there is a one-to-one correspondence between a linear bounded automaton (LBA) for $S$ and a tiling system for $P$. As consequence tiling systems become an alternative description for LBA that possibly exploits some geometric properties of lines and shapes inside the rectangular pictures. We are able to show a classification of sub-classes of context-sensitive languages via REC sub-classes. Moreover we state some relations among languages in Chomsky's hierarchy (from regularup to context-sensitive) and the corresponding size of the picture languages that recognize them.
Classification of String Languages via Tiling Recognizable Picture Languages
MADONIA, Maria Serafina
2011-01-01
Abstract
We introduce the definition of string language $S$ recognized via picture language $P$ and prove that there is a one-to-one correspondence between a linear bounded automaton (LBA) for $S$ and a tiling system for $P$. As consequence tiling systems become an alternative description for LBA that possibly exploits some geometric properties of lines and shapes inside the rectangular pictures. We are able to show a classification of sub-classes of context-sensitive languages via REC sub-classes. Moreover we state some relations among languages in Chomsky's hierarchy (from regularup to context-sensitive) and the corresponding size of the picture languages that recognize them.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
