Classification of String Languages via Tiling Recognizable Picture Languages

摘要: We introduce the definition of string language S recognized via picture P and prove that there is a one-to-one correspondence between linear bounded automaton (LBA) for tiling system P. As consequence systems become an alternative description LBA possibly exploits some geometric properties lines shapes inside rectangular pictures. are able to show classification sub-classes context-sensitive languages REC subclasses. Moreover we state relations among in Chomsky's hierarchy (from regular up context-sensitive) corresponding size recognize them.