A unifying approach to picture grammars

Details A unifying approach to picture grammars A unifying approach to picture grammars

2009-10-15

arxiv.org/abs/0910.2829v3

Computer Science

Formal Languages and Automata Theory

Scientific paper

Several old and recent classes of picture grammars, that variously extend context-free string grammars in two dimensions, are based on rules that rewrite arrays of pixels. Such grammars can be unified and extended using a tiling based approach, whereby the right part of a rule is formalized by means of a finite set of permitted tiles. We focus on a simple type of tiling,named regional, and define the corresponding regional tile grammars. They include both Siromoney's (or Matz's) Kolam grammars and their generalization by Prusa, as well as Drewes's grid grammars. Regionally defined pictures can be recognized with polynomial-time complexity by an algorithm extending the CKY one for strings. Regional tile grammars and languages are strictly included into our previous tile grammars and languages, and are incomparable with Giammarresi-Restivo tiling systems (or Wang systems).

Affiliated with

Also associated with

No associations

Rating

A unifying approach to picture grammars does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A unifying approach to picture grammars, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A unifying approach to picture grammars will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-619319