On the complexity of the recognition of parallel 2D-image languages

DOI10.1016/0020-0190(91)90063-NzbMath0731.68068MaRDI QIDQ808271

Wojciech Rytter, Ahmed Saoudi

Publication date: 1991

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

context-free grammarsparallel random access machineimage grammarpicture generationpicture grammars

Mathematics Subject Classification ID

Computing methodologies for image processing (68U10) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Distributed algorithms (68W15)

Related Items

Parallel recognition and ranking of context-free languages

Cites Work

• Tree-size bounded alternation
• Parallel computation and conflicts in memory access
• The membership question for ETOL-languages is polynomially complete
• General context-free recognition in less than cubic time
• Parallel generation of infinite images
• Parallel Matrix and Graph Algorithms
• Array grammar normal forms
• Recognition and parsing of context-free languages in time n3
• An efficient context-free parsing algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of the recognition of parallel 2D-image languages