Picture languages: tiling systems versus tile rewriting grammars.

DOI10.1016/j.tcs.2006.01.038zbMath1160.68392OpenAlexW2160472035MaRDI QIDQ2490811

Matteo Pradella, Pierluigi San Pietro, Stefano Crespi Reghizzi, A. Cherubini Spoletini

Publication date: 18 May 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.01.038

zbMATH Keywords

picture language2D languagepicture grammartiling systemrecognizable picture language2D regular expressionautoinclusive derivationtile rewriting grammar

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items

Generalized Gandy-Păun-Rozenberg Machines for Tile Systems and Cellular Automata ⋮ A SAT-based parser and completer for pictures specified by tiling ⋮ On Some Classes of 2D Languages and Their Relations ⋮ A unifying approach to picture grammars ⋮ Satisfiability via Smooth Pictures ⋮ Picture Languages Generated by Assembling Tiles ⋮ Two-dimensional models ⋮ Expressiveness and complexity of regular pure two-dimensional context-free languages

Cites Work

• Some properties of two-dimensional on-line tessellation acceptors
• A characterization of recognizable picture languages by tilings by finite sets
• Tile rewriting grammars and picture languages
• Collage of two-dimensional words
• A note on phrase structure grammars
• Regular expressions and context-free grammars for picture languages
• Full AFLs and nested iterated substitution
• Unnamed Item
• Unnamed Item
• Unnamed Item