The Complexity of Unary Tiling Recognizable Picture Languages: Nondeterministic and Unambiguous Cases

DOI10.3233/FI-2009-0042MaRDI QIDQ3633999zbMATH OpenOpenAlexFDO

Authors Massimiliano Goldwurm, Violetta Lonati, Alberto Bertoni

Publication date 23 June 2009

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2009-0042

zbMATH Keywords

head reversal-bounded computationlinearly space-bounded Turing machinetiling systemstwo-dimensional languages

Mathematics Subject Classification ID

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

Recommendations

• On the Complexity of Unary Tiling-Recognizable Picture Languages
• Exploring inside tiling recognizable picture languages to find deterministic subclasses
• Unambiguous recognizable two-dimensional languages
• A brief excursion inside the class of tiling recognizable two-dimensional languages
• Deterministic Two-Dimensional Languages over One-Letter Alphabet

Cited in

(5)

• Two-dimensional models
• Classes of two-dimensional languages and recognizability conditions
• Strategies to scan pictures with automata based on Wang tiles
• Snake-Deterministic Tiling Systems
• On the Complexity of Unary Tiling-Recognizable Picture Languages

This page was built for publication: The Complexity of Unary Tiling Recognizable Picture Languages: Nondeterministic and Unambiguous Cases

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