Complexity of two-dimensional patterns
From MaRDI portal
Publication:1284933
DOI10.1023/A:1023027932419zbMath0917.68156arXivcond-mat/9804071MaRDI QIDQ1284933
Kristian Lindgren, Moore, Cristopher, Mats G. Nordahl
Publication date: 8 August 1999
Published in: Journal of Statistical Physics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cond-mat/9804071
Formal languages and automata (68Q45) Topological dynamics (37B99) Cellular automata (computational aspects) (68Q80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (35)
A logical approach to locality in pictures languages ⋮ A computational model for tiling recognizable two-dimensional languages ⋮ A NEW TWO-DIMENSIONAL COMPLEXITY MEASURE ⋮ A CKY parser for picture grammars ⋮ EXPLORING INSIDE TILING RECOGNIZABLE PICTURE LANGUAGES TO FIND DETERMINISTIC SUBCLASSES ⋮ Snake-Deterministic Tiling Systems ⋮ Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages ⋮ Unnamed Item ⋮ A Nivat theorem for weighted picture automata and weighted MSO logics ⋮ Weighted picture automata and weighted logics ⋮ Some classes of rational functions for pictures ⋮ Tiling Recognizable Two-Dimensional Languages ⋮ Deterministic Two-Dimensional Languages over One-Letter Alphabet ⋮ A SAT-based parser and completer for pictures specified by tiling ⋮ Regularities unseen, randomness observed: Levels of entropy convergence ⋮ Agent-Based Modeling, Mathematical Formalism for ⋮ Strategies to scan pictures with automata based on Wang tiles ⋮ Simple picture processing based on finite automata and regular grammars ⋮ MULTISCALE COMPLEXITY/ENTROPY ⋮ A unifying approach to picture grammars ⋮ Automated pattern detection -- an algorithm for constructing optimally synchronizing multi-regular language filters ⋮ On Compiling Structured Interactive Programs with Registers and Voices ⋮ A Nivat Theorem for Weighted Picture Automata and Weighted MSO Logic ⋮ Deterministic and unambiguous two-dimensional languages over one-letter alphabet ⋮ Deterministic ordered restarting automata for picture languages ⋮ Automata with cyclic move operations for picture languages ⋮ Characterizations of recognizable picture series ⋮ A Survey on Picture-Walking Automata ⋮ Two-dimensional models ⋮ A characterization of recognizable picture languages by tilings by finite sets ⋮ A sufficient condition for non-soficness of higher-dimensional subshifts ⋮ Communication complexity tools on recognizable picture languages ⋮ PREFIX PICTURE CODES: A DECIDABLE CLASS OF TWO-DIMENSIONAL CODES ⋮ Two-dimensional Sgraffito automata ⋮ Two-dimensional codes
This page was built for publication: Complexity of two-dimensional patterns
