From words to pictures: row-column combinations and Chomsky-Schützenberger theorem

DOI10.1016/J.TCS.2024.114598zbMATH Open1541.68191MaRDI QIDQ6548960FDOQ6548960

Authors: Stefano Crespi Reghizzi, Antonio Restivo, Pierluigi San Pietro 

Publication date: 3 June 2024

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

Recommendations

• Developments in Language Theory
• Recognizable vs. Regular Picture Languages
• Two-dimensional regular languages and their syntactic characaterization
• Expressiveness and complexity of regular pure two-dimensional context-free languages

zbMATH Keywords

picture languagesDyck languagecrosswordsChomsky-Schützenberger theorem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Visibly pushdown languages
• Reconstructing convex polyominoes from horizontal and vertical projections
• Title not available (Why is that?)
• Title not available (Why is that?)
• Context-sensitive string languages and recognizable picture languages
• Recognizable picture languages and domino tiling
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• On Fine and Wilf's theorem for bidimensional words.
• Periodicity in rectangular arrays
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tile rewriting grammars and picture languages
• Regular expressions and context-free grammars for picture languages
• Non-recursive trade-offs between two-dimensional automata and grammars
• Title not available (Why is that?)
• Classification of string languages via tiling recognizable picture languages
• Non-erasing Variants of the Chomsky–Schützenberger Theorem
• Two-dimensional models
• Title not available (Why is that?)
• HV-Palindromes in Two-Dimensional Words
• Non-erasing Chomsky-Schützenberger theorem with grammar-independent alphabet
• The complexity of regex crosswords
• Reducing the local alphabet size in tiling systems by means of 2D comma-free codes

This page was built for publication: From words to pictures: row-column combinations and Chomsky-Schützenberger theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6548960)