using string languages to describe picture languages-论文.pdf

NFORMATION AND CONTROL 54, 155--185 (1982)
Using String Languages to Describe Picture Languages
H. A. MAURER
Institute fiir Informationsverarbeitung Graz (IIG),
Teehnische Universitdt Graz und Osterr.
Computer Gesellsehaft, A-8O l OGraz, Austria
G. ROZENBERG
Department of Mathematics, University of Leiden,
2300RA Leiden, The Netherlands
E. WELZL
Institute fiir Informationsverarbeitung Graz (IIG),
Technische Universitdt Graz und Osterr.
Computer Gesellschaft, A-8O lOGraz, Austria
A picture is a set of unit lines from the Cartesian plane considered as a square
grid. A word over the alphabet {l, r, u, d} is apicture description in the sense that it
represents a traversal of a picture where the interpretation of the symbols l, r, u, d,
is:
l go one unit line to the left of the current point,
r go one unit line to the right of the current point,
u go one unit line up from the current point, and
d go one unit line down from the current point.
A set of picture descriptions forms a picture description language. This paper
investigates the basic properties of pictures and picture description languages from
the formal language theory point of view.
INTRODUCTION
One of the approaches to pattern recognition is the syntactic approach,
see, ., Fu (1974) and Fu (1977). Within this approach patterns are being
composed of subpatterns (primitives). When the basic primitives are
represented as nodes and their interconnections as edges, patterns can be
represented by graphs and their sets (language