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

DOI10.1016/J.TCS.2024.114598MaRDI QIDQ6548960zbMATH OpenFDO

Authors Stefano Crespi Reghizzi, Antonio Restivo, Pierluigi San Pietro

Publication date 3 June 2024

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

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114598

zbMATH Keywords

Chomsky-Schützenberger theoremcrosswordsDyck languagepicture languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cites work

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

Cited in

(1)

• Row-column combination of Dyck words

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)