This HTML5 document contains 38 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n11http://localhost/temp/predkladatel/
n10http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n4http://linked.opendata.cz/resource/domain/vavai/projekt/
n7http://linked.opendata.cz/ontology/domain/vavai/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n17http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F47813059%3A19240%2F09%3A%230002978%21RIV10-GA0-19240___/
n14http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n15http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n16http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n8http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n18http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n12http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n13http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F47813059%3A19240%2F09%3A%230002978%21RIV10-GA0-19240___
rdf:type
n7:Vysledek skos:Concept
dcterms:description
A systematic study of self-assembly as a mathematical process has been initiated by L. Adleman and E. Winfree. The individual components are modeled as square tiles on the infinite two-dimensional plane. In this paper we focus on a special type of structure, called a ribbon: a non-self-crossing rectilinear semence of tiles on the plane, in which successive tiles are adjacent along an edge and abutting edges of consecutive tiles have matching glues. We prove that it is undecidable whether an arbitrary finite set of tiles with glues (infinite supply of each tile type available) can be used to assemble an infinite ribbon. Our result settles an open problem formerly known as the “unlimited infinite snake problem.” A systematic study of self-assembly as a mathematical process has been initiated by L. Adleman and E. Winfree. The individual components are modeled as square tiles on the infinite two-dimensional plane. In this paper we focus on a special type of structure, called a ribbon: a non-self-crossing rectilinear semence of tiles on the plane, in which successive tiles are adjacent along an edge and abutting edges of consecutive tiles have matching glues. We prove that it is undecidable whether an arbitrary finite set of tiles with glues (infinite supply of each tile type available) can be used to assemble an infinite ribbon. Our result settles an open problem formerly known as the “unlimited infinite snake problem.”
dcterms:title
The undecidability of the infinite ribbon problem: implications for computing by self-assembly The undecidability of the infinite ribbon problem: implications for computing by self-assembly
skos:prefLabel
The undecidability of the infinite ribbon problem: implications for computing by self-assembly The undecidability of the infinite ribbon problem: implications for computing by self-assembly
skos:notation
RIV/47813059:19240/09:#0002978!RIV10-GA0-19240___
n3:aktivita
n8:P
n3:aktivity
P(GA201/06/0567)
n3:cisloPeriodika
6
n3:dodaniDat
n13:2010
n3:domaciTvurceVysledku
n10:3180328
n3:druhVysledku
n12:J
n3:duvernostUdaju
n15:S
n3:entitaPredkladatele
n17:predkladatel
n3:idSjednocenehoVysledku
347568
n3:idVysledku
RIV/47813059:19240/09:#0002978
n3:jazykVysledku
n16:eng
n3:klicovaSlova
self-assembly; infinite snake problem; undecidability
n3:klicoveSlovo
n14:self-assembly n14:infinite%20snake%20problem n14:undecidability
n3:kodStatuVydavatele
US - Spojené státy americké
n3:kontrolniKodProRIV
[E84831EEC06E]
n3:nazevZdroje
SIAM J. on Computing
n3:obor
n18:IN
n3:pocetDomacichTvurcuVysledku
1
n3:pocetTvurcuVysledku
5
n3:projekt
n4:GA201%2F06%2F0567
n3:rokUplatneniVysledku
n13:2009
n3:svazekPeriodika
38
n3:tvurceVysledku
Sosík, Petr Kari, Lila
s:issn
0097-5397
s:numberOfPages
25
n11:organizacniJednotka
19240