HYPERGRAPH AUTOMATA: A THEORETICAL MODEL FOR PATTERNED SELF-ASSEMBLY
| Autor: | Lila Kari, Amirhossein Simjour, Steffen Kopecki |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
FOS: Computer and information sciences
Discrete mathematics TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Nested word Discrete Mathematics (cs.DM) Formal Languages and Automata Theory (cs.FL) Wang tile Timed automaton Computer Science - Formal Languages and Automata Theory ω-automaton Nonlinear Sciences::Cellular Automata and Lattice Gases Mobile automaton TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Continuous spatial automaton FOS: Mathematics Computer Science (miscellaneous) Mathematics - Combinatorics Automata theory Quantum finite automata Combinatorics (math.CO) Computer Science::Formal Languages and Automata Theory Computer Science - Discrete Mathematics Mathematics |
| Zdroj: | International Journal of Foundations of Computer Science. 25:419-439 |
| ISSN: | 1793-6373 0129-0541 |
| DOI: | 10.1142/s0129054114400048 |
| Popis: | Patterned self-assembly is a process whereby coloured tiles self-assemble to build a rectangular coloured pattern. We propose self-assembly (SA) hypergraph automata as an automata-theoretic model for patterned self-assembly. We investigate the computational power of SA-hypergraph automata and show that for every recognizable picture language, there exists an SA-hypergraph automaton that accepts this language. Conversely, we prove that for any restricted SA-hypergraph automaton, there exists a Wang Tile System, a model for recognizable picture languages, that accepts the same language. The advantage of SA-hypergraph automata over Wang automata, acceptors for the class of recognizable picture languages, is that they do not rely on an a priori defined scanning strategy Comment: 25 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|