The Experts below are selected from a list of 7542 Experts worldwide ranked by ideXlab platform
Trent A. Rogers - One of the best experts on this subject based on the ideXlab platform.
-
FOCS - Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016Co-Authors: Jacob Hendricks, Matthew J. Patitz, Trent A. RogersAbstract:As a mathematical Model of tile-based self-assembling systems, Winfree's abstract Tile Assembly Model (aTAM) has proven to be a remarkable platform for studying and understanding the behaviors and powers of self-assembling systems. Furthermore, as it is capable of Turing universal computation, the aTAM allows algorithmic self-Assembly, in which the components can be designed so that the rules governing their behaviors force them to inherently execute prescribed algorithms as they combine. This power has yielded a wide variety of theoretical results in the aTAM utilizing algorithmic self-Assembly to design systems capable of performing complex computations and forming extremely intricate structures. Adding to the completeness of the Model, in FOCS 2012 the aTAM was shown to also be intrinsically universal, which means that there exists one single tile set such that for any arbitrary input aTAM system, that tile set can be configured into a "seed" structure which will then cause self-Assembly using that tile set to simulate the input system, capturing its full dynamics modulo only a scale factor. However, the "universal simulator" of that result makes use of nondeterminism in terms of the tiles placed in several key locations when different Assembly sequences are followed. This nondeterminism remains even when the simulator is simulating a system which is directed, meaning that it has exactly one unique terminal Assembly and for any given location, no matter which Assembly sequence is followed, the same tile type is always placed there. The question which then arose was whether or not that nondeterminism is fundamentally required, and if any universal simulator must in fact utilize more nondeterminism than directed systems when simulating them. In this paper, we answer that question in the affirmative: the class of directed systems in the aTAM is not intrinsically universal, meaning there is no universal simulator for directed systems which itself is always directed. This result provides a powerful insight into the role of nondeterminism in self-Assembly, which is itself a fundamentally nondeterministic process occurring via unguided local interactions. Furthermore, to achieve this result we leverage powerful results of computational complexity hierarchies, including tight bounds on both best and worst-case complexities of decidable languages, to tailor design systems with precisely controllable space resources available to computations embedded within them. We also develop novel techniques for designing systems containing subsystems with disjoint, mutually exclusive computational powers. The main result will be important in the development of future simulation systems, and the supporting design techniques and lemmas will provide powerful tools for the development of future aTAM systems as well as proofs of their computational abilities.
-
Universal Simulation of Directed Systems in the abstract Tile Assembly Model Requires Undirectedness
arXiv: Computational Geometry, 2016Co-Authors: Jacob Hendricks, Matthew J. Patitz, Trent A. RogersAbstract:As a mathematical Model of self-assembling systems, Winfree's abstract Tile Assembly Model (aTAM) is a remarkable platform for studying the behaviors and powers of self-assembling systems. Capable of Turing universal computation, the aTAM allows algorithmic self-Assembly, in which the components can be designed so that the rules governing their behaviors force them to inherently execute prescribed algorithms as they combine. Adding to its completeness, the aTAM was shown to also be intrinsically universal, which means that there exists a single tile set such that for any arbitrary input aTAM system, that tile set can be configured into a seed structure which will then cause self-Assembly using that tile set to simulate the input system, capturing its full dynamics modulo only a scale factor. However, the universal simulator previously given makes use of nondeterminism in terms of tile types placed in several key locations when different Assembly sequences are followed, even when simulating a directed system, meaning one that has exactly one unique terminal Assembly. The question then became whether or not that nondeterminism is fundamentally required. Here, we answer that in the affirmative: the class of directed systems in the aTAM is not intrinsically universal, meaning there is no universal simulator for directed systems which itself is always directed. This provides insight into the role of nondeterminism in self-Assembly, which is itself a fundamentally nondeterministic process. To achieve this result we leverage powerful results of computational complexity hierarchies, including tight bounds on both best and worst-case complexities of decidable languages, to design systems with precisely controllable space resources available to embedded computations. We also develop novel techniques for designing systems containing subsystems with disjoint, mutually exclusive computational powers.
-
the two handed tile Assembly Model is not intrinsically universal
Algorithmica, 2016Co-Authors: Erik D Demaine, Scott M. Summers, Matthew J. Patitz, Trent A. Rogers, Robert T Schweller, Damien WoodsAbstract:The Two-Handed Tile Assembly Model (2HAM) is a Model of algorithmic self-Assembly in which large structures, or assemblies of tiles, are grown by the binding of smaller assemblies. In order to bind, two assemblies must have matching glues that can simultaneously touch each other, and stick together with strength that is at least the temperature $$\tau $$?, where $$\tau $$? is some fixed positive integer. We ask whether the 2HAM is intrinsically universal. In other words, we ask: is there a single 2HAM tile set $$U$$U which can be used to simulate any instance of the Model? Our main result is a negative answer to this question. We show that for all $$\tau ' < \tau $$??Assembly Model is intrinsically universal. On the positive side, we prove that, for every fixed temperature $$\tau \ge 2$$??2, temperature-$$\tau $$? 2HAM tile systems are indeed intrinsically universal. In other words, for each $$\tau $$? there is a single intrinsically universal 2HAM tile set $$U_{\tau }$$U? that, when appropriately initialized, is capable of simulating the behavior of any temperature-$$\tau $$? 2HAM tile system. As a corollary, we find an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. Finally, we show that for each $$\tau $$?, there is a temperature-$$\tau $$? 2HAM system that simultaneously simulates all temperature-$$\tau $$? 2HAM systems.
-
Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016Co-Authors: Jacob Hendricks, Matthew J. Patitz, Trent A. RogersAbstract:As a mathematical Model of tile-based self-assembling systems, Winfree's abstract Tile Assembly Model (aTAM) has proven to be a remarkable platform for studying and understanding the behaviors and powers of self-assembling systems. Furthermore, as it is capable of Turing universal computation, the aTAM allows algorithmic self-Assembly, in which the components can be designed so that the rules governing their behaviors force them to inherently execute prescribed algorithms as they combine. This power has yielded a wide variety of theoretical results in the aTAM utilizing algorithmic self-Assembly to design systems capable of performing complex computations and forming extremely intricate structures. Adding to the completeness of the Model, in FOCS 2012 the aTAM was shown to also be intrinsically universal, which means that there exists one single tile set such that for any arbitrary input aTAM system, that tile set can be configured into a "seed" structure which will then cause self-Assembly using that tile set to simulate the input system, capturing its full dynamics modulo only a scale factor. However, the "universal simulator" of that result makes use of nondeterminism in terms of the tiles placed in several key locations when different Assembly sequences are followed. This nondeterminism remains even when the simulator is simulating a system which is directed, meaning that it has exactly one unique terminal Assembly and for any given location, no matter which Assembly sequence is followed, the same tile type is always placed there. The question which then arose was whether or not that nondeterminism is fundamentally required, and if any universal simulator must in fact utilize more nondeterminism than directed systems when simulating them. In this paper, we answer that question in the affirmative: the class of directed systems in the aTAM is not intrinsically universal, meaning there is no universal simulator for directed systems which itself is always directed. This result provides a powerful insight into the role of nondeterminism in self-Assembly, which is itself a fundamentally nondeterministic process occurring via unguided local interactions. Furthermore, to achieve this result we leverage powerful results of computational complexity hierarchies, including tight bounds on both best and worst-case complexities of decidable languages, to tailor design systems with precisely controllable space resources available to computations embedded within them. We also develop novel techniques for designing systems containing subsystems with disjoint, mutually exclusive computational powers. The main result will be important in the development of future simulation systems, and the supporting design techniques and lemmas will provide powerful tools for the development of future aTAM systems as well as proofs of their computational abilities.
-
the two handed tile Assembly Model is not intrinsically universal
International Colloquium on Automata Languages and Programming, 2013Co-Authors: Erik D Demaine, Scott M. Summers, Matthew J. Patitz, Trent A. Rogers, Robert T Schweller, Damien WoodsAbstract:In this paper, we study the intrinsic universality of the well-studied Two-Handed Tile Assembly Model (2HAM), in which two "supertile" assemblies, each consisting of one or more unit-square tiles, can fuse together (self-assemble) whenever their total attachment strength is at least the global temperature τ. Our main result is that for all τ′<τ, each temperature-τ′ 2HAM tile system cannot simulate at least one temperature-τ 2HAM tile system. This impossibility result proves that the 2HAM is not intrinsically universal, in stark contrast to the simpler abstract Tile Assembly Model which was shown to be intrinsically universal (The tile Assembly Model is intrinsically universal, FOCS 2012). On the positive side, we prove that, for every fixed temperature τ≥2, temperature-τ 2HAM tile systems are intrinsically universal: for each τ there is a single universal 2HAM tile set U that, when appropriately initialized, is capable of simulating the behavior of any temperature τ 2HAM tile system. As a corollary of these results we find an infinite set of infinite hierarchies of 2HAM systems with strictly increasing power within each hierarchy. Finally, we show how to construct, for each τ, a temperature-τ 2HAM system that simultaneously simulates all temperature-τ 2HAM systems.
Matthew J. Patitz - One of the best experts on this subject based on the ideXlab platform.
-
Hierarchical growth is necessary and (sometimes) sufficient to self-assemble discrete self-similar fractals
Natural Computing, 2019Co-Authors: Jacob Hendricks, Matthew J. Patitz, Joseph Opseth, Scott M. SummersAbstract:In this paper, we prove that in the abstract Tile Assembly Model (aTAM), an accretion-based Model which only allows for a single tile to attach to a growing Assembly at each step, there are no tile Assembly systems capable of self-assembling the discrete self-similar fractals known as the “H” and “U” fractals. We then show that in a related Model which allows for hierarchical self-Assembly, the 2-Handed Assembly Model (2HAM), there does exist a tile Assembly system which self-assembles the “U” fractal and conjecture that the same holds for the “H” fractal. This is the first example of discrete self similar fractals which self-assemble in the 2HAM but not in the aTAM, providing a direct comparison of the Models and greater understanding of the power of hierarchical Assembly.
-
FOCS - Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016Co-Authors: Jacob Hendricks, Matthew J. Patitz, Trent A. RogersAbstract:As a mathematical Model of tile-based self-assembling systems, Winfree's abstract Tile Assembly Model (aTAM) has proven to be a remarkable platform for studying and understanding the behaviors and powers of self-assembling systems. Furthermore, as it is capable of Turing universal computation, the aTAM allows algorithmic self-Assembly, in which the components can be designed so that the rules governing their behaviors force them to inherently execute prescribed algorithms as they combine. This power has yielded a wide variety of theoretical results in the aTAM utilizing algorithmic self-Assembly to design systems capable of performing complex computations and forming extremely intricate structures. Adding to the completeness of the Model, in FOCS 2012 the aTAM was shown to also be intrinsically universal, which means that there exists one single tile set such that for any arbitrary input aTAM system, that tile set can be configured into a "seed" structure which will then cause self-Assembly using that tile set to simulate the input system, capturing its full dynamics modulo only a scale factor. However, the "universal simulator" of that result makes use of nondeterminism in terms of the tiles placed in several key locations when different Assembly sequences are followed. This nondeterminism remains even when the simulator is simulating a system which is directed, meaning that it has exactly one unique terminal Assembly and for any given location, no matter which Assembly sequence is followed, the same tile type is always placed there. The question which then arose was whether or not that nondeterminism is fundamentally required, and if any universal simulator must in fact utilize more nondeterminism than directed systems when simulating them. In this paper, we answer that question in the affirmative: the class of directed systems in the aTAM is not intrinsically universal, meaning there is no universal simulator for directed systems which itself is always directed. This result provides a powerful insight into the role of nondeterminism in self-Assembly, which is itself a fundamentally nondeterministic process occurring via unguided local interactions. Furthermore, to achieve this result we leverage powerful results of computational complexity hierarchies, including tight bounds on both best and worst-case complexities of decidable languages, to tailor design systems with precisely controllable space resources available to computations embedded within them. We also develop novel techniques for designing systems containing subsystems with disjoint, mutually exclusive computational powers. The main result will be important in the development of future simulation systems, and the supporting design techniques and lemmas will provide powerful tools for the development of future aTAM systems as well as proofs of their computational abilities.
-
Universal Simulation of Directed Systems in the abstract Tile Assembly Model Requires Undirectedness
arXiv: Computational Geometry, 2016Co-Authors: Jacob Hendricks, Matthew J. Patitz, Trent A. RogersAbstract:As a mathematical Model of self-assembling systems, Winfree's abstract Tile Assembly Model (aTAM) is a remarkable platform for studying the behaviors and powers of self-assembling systems. Capable of Turing universal computation, the aTAM allows algorithmic self-Assembly, in which the components can be designed so that the rules governing their behaviors force them to inherently execute prescribed algorithms as they combine. Adding to its completeness, the aTAM was shown to also be intrinsically universal, which means that there exists a single tile set such that for any arbitrary input aTAM system, that tile set can be configured into a seed structure which will then cause self-Assembly using that tile set to simulate the input system, capturing its full dynamics modulo only a scale factor. However, the universal simulator previously given makes use of nondeterminism in terms of tile types placed in several key locations when different Assembly sequences are followed, even when simulating a directed system, meaning one that has exactly one unique terminal Assembly. The question then became whether or not that nondeterminism is fundamentally required. Here, we answer that in the affirmative: the class of directed systems in the aTAM is not intrinsically universal, meaning there is no universal simulator for directed systems which itself is always directed. This provides insight into the role of nondeterminism in self-Assembly, which is itself a fundamentally nondeterministic process. To achieve this result we leverage powerful results of computational complexity hierarchies, including tight bounds on both best and worst-case complexities of decidable languages, to design systems with precisely controllable space resources available to embedded computations. We also develop novel techniques for designing systems containing subsystems with disjoint, mutually exclusive computational powers.
-
the two handed tile Assembly Model is not intrinsically universal
Algorithmica, 2016Co-Authors: Erik D Demaine, Scott M. Summers, Matthew J. Patitz, Trent A. Rogers, Robert T Schweller, Damien WoodsAbstract:The Two-Handed Tile Assembly Model (2HAM) is a Model of algorithmic self-Assembly in which large structures, or assemblies of tiles, are grown by the binding of smaller assemblies. In order to bind, two assemblies must have matching glues that can simultaneously touch each other, and stick together with strength that is at least the temperature $$\tau $$?, where $$\tau $$? is some fixed positive integer. We ask whether the 2HAM is intrinsically universal. In other words, we ask: is there a single 2HAM tile set $$U$$U which can be used to simulate any instance of the Model? Our main result is a negative answer to this question. We show that for all $$\tau ' < \tau $$??Assembly Model is intrinsically universal. On the positive side, we prove that, for every fixed temperature $$\tau \ge 2$$??2, temperature-$$\tau $$? 2HAM tile systems are indeed intrinsically universal. In other words, for each $$\tau $$? there is a single intrinsically universal 2HAM tile set $$U_{\tau }$$U? that, when appropriately initialized, is capable of simulating the behavior of any temperature-$$\tau $$? 2HAM tile system. As a corollary, we find an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. Finally, we show that for each $$\tau $$?, there is a temperature-$$\tau $$? 2HAM system that simultaneously simulates all temperature-$$\tau $$? 2HAM systems.
-
Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016Co-Authors: Jacob Hendricks, Matthew J. Patitz, Trent A. RogersAbstract:As a mathematical Model of tile-based self-assembling systems, Winfree's abstract Tile Assembly Model (aTAM) has proven to be a remarkable platform for studying and understanding the behaviors and powers of self-assembling systems. Furthermore, as it is capable of Turing universal computation, the aTAM allows algorithmic self-Assembly, in which the components can be designed so that the rules governing their behaviors force them to inherently execute prescribed algorithms as they combine. This power has yielded a wide variety of theoretical results in the aTAM utilizing algorithmic self-Assembly to design systems capable of performing complex computations and forming extremely intricate structures. Adding to the completeness of the Model, in FOCS 2012 the aTAM was shown to also be intrinsically universal, which means that there exists one single tile set such that for any arbitrary input aTAM system, that tile set can be configured into a "seed" structure which will then cause self-Assembly using that tile set to simulate the input system, capturing its full dynamics modulo only a scale factor. However, the "universal simulator" of that result makes use of nondeterminism in terms of the tiles placed in several key locations when different Assembly sequences are followed. This nondeterminism remains even when the simulator is simulating a system which is directed, meaning that it has exactly one unique terminal Assembly and for any given location, no matter which Assembly sequence is followed, the same tile type is always placed there. The question which then arose was whether or not that nondeterminism is fundamentally required, and if any universal simulator must in fact utilize more nondeterminism than directed systems when simulating them. In this paper, we answer that question in the affirmative: the class of directed systems in the aTAM is not intrinsically universal, meaning there is no universal simulator for directed systems which itself is always directed. This result provides a powerful insight into the role of nondeterminism in self-Assembly, which is itself a fundamentally nondeterministic process occurring via unguided local interactions. Furthermore, to achieve this result we leverage powerful results of computational complexity hierarchies, including tight bounds on both best and worst-case complexities of decidable languages, to tailor design systems with precisely controllable space resources available to computations embedded within them. We also develop novel techniques for designing systems containing subsystems with disjoint, mutually exclusive computational powers. The main result will be important in the development of future simulation systems, and the supporting design techniques and lemmas will provide powerful tools for the development of future aTAM systems as well as proofs of their computational abilities.
Jacob Hendricks - One of the best experts on this subject based on the ideXlab platform.
-
Hierarchical growth is necessary and (sometimes) sufficient to self-assemble discrete self-similar fractals
Natural Computing, 2019Co-Authors: Jacob Hendricks, Matthew J. Patitz, Joseph Opseth, Scott M. SummersAbstract:In this paper, we prove that in the abstract Tile Assembly Model (aTAM), an accretion-based Model which only allows for a single tile to attach to a growing Assembly at each step, there are no tile Assembly systems capable of self-assembling the discrete self-similar fractals known as the “H” and “U” fractals. We then show that in a related Model which allows for hierarchical self-Assembly, the 2-Handed Assembly Model (2HAM), there does exist a tile Assembly system which self-assembles the “U” fractal and conjecture that the same holds for the “H” fractal. This is the first example of discrete self similar fractals which self-assemble in the 2HAM but not in the aTAM, providing a direct comparison of the Models and greater understanding of the power of hierarchical Assembly.
-
FOCS - Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016Co-Authors: Jacob Hendricks, Matthew J. Patitz, Trent A. RogersAbstract:As a mathematical Model of tile-based self-assembling systems, Winfree's abstract Tile Assembly Model (aTAM) has proven to be a remarkable platform for studying and understanding the behaviors and powers of self-assembling systems. Furthermore, as it is capable of Turing universal computation, the aTAM allows algorithmic self-Assembly, in which the components can be designed so that the rules governing their behaviors force them to inherently execute prescribed algorithms as they combine. This power has yielded a wide variety of theoretical results in the aTAM utilizing algorithmic self-Assembly to design systems capable of performing complex computations and forming extremely intricate structures. Adding to the completeness of the Model, in FOCS 2012 the aTAM was shown to also be intrinsically universal, which means that there exists one single tile set such that for any arbitrary input aTAM system, that tile set can be configured into a "seed" structure which will then cause self-Assembly using that tile set to simulate the input system, capturing its full dynamics modulo only a scale factor. However, the "universal simulator" of that result makes use of nondeterminism in terms of the tiles placed in several key locations when different Assembly sequences are followed. This nondeterminism remains even when the simulator is simulating a system which is directed, meaning that it has exactly one unique terminal Assembly and for any given location, no matter which Assembly sequence is followed, the same tile type is always placed there. The question which then arose was whether or not that nondeterminism is fundamentally required, and if any universal simulator must in fact utilize more nondeterminism than directed systems when simulating them. In this paper, we answer that question in the affirmative: the class of directed systems in the aTAM is not intrinsically universal, meaning there is no universal simulator for directed systems which itself is always directed. This result provides a powerful insight into the role of nondeterminism in self-Assembly, which is itself a fundamentally nondeterministic process occurring via unguided local interactions. Furthermore, to achieve this result we leverage powerful results of computational complexity hierarchies, including tight bounds on both best and worst-case complexities of decidable languages, to tailor design systems with precisely controllable space resources available to computations embedded within them. We also develop novel techniques for designing systems containing subsystems with disjoint, mutually exclusive computational powers. The main result will be important in the development of future simulation systems, and the supporting design techniques and lemmas will provide powerful tools for the development of future aTAM systems as well as proofs of their computational abilities.
-
Universal Simulation of Directed Systems in the abstract Tile Assembly Model Requires Undirectedness
arXiv: Computational Geometry, 2016Co-Authors: Jacob Hendricks, Matthew J. Patitz, Trent A. RogersAbstract:As a mathematical Model of self-assembling systems, Winfree's abstract Tile Assembly Model (aTAM) is a remarkable platform for studying the behaviors and powers of self-assembling systems. Capable of Turing universal computation, the aTAM allows algorithmic self-Assembly, in which the components can be designed so that the rules governing their behaviors force them to inherently execute prescribed algorithms as they combine. Adding to its completeness, the aTAM was shown to also be intrinsically universal, which means that there exists a single tile set such that for any arbitrary input aTAM system, that tile set can be configured into a seed structure which will then cause self-Assembly using that tile set to simulate the input system, capturing its full dynamics modulo only a scale factor. However, the universal simulator previously given makes use of nondeterminism in terms of tile types placed in several key locations when different Assembly sequences are followed, even when simulating a directed system, meaning one that has exactly one unique terminal Assembly. The question then became whether or not that nondeterminism is fundamentally required. Here, we answer that in the affirmative: the class of directed systems in the aTAM is not intrinsically universal, meaning there is no universal simulator for directed systems which itself is always directed. This provides insight into the role of nondeterminism in self-Assembly, which is itself a fundamentally nondeterministic process. To achieve this result we leverage powerful results of computational complexity hierarchies, including tight bounds on both best and worst-case complexities of decidable languages, to design systems with precisely controllable space resources available to embedded computations. We also develop novel techniques for designing systems containing subsystems with disjoint, mutually exclusive computational powers.
-
Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016Co-Authors: Jacob Hendricks, Matthew J. Patitz, Trent A. RogersAbstract:As a mathematical Model of tile-based self-assembling systems, Winfree's abstract Tile Assembly Model (aTAM) has proven to be a remarkable platform for studying and understanding the behaviors and powers of self-assembling systems. Furthermore, as it is capable of Turing universal computation, the aTAM allows algorithmic self-Assembly, in which the components can be designed so that the rules governing their behaviors force them to inherently execute prescribed algorithms as they combine. This power has yielded a wide variety of theoretical results in the aTAM utilizing algorithmic self-Assembly to design systems capable of performing complex computations and forming extremely intricate structures. Adding to the completeness of the Model, in FOCS 2012 the aTAM was shown to also be intrinsically universal, which means that there exists one single tile set such that for any arbitrary input aTAM system, that tile set can be configured into a "seed" structure which will then cause self-Assembly using that tile set to simulate the input system, capturing its full dynamics modulo only a scale factor. However, the "universal simulator" of that result makes use of nondeterminism in terms of the tiles placed in several key locations when different Assembly sequences are followed. This nondeterminism remains even when the simulator is simulating a system which is directed, meaning that it has exactly one unique terminal Assembly and for any given location, no matter which Assembly sequence is followed, the same tile type is always placed there. The question which then arose was whether or not that nondeterminism is fundamentally required, and if any universal simulator must in fact utilize more nondeterminism than directed systems when simulating them. In this paper, we answer that question in the affirmative: the class of directed systems in the aTAM is not intrinsically universal, meaning there is no universal simulator for directed systems which itself is always directed. This result provides a powerful insight into the role of nondeterminism in self-Assembly, which is itself a fundamentally nondeterministic process occurring via unguided local interactions. Furthermore, to achieve this result we leverage powerful results of computational complexity hierarchies, including tight bounds on both best and worst-case complexities of decidable languages, to tailor design systems with precisely controllable space resources available to computations embedded within them. We also develop novel techniques for designing systems containing subsystems with disjoint, mutually exclusive computational powers. The main result will be important in the development of future simulation systems, and the supporting design techniques and lemmas will provide powerful tools for the development of future aTAM systems as well as proofs of their computational abilities.
Damien Woods - One of the best experts on this subject based on the ideXlab platform.
-
the two handed tile Assembly Model is not intrinsically universal
Algorithmica, 2016Co-Authors: Erik D Demaine, Scott M. Summers, Matthew J. Patitz, Trent A. Rogers, Robert T Schweller, Damien WoodsAbstract:The Two-Handed Tile Assembly Model (2HAM) is a Model of algorithmic self-Assembly in which large structures, or assemblies of tiles, are grown by the binding of smaller assemblies. In order to bind, two assemblies must have matching glues that can simultaneously touch each other, and stick together with strength that is at least the temperature $$\tau $$?, where $$\tau $$? is some fixed positive integer. We ask whether the 2HAM is intrinsically universal. In other words, we ask: is there a single 2HAM tile set $$U$$U which can be used to simulate any instance of the Model? Our main result is a negative answer to this question. We show that for all $$\tau ' < \tau $$??Assembly Model is intrinsically universal. On the positive side, we prove that, for every fixed temperature $$\tau \ge 2$$??2, temperature-$$\tau $$? 2HAM tile systems are indeed intrinsically universal. In other words, for each $$\tau $$? there is a single intrinsically universal 2HAM tile set $$U_{\tau }$$U? that, when appropriately initialized, is capable of simulating the behavior of any temperature-$$\tau $$? 2HAM tile system. As a corollary, we find an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. Finally, we show that for each $$\tau $$?, there is a temperature-$$\tau $$? 2HAM system that simultaneously simulates all temperature-$$\tau $$? 2HAM systems.
-
the two handed tile Assembly Model is not intrinsically universal
International Colloquium on Automata Languages and Programming, 2013Co-Authors: Erik D Demaine, Scott M. Summers, Matthew J. Patitz, Trent A. Rogers, Robert T Schweller, Damien WoodsAbstract:In this paper, we study the intrinsic universality of the well-studied Two-Handed Tile Assembly Model (2HAM), in which two "supertile" assemblies, each consisting of one or more unit-square tiles, can fuse together (self-assemble) whenever their total attachment strength is at least the global temperature τ. Our main result is that for all τ′<τ, each temperature-τ′ 2HAM tile system cannot simulate at least one temperature-τ 2HAM tile system. This impossibility result proves that the 2HAM is not intrinsically universal, in stark contrast to the simpler abstract Tile Assembly Model which was shown to be intrinsically universal (The tile Assembly Model is intrinsically universal, FOCS 2012). On the positive side, we prove that, for every fixed temperature τ≥2, temperature-τ 2HAM tile systems are intrinsically universal: for each τ there is a single universal 2HAM tile set U that, when appropriately initialized, is capable of simulating the behavior of any temperature τ 2HAM tile system. As a corollary of these results we find an infinite set of infinite hierarchies of 2HAM systems with strictly increasing power within each hierarchy. Finally, we show how to construct, for each τ, a temperature-τ 2HAM system that simultaneously simulates all temperature-τ 2HAM systems.
-
the two handed tile Assembly Model is not intrinsically universal
arXiv: Computational Geometry, 2013Co-Authors: Erik D Demaine, Scott M. Summers, Matthew J. Patitz, Trent A. Rogers, Robert T Schweller, Damien WoodsAbstract:The well-studied Two-Handed Tile Assembly Model (2HAM) is a Model of tile Assembly in which pairs of large assemblies can bind, or self-assemble, together. In order to bind, two assemblies must have matching glues that can simultaneously touch each other, and stick together with strength that is at least the temperature $\tau$, where $\tau$ is some fixed positive integer. We ask whether the 2HAM is intrinsically universal, in other words we ask: is there a single universal 2HAM tile set $U$ which can be used to simulate any instance of the Model? Our main result is a negative answer to this question. We show that for all $\tau' < \tau$, each temperature-$\tau'$ 2HAM tile system does not simulate at least one temperature-$\tau$ 2HAM tile system. This impossibility result proves that the 2HAM is not intrinsically universal, in stark contrast to the simpler (single-tile addition only) abstract Tile Assembly Model which is intrinsically universal ("The tile Assembly Model is intrinsically universal", FOCS 2012). However, on the positive side, we prove that, for every fixed temperature $\tau \geq 2$, temperature-$\tau$ 2HAM tile systems are indeed intrinsically universal: in other words, for each $\tau$ there is a single universal 2HAM tile set $U$ that, when appropriately initialized, is capable of simulating the behavior of any temperature-$\tau$ 2HAM tile system. As a corollary of these results we find an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. Finally, we show that for each $\tau$, there is a temperature-$\tau$ 2HAM system that simultaneously simulates all temperature-$\tau$ 2HAM systems.
-
The Tile Assembly Model is Intrinsically Universal
2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, 2012Co-Authors: David Doty, Jack H. Lutz, Scott M. Summers, Matthew J. Patitz, Robert T Schweller, Damien WoodsAbstract:We prove that the abstract Tile Assembly Model (aTAM) of nanoscale self-Assembly is intrinsically universal. This means that there is a single tile Assembly system U that, with proper initialization, simulates any tile Assembly system T. The simulation is "intrinsic" in the sense that the self-Assembly process carried out by U is exactly that carried out by T, with each tile of T represented by an m × m "super tile" of U. Our construction works for the full aTAM at any temperature, and it faithfully simulates the deterministic or nondeterministic behavior of each T. Our construction succeeds by solving an analog of the cell differentiation problem in developmental biology: Each super tile of U, starting with those in the seed Assembly, carries the "genome" of the simulated system T. At each location of a potential super tile in the self-Assembly of U, a decision is made whether and how to express this genome, i.e., whether to generate a super tile and, if so, which tile of T it will represent. This decision must be achieved using asynchronous communication under incomplete information, but it achieves the correct global outcome(s).
Jinxiang Dong - One of the best experts on this subject based on the ideXlab platform.
-
Assembly Sequence Planning in VM System
2007 11th International Conference on Computer Supported Cooperative Work in Design, 2007Co-Authors: Weize Zhang, Ruofeng Tong, Jinxiang DongAbstract:Virtual manufacturing (VM) has been proved in different industrial contexts as an effective technology to ensure competitivity and increase profit margins. This paper presents such a system named MEWS, short for module-based extensible integrated VM system. The system now contains 7 modules and owns good extensibility. One of the most important modules is assembling module. It has significant impact on the performance of the system. The adoption of hierarchical Assembly Model with discrete patches brings many benefits for the whole system as well as the assembling module itself. And the hybrid Assembly sequence planning based on subAssembly identification with human-interaction expands the planner's scope of application and enhances its robustness, while restricts human-interaction in hierarchical layers of the Assembly Model.
-
Intelligent virtual Assembly planning with integrated Assembly Model
SMC'03 Conference Proceedings. 2003 IEEE International Conference on Systems Man and Cybernetics. Conference Theme - System Security and Assurance (Ca, 2003Co-Authors: Jinxiang DongAbstract:Based on the comparison and analysis to automated assemble planning and virtual Assembly planning, a new Assembly planning method named Intelligent Virtual Assembly Planning (IVAP) is proposed in this paper. After the main idea of IVAP is introduced, the architecture of the IVAP system, and the structure and functions of the main parts are discussed in detail. Then the paper focuses on the Integrated Assembly Model (IAM), which is the kernel part of the IVAP system and is used to represent different types of Assembly knowledge and data. At last this paper presents the strategy of Multi-Level Intelligent Assembly Planning that is based on IAM.
