Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
438824 | Theoretical Computer Science | 2006 | 14 Pages |
Abstract
Two formal models of pictures, i.e., two dimensional (2D) languages are compared: tiling systems and tile rewriting grammars, which resp. extend to 2D the regular and context-free languages. Two results extending classical language properties into 2D are proved. First, non-recursive tile writing grammars (TRG) coincide with tiling systems (TS). Second, non-self-embedding TRG are suitably defined as corner grammars, showing that they generate TS languages. The proofs exploit newly introduced language substitutions, also nested and iterated.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics