Tile rewriting grammars and picture languages

DOI10.1016/j.tcs.2005.03.041zbMath1079.68047OpenAlexW2053959528MaRDI QIDQ2484438

Matteo Pradella, Stefano Crespi Reghizzi

Publication date: 1 August 2005

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

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

zbMATH Keywords

Picture languagesContext-free grammarsLocally testable languages2D languagesTiling systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

A CKY parser for picture grammars ⋮ EXPLORING INSIDE TILING RECOGNIZABLE PICTURE LANGUAGES TO FIND DETERMINISTIC SUBCLASSES ⋮ HYPERGRAPH AUTOMATA: A THEORETICAL MODEL FOR PATTERNED SELF-ASSEMBLY ⋮ Weighted picture automata and weighted logics ⋮ On Some Classes of 2D Languages and Their Relations ⋮ Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages ⋮ Picture languages: tiling systems versus tile rewriting grammars. ⋮ A unifying approach to picture grammars ⋮ Characterizations of recognizable picture series ⋮ Picture Languages Generated by Assembling Tiles ⋮ Two-dimensional models ⋮ Expressiveness and complexity of regular pure two-dimensional context-free languages ⋮ Unambiguous recognizable two-dimensional languages

Cites Work

• Some properties of two-dimensional on-line tessellation acceptors
• Regular expressions and context-free grammars for picture languages
• Unnamed Item
• Unnamed Item