An Isometric Context-Free Array Grammar That Generates Rectangles

Yasunori YAMAMOTO  Kenichi MORITA  Kazuhiro SUGATA  

IEICE TRANSACTIONS (1976-1990)   Vol.E65   No.12   pp.754-755
Publication Date: 1982/12/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: LETTER
Category: Automata and Languages

Full Text: PDF(140.7KB)>>
Buy this Article

We present an Isometric Context-Free Array Grammar (ICFAG) that generates the set of all solid upright rectangles. This is performed by using the property that blank symbols in the rewriting rules enable ICFAGs to sense the local shapes of the host array. Thus ICFAGs are context-sensitive in some sense.