Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at customercare@wspc.com for any enquiries.

SEARCH GUIDE  Download Search Tip PDF File

  • articleNo Access

    AN UNIVERSALITY RESULT FOR A (MEM)BRANE CALCULUS BASED ON MATE/DRIP OPERATIONS

    Operations with membranes are essential both in brane calculi and in membrane computing. In this paper we take four basic operations from brane calculi, pino, exo, mate, drip, we express them in terms of the membrane computing formalism, and then we investigate the computing power of the P systems using the mate, drip operations as unique evolution rules. All operations are controlled by – and make evolve – multisets of protein-objects embedded in the membranes themselves (not contained in the compartments of the cell, as standard in membrane computing; all compartments delimited by membranes are here empty). Somewhat surprisingly, for systems which use the mate, drip operations we obtain the Turing completeness. The power of P systems based on other operations remains to be investigated.

  • articleNo Access

    ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS

    Matrix grammars are one of the classical topics of formal languages, more specifically, regulated rewriting. Although this type of control on the work of context-free grammars is one of the earliest, matrix grammars still raise interesting questions (not to speak about old open problems in this area). One such class of problems concerns the leftmost derivation (in grammars without appearance checking). The main point of this paper is the systematic study of all possibilities of defining leftmost derivation in matrix grammars. Twelve types of such a restriction are defined, only four of which being discussed in literature. For seven of them, we find a proof of a characterization of recursively enumerable languages (by matrix grammars with arbitrary context-free rules but without appearance checking). Other three cases characterize the recursively enumerable languages modulo a morphism and an intersection with a regular language. In this way, we solve nearly all problems listed as open on page 67 of the monograph [7], which can be seen as the main contribution of this paper.

    Moreover, we find a characterization of the recursively enumerable languages for matrix grammars with the leftmost restriction defined on classes of a given partition of the nonterminal alphabet.

  • articleNo Access

    SIROMONEY ARRAY GRAMMARS AND APPLICATIONS

    The Siromoney matrix model is a simple and elegant model for describing two-dimensional digital picture languages. The notion of attaching indices to nonterminals in a generative grammar, introduced and investigated by Aho. is considered in the vertical phase of a Siromoney matrix grammar (SMG). The advantage of this study is that the new model retains the simplicity and elegance of SMG but increases the generative power and enables us to describe pictures not generable by SMG. Besides certain closure properties and hierarchy results. applications of these two-dimensional grammars to describe tilings, polyominoes, distorted patterns and parquet deformations are studied.

  • chapterNo Access

    SIROMONEY ARRAY GRAMMARS AND APPLICATIONS

    The Siromoney matrix model is a simple and elegant model for describing two-dimensional digital picture languages. The notion of attaching indices to nonterminals in a generative grammar, introduced and investigated by Aho, is considered in the vertical phase of a Siromoney matrix grammar (SMG). The advantage of this study is that the new model retains the simplicity and elegance of SMG but increases the generative power and enables us to describe pictures not generable by SMG. Besides certain closure properties and hierarchy results, applications of these two-dimensional grammars to describe tilings, polyominoes, distorted patterns and parquet deformations are studied.