On the Complexity of Unary Tiling-Recognizable Picture Languages

DOI10.1007/978-3-540-70918-3_33MaRDI QIDQ3590949zbMATHOpenAlexFDO

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

zbMATH Keywords

Turing machinetiling systemshead reversalunary picture languages

Mathematics Subject Classification ID

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

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

Cited in

(6)

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

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)