• PDF / 1,451,371 Bytes
• 11 Pages / 595.276 x 790.866 pts Page_size
• 85 Downloads / 183 Views

DOWNLOAD

REPORT

---

SURVEY PAPER

Generating pictures in string representation with P systems: the case of space‑filling curves Rodica Ceterchi1   · K. G. Subramanian2 Received: 14 June 2020 / Accepted: 9 October 2020 © Springer Nature Singapore Pte Ltd. 2020

Abstract The computing model of P system with its several variants is known to be a very convenient framework for dealing with different kinds of problems. P systems have been constructed for the generation of approximating geometric patterns of space-filling curves, such as the Peano curve, the Hilbert curve and others. We present the state-of-the-art in the generation of space-filling curves, and related curves, with P systems with parallel rewriting. Keywords  Space filling curves · Chain code picture languages · Parallel rewriting · P systems

1 Introduction Membrane computing, a computing model later known as P system, inspired by the living cell structure and its functioning, was developed by Păun and first introduced in 1998 in a TUCS Report, later in the seminal paper [22]. It has provided a rich platform for dealing with many problems of computing and has opened up a variety of research directions [16]. The first approach to generate 2D words [17] and languages with P systems was made in [3]. Those initial models, and many more developed afterwards, used pictures represented as arrays, and array-rewriting rules. An open problem formulated in [3] was to generate pictures codified as strings, and thus to use P systems with string-rewriting rules for generating pictures. In 1982, in the paper [19], the authors described a class of pictures which can be codified as strings. The pictures are composed of straight lines in the plane, described by words over the four-letter alphabet {u, d, r, l} , codifying unit lines drawn by a writing head from a current point to another, in one of the four directions—up, down, right, left—on the 2D lattice. These pictures were called chain-code pictures, they * Rodica Ceterchi [email protected] 1



Faculty of Mathematics and Computer Science, University of Bucharest, 14 Academiei St, 010014 Bucharest, Romania



Faculty of Science, Liverpool Hope University, Hope Park, Liverpool L16 9JD, UK

2

make up chain-code languages, and chain-code grammars were introduced to generate them. Space-filling curves (SFC) [25] are continuous curves which fill up every point of a unit square in the plane. The first space-filling curve, subsequently called the Peano curve, was proposed by Peano in 1890 [21]. It answered an open problem, namely: “can a line pass through every point of a square?” Many other space-filling curves followed: the Hilbert curve [18] the next year, and later the Sierpiński curve [26], Wunderlich’s versions of the Peano curve [29], Moore’s version of the Hilbert curve [20], etc. Space-filling curves have important applications, as can be seen in [1]. Their mathematical representations and properties have been intensively studied over the years. They can be seen as limits of finite approximations, and these in turn can be describe