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.
978-3-642-21253-6
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/77834
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact