Regular expressions and context-free grammars for picture languages

DOI10.1007/BFb0023466zbMath1498.68139MaRDI QIDQ5048931

Oliver Matz

Publication date: 9 November 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

regular expressionsformal languagesgrammarspictures languages

Mathematics Subject Classification ID

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

Related Items (17)

A CKY parser for picture grammars ⋮ Axiomatizing the identities of binoid languages ⋮ (Un)decidability of the Emptiness Problem for Multi-dimensional Context-Free Grammars ⋮ Non-recursive trade-offs between two-dimensional automata and grammars ⋮ Tiling Recognizable Two-Dimensional Languages ⋮ Recognizable vs. Regular Picture Languages ⋮ Deterministic Two-Dimensional Languages over One-Letter Alphabet ⋮ Unnamed Item ⋮ Tile rewriting grammars and picture languages ⋮ New operations and regular expressions for two-dimensional languages over one-letter alphabet ⋮ Picture languages: tiling systems versus tile rewriting grammars. ⋮ A unifying approach to picture grammars ⋮ Deterministic and unambiguous two-dimensional languages over one-letter alphabet ⋮ Characterizations of recognizable picture series ⋮ Two-dimensional models ⋮ A characterization of recognizable picture languages by tilings by finite sets ⋮ Undecidability of the emptiness problem for context-free picture languages

Cites Work

• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• Unnamed Item

This page was built for publication: Regular expressions and context-free grammars for picture languages