Expressiveness and complexity of regular pure two-dimensional context-free languages

DOI10.1080/00207160.2013.787143zbMath1286.68181OpenAlexW2068368326MaRDI QIDQ2855787

Marcello M. Bersani, Achille Frigeri, A. Cherubini Spoletini

Publication date: 22 October 2013

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207160.2013.787143

zbMATH Keywords

picture languagesrectangular arrayspure grammarstwo-dimensional grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Discrete mathematics in relation to computer science (68R99)

Related Items (4)

Parallel contextual array insertion deletion grammars, pure 2D context-free grammars and associated P systems ⋮ Array P systems and pure 2D context-free grammars with independent mode of rewriting ⋮ An Overview of 2D Picture Array Generating Models Based on Membrane Computing ⋮ An array P system based on a new variant of pure 2D context-free grammars

Cites Work

• A unifying approach to picture grammars
• Pure 2D picture grammars and languages
• Some properties of two-dimensional on-line tessellation acceptors
• Tile rewriting grammars and picture languages
• Picture languages: tiling systems versus tile rewriting grammars.
• Scattered context grammars
• Picture languages with array rewriting rules

This page was built for publication: Expressiveness and complexity of regular pure two-dimensional context-free languages