On the Complexity of Unary Tiling-Recognizable Picture Languages

DOI10.1007/978-3-540-70918-3_33zbMATH Open1159.68473OpenAlexW1566241976MaRDI QIDQ3590949FDOQ3590949

Authors: Massimiliano Goldwurm, Violetta Lonati, Alberto Bertoni 

Publication date: 3 September 2007

Published in: STACS 2007 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70918-3_33

Recommendations

• The Complexity of Unary Tiling Recognizable Picture Languages: Nondeterministic and Unambiguous Cases
• Exploring inside tiling recognizable picture languages to find deterministic subclasses
• scientific article; zbMATH DE number 1206599
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• A brief excursion inside the class of tiling recognizable two-dimensional languages

zbMATH Keywords

Turing machinetiling systemshead reversalunary picture languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cited In (6)

• Deterministic and unambiguous two-dimensional languages over one-letter alphabet
• The Complexity of Unary Tiling Recognizable Picture Languages: Nondeterministic and Unambiguous Cases
• Complexity and decidability for restricted classes of picture languages
• Recognizable picture languages and domino tiling
• Picture Languages Generated by Assembling Tiles
• Deterministic Two-Dimensional Languages over One-Letter Alphabet

This page was built for publication: On the Complexity of Unary Tiling-Recognizable Picture Languages

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