Abstract
Running Time and Program Size for Self-assembled Squares?
Leonard Adleman??
University of Oklahoma
Ashish Goel§Stanford University
Ming-Deh Huang?University of Southern California
Pablo Moisset de Espan′e s University of Southern California
University of Southern California
Abstract
Recently Rothemund and Winfree[8]have considered the program size complexity of constructing squares by self-assembly.Here,we consider the time complexity of such constructions using a natural generalization of the Tile Assembly Model de?ned in[8].In the generalized model,the Rothemund-Winfree construction of n×n squares requires timeΘ(n log n)and program sizeΘ(log n).We present a new construction for assembling n×n squares which uses optimal timeΘ(n)and program size
Θ(log n
log log n ).This program size is also optimal since it matches the bound dictated by Kolmogorov
complexity.Our improved time is achieved by demonstrating a set of tiles for parallel self-assembly
of binary counters.Our improved program size is achieved by demonstrating that self-assembling sys-
tems can compute changes in the base representation of numbers.Self-assembly is emerging as a useful
paradigm for computation.In addition the development of a computational theory of self-assembly
promises to provide a new conduit by which results and methods of theoretical computer science might
be applied to problems of interest in biology and the physical sciences.
1Introduction
Self-assembly is the ubiquitous process by which objects autonomously assemble into complexes.Na-ture provides many examples:Atoms react to form molecules.Molecules react to form crystals and supramolecules.Cells sometimes coalesce to form organisms.It has been suggested that self-assembly will ?A preliminary version of this paper appeared in the33rd ACM Symposium on Theory of Computing,2001.
?Professor of Computer Science and Molecular Biology,University of Southern California.Research supported by grants from NASA/JPL,NSF,ONR,and DARPA.Email:adleman@https://www.wendangku.net/doc/7f5243816.html,
?Qi Cheng is at the Department of Computer Science,University of Oklahoma.Research supported by an NSF CAREER award. Email:qcheng@https://www.wendangku.net/doc/7f5243816.html,.
§Ashish Goel is at the Department of Management Science and Engineering and(by courtesy)Computer Science,Stanford University,Terman311,Stanford CA94305.Email:ashishg@https://www.wendangku.net/doc/7f5243816.html,.Research supported by NSF CAREER Award0133968 and a grant from NASA.
?Ming-Deh Huang is at the Department of Computer Science,University of Southern California.Email:huang@https://www.wendangku.net/doc/7f5243816.html,. Research supported in part by a grant from NASA and by NSF Grant CR-9820778.
Pablo Moisset de Espan′e s is at the Department of Computer Science,University of Southern California.Email:pmois-set@https://www.wendangku.net/doc/7f5243816.html,.Research supported in part by a grant from NASA/JPL.
1
ultimately become an important technology,enabling the fabrication of great quantities of intricate objects such as computer circuits from inexpensive components such as DNA and inorganic nanocrystals.Despite its importance,self-assembly is poorly understood.Recently,work related to DNA computation has led to experimental systems for the investigation of self-assembly and its relation to computation[10,6,4,3]. In addition certain theoretical aspects of self-assembly have been considered.Winfree[10,11]proved that self-assembling tile systems in a plane are capable of doing universal computation,and when restricted to a line are exactly as powerful as discrete?nite automata.Adleman[1]proposed a mathematical model of self-assembly and analyzed the time complexity of linear polymerization.Rothemund and Winfree[8] proposed the Tile Assembly Model of self-assembly and studied the program size complexity(the num-ber of different tile-types used)of constructing n×n squares.In this paper we extend the Tile Assembly Model to include the time complexity of the assembly process.We then demonstrate a system of tiles which assembles into an n×n square while simultaneously achieving optimal(Θ(n))time and optimal program size(Θ(log n/log log n)).In contrast,the system proposed by Rothemund and Winfree takes time Θ(n log n)and usesΘ(log n)program-size in the worst case.It is our hope that an understanding of simple self-assembling systems will pave the way for a general theory of self-assembly.
To achieve the improved time complexity,we show how a binary counter that counts from0to n can be assembled in expected timeΘ(n),as opposed to theΘ(n log n)time for the same assembly in the work of Rothemund and Winfree.Further,the assembly time has an exponentially decaying tail.The number of increment steps required to count from0to n is exactly n.Thus our construction takes an amortized time ofΘ(1)for an increment step,even though each increment step requires an addition ofΘ(log n)new tiles.This is made possible by the parallelism inherent in our tile-assembly system.We also observe that no system can result in a square being assembled in expected time less than?(n)in the model suggested by Rothemund and Winfree and expanded by us in this paper.
In order to count to n,a log n-bit counter is required.Most of the?log n)tiles in the construction of Rothemund and Winfree were used to produce the?rst row(the seed row)in the counter.The increment steps in their counter assembly(and in ours)can be performed using a constant number of tiles,and the fully assembled counter,which is roughly a log n×n rectangle can be completed into a square using a con-stant number of tiles.To eliminate the need to produce a seed-row that is log n bits long,we represent the number n in baseΘ(log n/log log n)using onlyΘ(log n/log log n)digits.Thus if the counter were to use baseΘ(log n/log log n)rather than binary,onlyΘ(log n/log log n)tiles would be required to assemble a counter.This observation immediately allows us to reduce the number of tiles(the program size)required to assemble a square toΘ(log n/log log n),which matches the lower bound dictated by Kolmogorov complex-ity.Unfortunately,this program size reduction comes at the cost of increased assembly time.To remedy this, we introduce the notion of base conversion.We start out with a row ofΘ(log n/log log n)tiles representing a number between0and n in baseΘ(log n/log log n).We then convert this number into binary using a self-assembly process that simulates base conversion.Now the counting process can take place in binary, allowing us to achieve the optimal time complexity and optimal program-size complexity simultaneously.
Section2presents a natural extension of the tile-assembly model of Rothemund and Winfree to include the time-complexity of self-assembly.Section3shows how a log n×n counter can be assembled in time Θ(n)and section5explains how base conversion can be simulated in the tile-assembly model.Section6 sketches how an entire n×n square can be constructed using the tools outlined in sections3and5.Section7 describes a more general running time analysis technique.Finally,we present some open problems and conclusions in section8.
2
2Adding time complexity to the Tile Assembly Model
The Tile Assembly Model was originally proposed by Rothemund and Winfree[8].It extends the theoretical model of tiling by Wang[9]to include a mechanism for growth based on the physics of molecular self-assembly.Since self-assembly is an emerging research?eld,there no widely accepted terminology.For this reason the notation we use in this paper is somewhat ad-hoc and may not be appropriate to describe other self-assembly problems such as the combinatorial optimizations presented in[2].
Informally each unit of an assembly is a square with glues of various types on each edge.The tile”?oats”on a two dimensional plane and when two tiles collide they stick if their abutting sides have compatible glues.
Formally,a tile is an oriented unit square with the north,east,south and west edges labeled from some alphabetΣof glues.We begin with a triple T,g,τ where T is a?nite set of tiles,τ∈Z>0is the temperature,and g is the glue strength function fromΣ×Σto N,whereΣis the set of edge labels and N is the set of natural numbers.It is assumed that null∈Σ,g(x,y)=g(y,x)for x,y∈Σ,and g(null,x)=0 for all x∈Σ.For each tile i∈T,the labels of its four edges are denotedσN(i),σE(i),σS(i),andσW(i).
Given p=(x,y),p =(x ,y )∈Z2,we say p and p are position adjacent iff|x?x |+|y?y |=1.
A shape S is a?nite subset of Z2,such that for all pairs of positions p,p in S,either p=p or there exists a sequence of positions p1,p2,···,p n such that p1=p,p n=p and for all1≤k t is the con?guration such thatΓ(x,y) t (i,j)=t iff(i,j)=(x,y)and empty otherwise.Let C and D be two con?gurations. Suppose there exist some i∈T and(x,y)∈Z2such that C(x,y)=empty,D=C except at(x,y), D(x,y)=i,and g(σE(i),σW(D(x+1,y))+g(σW(i),σE(D(x?1,y))+ g(σN(i),σS(D(x,y+1))+g(σS(i),σN(D(x,y?1))≥τ. Then we say that the position(x,y)in C is attachable,and we write C→T D to denote the transition from C to D in attaching tile i to C at position(x,y).Informally,C→T D iff D can be obtained from C by adding a tile to it such that the total strength of interaction in adding the tile to C is at leastτ. A seed con?guration is a con?gurationΓof T such that{p|Γ(p)=empty}is a shape. A tile system is a quadruple T= T,S,g,τ ,where T,g,τare as above and S is a set of seed con?gu-rations called seed s-tiles. We de?ne the notion of a supertile(s-tile in brief)recursively as follows: 1.Every element in S is an s-tile. 2.For t∈T,Γ(x,y) t is an s-tile. 3.if C→T D and C is an s-tile,then D is also an s-tile. From this de?nition,it is clear that for every s-tile A,{p|A(p)=empty}is a shape,and we will call that set the shape of A and we will use the notation[A]to refer to it.Write A→T B for s-tiles A and B iff there exist a∈A and b∈B such that a→T b. Let→?T denote the re?exive transitive closure of→T.A derived supertile of the tile system T is an s-tile such that s→?T A for some s∈S.A terminal supertile of the tile system T is a derived supertile A 3 such that there is no s-tile B,different from A,such that A→?T B.If there is a terminal supertile A such that for any derived supertile B,B→?T A,we say that the tile system uniquely produces A.We also say that for a given shape S,a tile system uniquely produces S iff it uniquely produces some supertile A and [A]=S. Given a tile system T which uniquely produces A,we say that the program size complexity of the system is|T|i.e.the number of tile types. In this paper,we adopt the restriction,suggested by Rothemund and Winfree[8],that S contains a single seed s,and that g(α,β)=0forα,β∈Σwithα=β.For a discussion of the lower bound on program-size in the absence of the latter restriction,see open problem#2in section8.If the seed s consists of a single tile we will say the system is a unit-seed tile system. We now introduce the de?nition of the time complexity of self-assembly.A similar de?nition has also been suggested by Winfree[12].We associate with each tile i∈T a positive probability P(i),such that i∈T P(i)=1.P is called a concentrations function for T.We assume that the tile system has an in?nite supply of each tile,and P(i)models the concentration of tile i in the system–the probability that tile i is chosen when a tile is drawn at random.Now self-assembly of the tile system T corresponds to a continuous time Markov process where the states are in a one-one correspondence with derived s-tiles,and the initial state corresponds to the seed s.There is a transition of state B to C iff B→T C,and the rate of the transition is P(i)if C is obtained from B by adding a tile i.Suppose the tile system uniquely produces an s-tile A T.It would follow that A T is the unique sink state.Given the Markov process,the time for reaching A T from s is a random variable.The time complexity for producing A T from s is de?ned as the expected value of this random variable. Informally our de?nition of time models a system wherein a seed”?oats”in solution encountering tiles at random.The higher the concentration of a particular tile the higher the rate at which it is encountered. When a tile is encountered which has suf?ciently strong interaction with the seed,the tile is incorporated. By this process of accretion the seed grows larger and larger. We say a tile system produces an n×n square iff it uniquely produces a terminal s-tile which is an n×n square of tiles.Then the time complexity of producing an n×n square is the minimum of the time complexity of all the tile systems which produce n×n squares.The following theorem is immediate from our formal model. Theorem2.1The time complexity of producing an n×n square is?(n). 3Counting up to n in timeΘ(n) The square construction of Rothemund and Winfree[8]occurs in two stages.They?rst show how to assemble a log n×n rectangle,and then extend it into an n×n square.To assemble the log n×n rectangle, they simulate a counter that counts from1to n in binary.We are going to use the same general framework, but will replace their counter assembly by a more ef?cient process.In their counter assembly,only one tile is attachable to the assembly at any given time.In our assembly process,several tiles may be attachable at the same time.This“parallelism”allows us to assemble a counter in timeΘ(n)as opposed to theΘ(n log n) assembly time for the counter described by Rothemund and Winfree.We call the process described below the SA-counter. 4 3.1The Tile System We initially assume that n =2K for some positive integer K –we will later show how this assumption can be removed.While each tile is completely speci?ed by its four glues,it is convenient for the purpose of exposition to allow tiles to have labels.Each tile has one main label (either 0or 1)which corresponds to the bit represented by the tile.Further,the east-most zero in a binary number is any is labeled as 0?.The fully assembled counter is going to be a rectangle,with K tiles in each row.Each row represents a number between 0and n –this number can be obtained by reading the main labels on the tiles in the row,with the most signi?cant bit being the westmost in the row.We describe the self-assembly process which results in the counter being incremented. The increment operation uses 8different tiles as well as K special tiles that appear in the seed row only (see Figure 1).The east-most zero in the i th row (auxiliary label 0?)is replaced by a 1-tile in the (i +1)st row.Further,the assembly of the (i +1)th row always starts as the attachment of a 1-tile on top of a 0?-tile.All digits to the east of the east-most zero are replaced by 0-tiles.All digits to the west of the east-most zero are replicated in the new row.If the east-most zero in the i th row is the least signi?cant digit then the position of the west-most zero in the (i +1)st row must be determined by a sequential search running from east to west. We will assume that the temperature for this counter construction is 2.We now describe the tiles in each of the rows and their glues.All tiles occur with the same probability,p SA which is a constant independent of n . 0-tiles:There are the following 0-tiles:0?E ,0?M ,0Z ,0C . 1-tiles:1E ,1M ,1S ,1C . The glues and their strengths are depicted pictorially in ?gure 1. n c s a s s u b s u l u u c c c c n n c z u a n z u z b z l 111* *000C 1M M S 0C Z E E Figure 1:The tiles for the SA-counter.The number of lines jutting from each edge of the tile represent the strength of the bond (1or 2)and the label on the edges represents the glue.Some edges do not have any glues. The label suf?xes indicate the position in the row each row a tile may occupy and or the function in the assembly. E:The tile can be only in the east-most column of the counter. 5 M:The tile cannot be in the east-most column of the counter. Z:Attach a0-tile to the east. C:Copy to the west the digit in the lower row. S:Search to the west for the position of the?rst0-tile in the lower row. The Seed Row:The seed supertile S K is a row of K special tiles. The tile system T SA(K)has a tile set consisting of all the tiles in?gure1.The glue strength function is as indicated in?gure1.The temperature is2,and there is a single seed s-tile S K.We will refer to the Markov chain de?ned by the tile system as the SA-counter.We will assume that all tiles which are not in S K have the same constant probability. We reproduce a de?nition from[7]with minor modi?cations in the terminology to make it consistent with the de?nitions in this paper. Deterministic row-column(RC)property:Let T= T,S,g,τ be a unit-seed tile system and letΓbe a terminal s-tile of T and let S be the shape ofΓ.Let Let w S=min{x|?y s.t.(x,y)∈S},i.e.the x coordinate of the westmost tile.De?ne e S,n S and s S similarly. We sayΓhas the C-property iff the shape ofΓhas no holes and for all w S≤x This theorem,also from[7]will help us to prove correctness of the counter. Theorem3.1If a unit-seed tile system T produces an s-tileΓthat has the Strong RC-property,then T uniquely producesΓ. Theorem3.2The tile system T SA(K)uniquely produces an s-tile which is a K×2K rectangle. Proof:Consider a unit-seed tile system T SA(K)that results from modifying the K special tiles so T can assemble the seed-line starting from the unit seed at the eastmost position.This can be easily accomplished by making all east-west bonds in the seed line of strength2. Clearly,there exists a derivation that assembles the rectangle row by row,i.e.no tile is attached in row before the row below is totally assembled.Further,observe that in that derivation all attachments are deterministic.Therefore,Γhas the Strong RC property,and by Theorem3.1,T SA(K)uniquely produces a K×n rectangle. By contradiction,consider now the original tile system T SA(K)and assume T SA(K)does not produce a K×n rectangle.That would imply T SA(K)does not uniquely produceΓ. Minor modi?cation of the seed row results in a tile system that uniquely produces an s-tile which is a K×n rectangle for any n≤2K. 6 3.2Analysis Our counter construction is more involved than that proposed by Rothemund and Winfree[8]but exploits “parallelism”to speed up the assembly process.The construction of Rothemund and Winfree takes time O(n log n)in the model of running time described in Section2.We show that the SA-counter gets assembled in linear time in Section4).Intuitively,the strongerΘ(n)bound on the assembly time is due to the fact that a row may start getting assembled even before the previous row is completely assembled. In spite of having many possible derivations of the rectangle from the seed row,this particular tile system has a property that makes the analysis of the running time easier.We reproduce the de?nition of partial order systems introduced in[2],with minor adaptations. Assume that we are given a tile system T and a shape S that is uniquely produced by T.Let A denote the s-tile of T that has shape S.Let A(i,j)represent the tile-type at position(i,j).Consider a derivation of A and let t i,j represent the time when the tile at position(i,j)attaches to the growing assembly.De?ne a partial order?on the tile positions in S such that(i,j)?(p,q)iff t i,j≤t p,q for all possible derivations of A using T. De?nition:A tile system T is said to be a partial order system iff it uniquely produces a shape S,and if for all adjacent positions(i,j),(x,y)in S,either(i,j)?(p,q),or(x,y)?(i,j),or the strength of the glues connecting tiles at positions(i,j)and(x,y)is zero. Note that we can represent the partial order relation as a DAG G=(S,E),where(p,q)∈E iff p?q. Figure2depicts the assembly of a SA-counter counting from0to7in binary.The thin arrows indicate the order relation in the process.For a arrow,the position at the tail must be?lled before the position at the head.Intuitively,a long path in the graph suggests long running time because it implies those positions will be?lled sequentially. Lemma3.3The tile system T SA(K)is a partial order system. Proof:For all rows(other than the seed row),the?rst tile to be added to that row is the one on top of the0?tile in the immediately lower row.This is because only tiles labeled as0?have a strength2glue on top.Since there is exactly one0?tile per row,we observe that no tile can attach to the assembly if the tile immediately to the south is not already in place.This gives the north-south order relation.Inside each row,we note that for all positions p to the west of the0?tile,an attachment is impossible if the position immediately to the east of p is empty.Similarly,for all positions p to the east of the0?tile,an attachment is impossible if the position immediately to the east of p is empty.This completes the de?nition of the partial order relation for all pairs of adjacent positions. Let G n be the DAG representing the partial order relation in an SA-counter counting from0to n. Lemma3.4The length of the longest directed path in G n isΘ(n). Proof:Let L be length of the longest path in G n.The longest path is the one containing the most west-east edges.There is exactly one path containing all of them.It is the path containing all the vertices corresponding to the0?labeled tiles.Any path going from the bottom row to the top row will traverse exactly n?1north-south edges,hence L=?(n).The number of west-east and east-west edges traversed is easily bounded by adding the distance from the east-most zero to the east-most column for all rows. 7 001M C 11M 1M *0R * 01R *0R 1R 1R *0R 1R C 1C 1C 1 C 1 0M * C 0 C 0M *0 Z 0M *Seed row Figure 2:Graph representing the assembly of a counter.The dashed line encloses the seed row.The thin arrows indicate the order relation.The thick arrows represent the edges added to construct an Equivalent Acyclic graph. L ≤n ?1+ k j =1(k ?j )×2j and n ?1+ k j =1(k ?j )×2j ≤n +k k ?1i =0i 2k ?i ≤n (1+ ∞i =0i 2?i )=O (n ) Theorem 3.5The time complexity for building an SA-counter that counts from 0to n is Θ(n ). We will present the proof of Theorem 3.5at the end of Section 4after we develop some more machinery.4Running time Analysis. For the purpose of our analysis,we transform the self-assembly process into another process which we call the “sentinel”process.The sentinel process does not adhere to the model described in Section 2;in fact there does not seem to be an easy implementation of the sentinel process.However,the sentinel process is more amenable to analysis,and the time for this process to complete is an upper bound (in the stochastic domination sense)on the completion time for the self-assembly process. Given a directed graph G =(V,E )and vertices v,v in V ,we say v is a predecessor of v iff (v,v )∈E .Given a vertex v ,we de?ne the predecessors of v in G ,and we denote it as P red G (v ),to be the set of all vertices v such that v is a predecessor of v . 8 Equivalent Acyclic Graph(EAG):Let T= T,S,g,τ be a tile system that uniquely produces some s-tileΓ,and let G=(V,E)be a DAG.G is an Equivalent Acyclic Graph(EAG)for T iff: 1.V=[Γ]. 2.G has exactly one source. 3.For all edges(p,p )∈E,p is position-adjacent to p . 4.Letσbe the seed s-tile.For all p∈[Γ]?[σ],for all derived s-tilesΓ of T,if P red G(p)?[Γ]and p∈[Γ ],thenΓ(p)is attachable toΓ at p. Note that for a given T there may exist more than one EAG. Lemma4.1For all tile systems T that uniquely produce an s-tile,there exists an EAG. Proof:LetΓbe the terminal s-tile produced by T,letσbe the seed s-tile and let n be the size of[Γ]?[σ]. Consider one arbitrary derivation ofΓand the graph G=(V,E)constructed in the following way:For 1≤i≤n call p i the position where the i th attachment occurs.De?ne V=[Γ],E1={(p i,p j)|i To complete the proof,we have to verify that G is an EAG.We start by proving G is a DAG.Because of the way we constructed it,there cannot be a cycle in G .We observe that all edges in E1connect vertices in[Γ]?[σ],that all edges in E b go from a vertex in[σ]to a vertex in[Γ]?[σ]and that all edges in E s connect elements in[σ].Therefore,there cannot be a path from a vertex in[Γ]?[σ]to[σ].There are not cycles in G ,so if there is a cycle in G it must contain exclusively elements in[Γ]?[σ].By the de?nition of E1this is clearly impossible,hence G is a DAG.Now we prove that G has exactly one source,i.e.the one in[σ].We claim that there cannot be a source in[Γ]?[σ]:Assume there is one and let p i be that vertex.If there is a vertex p∈[σ]such that p i and p are position-adjacent then,by de?nition of E b,p i has an incoming edge and is not a source.Now consider the case when there is not such a p.Because of the de?nition of E1we know that for all all outgoing edges(p i,p j),i To verify the last condition of the de?nition of EAG,we simply observe that E was obtained from an actual derivation. In the previous proof we used a derivation of the s-tile to construct a suitable EAG.We say that the EAG was induced by the derivation. Sentinel process:Let T= T,S,g,τ be a tile system that uniquely produces an s-tile,letΓbe that s-tile, let P be a concentrations function for T,let G be a EAG for T and let g s be the source of G.Let S be the set of all subgraphs G =(V ,E )of G such that g s∈V and for all edges(p,p )∈V,(p,p )∈E iff p,p ∈V . We de?ne S T,G,P to be the continuous time Markov process such that: 9 1.Each state in S T,G,P corresponds to a graph in S. 2.There is a transition from state s to s in S T,G,P iff the corresponding subgraphs G =(V ,E ) and G =(V ,E )are such that V ?V is a singleton and E ?E ={(u,v)|v∈V ?V and u∈P red G(v)}. 3.The probability associated with a transition from s to s is P(v),where v is de?ned as before. Note that S T,G,P has exactly one source state,corresponding to the source of G,and exactly one sink state,corresponding to G.We de?ne the completion time for the sentinel process as the time to go from the source state to the sink state.Intuitively,the sentinel process is obtained by modifying the self-assembly process by deleting some transitions in it,i.e.disallowing some bonds to form.This elimination of tran-sitions will make the completion time of the sentinel process an upper bound for the running time of the self-assembly process. Completion time for the sentinel process:Consider a tile system T that uniquely produces an s-tile,and a concentrations function P for T,and let c=min i(P(i)),i.e.the smallest concentration.Let G be an EAG for T and let L be the length of the longest directed path in G.Let t be the completion time for S T,G,P. Lemma4.2E[t]=O(L/c).Further,t has an exponentially decaying tail. Proof:Let P1,P2,...P N represent the N directed paths from the seed to any sink in the sentinel graph.At each step in any path,the edge must go to a position-adjacent vertex and there are at most three candidates. Therefore N is at most3L≤e2L.Let S l denote the sum of all X i,j such that position(i,j)lies on path P l.Then the completion time t=max n l=1S l.S l is the sum of at most L mutually independent exponential variables,each with mean less or equal to1/c.Hence E[S l]≤L/c;letφdenote the value L/c.Clearly φ=O(L/c).Using Chernoff bounds for exponential variables[5],it follows that Pr[S l>φ·(1+δ)]≤((1+δ)/eδ)L.Hence Pr[t>φ(1+δ)]≤N((1+δ)/eδ)L≤e2L((1+δ)/eδ)L=((1+δ)/eδ?2)L.Let us chooseδ=δ +4,whereδ >0.Now Pr t>5φ(1+δ ) ≤Pr t>φ(1+4+δ ) ≤((1+δ )/eδ )L. This clearly gives an exponential tail bound.Now, E[t]≤5·φ(1+ ∞δ =0((1+δ )/eδ )L dδ ), which is O(L/c)asφ=O(L/c)and the integral is bounded by a constant for any value of L≥1. Stochastic dominance:De?ne t i,j to be the time at which the(i,j)position gets?lled in the original self-assembly process and t i,j to be the time at which it gets?lled in the sentinel process.If(i,j)is in the shape of the seed s-tile then assume t i,j=0.Note that t i,j and t i,j are random variables.Let t and t be the 10 random variables denoting the times at which the original self-assembly process and the sentinel assembly complete. A real valued random variable A is said to be stochastically dominated by another random variable B, denoted A≤sd B,if for all x,Pr[A>x]≤Pr[B>x]. Lemma4.3For all(i,j)in the shape of the uniquely produced s-tile,t i,j≤sd t i,j Proof:LetΓbe the s-tile produced by T Let X i,j be an exponential random variable with mean 1/P(Γ((i,j))),i.e.the reciprocal of the probability associated with the tile at position(i,j)in the?nal s-tile.Let all the X i,j be independent.A tile attaches at position(i,j)in the self-assembly X i,j time after this position becomes attachable1.We couple the sentinel process and the self-assembly process by setting the values of X i,j to be the same for both processes.De?ne a i,j and a i,j to be the times at which tile position (i,j)is attachable in the self-assembly process and the sentinel process,respectively.Let t be the earliest time when a tile gets attached in the sentinel process but is still unattached in the self-assembly process.Let (i,j)be this tile position.Clearly,a i,j Lemma4.3in conjunction with the lemma4.2now allows us to conclude: Theorem4.4E[t]=O(L/c).Further,t has an exponentially decaying tail. Consider a unit-seed tile system T that uniquely produces a s-tile,and a constant valued concentrations function C for T.Let c be the value of C. Theorem4.5There exists an EAG G for T such that the time complexity of T isΘ(L/c). Proof:LetΓbe the terminal s-tile of T,and let t be the time complexity of T.Consider an experiment, i.e.the assembly ofΓfrom the seed.Let?t be the completion time of the experiment. De?ne p1=Pr ?t≤2t .Clearly,E[?t]=t and by Markov’s inequality p1≥1/2. Let?G be the EAG induced by the experiment,that can be constructed as we shown in the proof of Theorem4.1.Let?L be the length of the longest directed path in?G.De?ne p2=Pr ?L/(4c)≥?t .We will now show that p2<1/4. De?neβ=x1+x2+ (x) L where the x i s are independent exponential random variables with mean 1/https://www.wendangku.net/doc/7f5243816.html,ing the fact that exponential variables are the inter-arrival times of Poisson events we get: Pr β≤?L/(4c) =Pr ρ(?L/4)≥?L whereρ(?L/4)is a Poisson variable with mean?L/https://www.wendangku.net/doc/7f5243816.html,ing Markov inequality again,we obtain Pr ρ(?L/4)≥?L ≤1/4p,hence Pr β≤?L/(4c) ≤1/4.Sinceβ≤sd?t we conclude that Pr ?L/(4c)≥?t ≤1/4. 1This fact follows from the fact that once a tile position becomes attachable it remains attachable till it actually attaches. 11 Since p1>p2,it must be the case that Pr ?L/(4c)≤?t∧?t≤2t =0.Therefore,there must exist a derivation that induces an EAG G such that L/(4c)≤2t and hence t=?(L/c),where L is the length of the longest directed path in G.From Theorem4.3we know that t=O(L/c),completing the proof. For completeness,we state the following lemma of trivial proof that gives a lower bound on the time-complexity of a partial order system.Let T be a partial-order system and let G be the DAG describing the partial order relation. Lemma4.6For all concentrations functions P for T,the time complexity of T is?(L) Theorem3.5can be obtained immediately from Lemma3.4,Lemma4.6,and Theorem4.5.We present the details below. Proof of Theorem3.5:Let G be the acyclic graph representing the partial order relation in the counter. Lemma3.4states that the longest path in G hasΘ(n)length.TheΘ(n)running time follows from The-orem4.5.A suitable EAG is G,augmented with all edges of the form((x+1,y),(x,y)),where both (x+1,y)and(x,y)are in the seed row,and with edges of the form((x,y),(x,y+1)),where(x,y)’s are in the seed row,(see Fig2).It’s easy to see that the length of the longest directed path in the augmented graph is stillΘ(n).To prove the time complexity is?(n),we simply invoke Lemma4.6. 5Simulating base conversion by self-assembly. In Rothemund and Winfree’s construction(and in ours),the“seed row”represents a number written in binary and consists of log n tiles,each encoding0or1.The number is used as the starting point for a counter.Since we are only allowed a seed s-tile consisting of a single tile,this seed row itself needs to be assembled from a single tile.Each tile in the seed row needs to be distinct,and therefore the program size complexity for assembling the seed row itself is?(log n).On the other hand,Kolmogorov complexity dictates the program size complexity to be?(log n log log n ).In order to achieve the Kolmogorov bound,we could use a”seed row”to represent a number written base b,where b is power of2such that log n log log n ≤b=2k< 2log n log log n , for k a positive integer.Then the number of tiles to construct the seed row will be h=log n log b < log n log log n?log log log n =O( log n log log n ). As in Rothemund and Winfree[8]’s counting scheme,we could use the“seed row”as a starting point for a counter.If we use the counting strategy of Rothemund and Winfree,modi?ed to count base b,we easily achieve the optimal program size complexity or in the language of Rothemund and Winfree: Theorem5.1K2SA(N)=O(log N log log N ). Unfortunately if we simply follow Rothemund and Winfree[8]’s method,we pay a price in time com-plexity.The Rothemund and Winfree construction begins with the seed row and grows through a succession 12 of s-tiles to produce a?nal rectangle.But for each s-tile produced in the process,there is exactly one tile which can be incorporated.There are at least b=Θ(log n log log n )distinct tiles which occur?(n)times in the ?nal rectangle,and at least one of these tiles must have probability O(log log n log n ).It follows that such tiles require?(n log n log log n )time for assembling of the rectangle.In particular,the time is not linear.Even using the parallel construction described in section3,the time is not improved. To overcome this time problem while preserving the O(log n log log n )program size,we adopt the strategy of writing a”seed column”base b and then converting it to base2,forming a seed row for a counter.We then employ the fast parallel counter described in section3. In the conversion part,we will employ some tiles,which have the capability to perform division-by-2. These tiles have glues representing binary strings.The north glue represents last bit,the west glue represents the pre?x substring and the east glue represents the string itself.See Figure5(A)for the tile associated with the string0110,and Figure5(B)for cooperation of two tiles.We assume that the temperature is3,but it is not hard to see that the same idea also works for temperature2 . (A) Convert one bit. (B) Convert two bits. (C) Convert 031 in base 4 to 001101 in base 2. Figure3:Converting base by self-assembly. In the following tile descriptions,we identify a tile by the labels on its four sides:North(N),West(W), East(E)and South(S),and a title symbol(TS).In our notations,a pre?x“(2)”indicated a glue with strength 2,a pre?x“(3)”indicated a glue with strength3.The absence of pre?x indicates glue with strength1. Suppose we want to convert b1···b h in base b to binary base number,where b i if written in binary would be b i,1b i,2···b i,k.The set of tiles consists of 13 1.(Seed.)These tiles will form a seed column.For each b i,1b i,2···b i,k,1≤i≤h, TS:(b i,1b i,2···b i,k)s N:if i W:if i=h,(3)b h,1b h,2···b h,k,else b i,1b i,2···b i,k. 2.(division by2.)For each binary string a1a2···a i,1≤i≤k, TS:(a1a2···a i)d, N:(2)a i,E:(3)a1a2···a i, W:if i≥2,(3)a1a2···a i?1,otherwise x2, S:if i≥2,(2)x1,otherwise(2)x3. 3.(Base b copy.)For each binary string a1a2···a k, TS:(a1a2···a k)c, N:(2)x1,W:a1a2···a i,E:a1a2···a i,S:(2)x1. 4.(Last b copy tile.)For each binary string a1a2···a k, TS:(a1a2···a k)C? N:(2)x3,W:(3)a1a2···a i,E:a1a2···a i,S:(2)x1. 5.(Base2copy.)For a=0or1, TS:a x;N:(2)a;E:x2;S:(2)a;W:x2. Note that the east side of the seed tiles,the south side of the?rst seed tile and the north side of the last seed tile are not assigned with any glues.They are open for later use.Even if those glues are all different, the number of distinct tiles is not increased. Figure5(C)is an example showing how to convert string031in base4to string001101in base2. In item2,we use the most distinct tiles.which is b+b 2 + b 4 +···1<2b=O( log n log log n ). Thus the number of distinct tiles in this conversion subroutine is O(log n log log n ).Every tile appears at most O(log n)times.We can arrange that each tile has probability greater than?(log2n n log log n ),in which case,the time to do the conversion is at most O(n). 6Putting it all together The self-assembly of an n×n square begins with a seed tile which grows into a seed column consisting of roughly b=Θ(log n log log n )tiles representing a number m written base b.This seed row spawns a base 14 B a s e c o n v e r s i o n I n i t i a l B i n a r y C o u n t e r R o w B i n a r y C o u n t e r Base b Seed Line Figure 4:Constructing a square by self-assembly. 15 conversion assembly as outlined in section5The result is a rectangle with top row representing m written base2.This top row becomes the starting point for a binary counter assembly as outlined in section3. The height of the resulting counter rectangle is a function H of m.H satis?es H(m+1)=H(m)+ 3.Hence by selecting an appropriate m,the base conversion assembly and the counter assembly have dimensions such that height plus width equals n?e,where e=0,1or2.We can grow e extra rows at the base of the combined rectangle to bring the sum of the two dimensions exactly up to n.The resulting rectangle acts as the basis for the completion of the n×n square as described in[8]using diagonal elements and?ller tiles.Figure4describes this process pictorially. Let T n be the variant of the tile system described above that assembles an n×n square.Note that only the seed row and base conversion tiles have to be adjusted to specify n.The tiles to build the square,the diagonal and the?ller tiles do not depend on n. Theorem6.1For all positive integers n,there is a concentration functions P n for T n such that T n assem-bles an n×n square in O(n)time.Further,for all concentrations functions P n for T n,the square assembles in?(n)time. Proof: T n is a partial-order system.We can use the DAG describing the partial-order relation as EAG.We claim he length of the longest directed path in the DAG isΘ(n),since by Lemma3.4the longest path in the counter is of lengthΘ(n),the total number of positions in the seed columns and base conversion is O(log2(n)/log log(n)),and the longest path in the rest of the square is of lengthΘ(n).By allocating a combined probability of1/5to the tiles constructing the seed row,1/5to the tiles which perform the base conversion,1/5to the tiles which perform the counter construction,1/5to the diagonal elements and1/5 to the?ller tiles,it follows from Theorem4.4that the time to construct the n×n square is O(n).By Lemma4.6the time complexity is?(n). 7Bounding running time of a self assembly process In section3.2we constructed the equivalent acyclic graph based on the partial order relation existing among the times to?ll every position of the counter.The technique is not always applicable.There are self-assembly processes that do not exhibit the partial order relation.We present in this section a different parallel counter that is not a partial order system and we will show how to bound the time to complete its assembly. The fully assembled counter is going to be a rectangle,with K tiles in each row.Each row represents a number between0and n–this number can be obtained by reading the main labels on the tiles in the row, with the most signi?cant bit being the west-most in the row.We describe the self-assembly process which results in the counter being incremented. The increment operation happens in three stages and uses15different tiles(see?gure5).We start with an“INERT”row(each tile carries the auxiliary label“I”).This row gets replicated into an“ACTIVE”row (auxiliary label“A”)if and only if there is at least one0-tile in the original INERT row.If all the tiles in the INERT row are1-tiles,the counter construction can not proceed any further and the self-assembly process terminates.A“CARRY”row(auxiliary label“C”)then assembles on top of the ACTIVE row. 16 The bulk of the increment operation happens during this step.The CARRY row will represent the value of the ACTIVE row incremented by one,except that the 0-tile (if any)which needs to change to a 1-tile due to a carry propagation is still unchanged.Then an INERT row assembles on top of the CARRY row which will convert such a tile (if any)to a 1-tile.The east-most tile in any row always carries the auxiliary label “R”along with the auxiliary label corresponding to the row.Some tiles may also be marked special (auxiliary label “S”)to aid in the carry propagation.Even though the above description seems serial,the SA-counter need not assemble row-by-row;several different tiles (possibly belonging to different rows)may be attachable at the same time. We will assume that the temperature for this counter construction is 3.We now describe the tiles in each of the rows and their glues.All tiles occur with the same probability,p SA which is a constant independent of n . INERT tiles:There are the following INERT tiles:0L ,1L ,0LE ,1LE ,0LL ,1LL . ACTIVE tiles:0L ,1L ,0LE ,1LE . CARRY tiles:0L ,1L ,0LL ,0LE ,1LE .The glues and their strengths are depicted pictorially in ?gure 5. ACTIVE TILES CARRY TILES INERT TILES Figure 5:The tiles for the SA-counter.The number of lines jutting from each edge of the tile represent the strength of the bond (1,2,or 3)and the label on the edges represents the glue.Some edges do not have any glues. Assembling ACTIVE rows:Notice that starting with an INERT row that consists of all 1-tiles,no ACTIVE tiles can attach to the top of the row since all possible bonds are of strength 2whereas the temperature is 3.However,all 0-tiles in the INERT row can allow ACTIVE 0-tiles to attach on top through bonds of strength 3.These newly attached ACTIVE 0-tiles provide strength 1bonds that supplement the strength 2bonds between ACTIVE 1-tiles and INERT 1-tiles,allowing ACTIVE 1-tiles to attach in positions adjacent to the already attached ACTIVE 0-tiles.The newly attached ACTIVE 1-tiles in turn provide strength 1bonds that allow adjacent ACTIVE 1-tiles to attach on top of INERT 1-tiles,and so on.This allows the entire INERT row to be replicated into an ACTIVE row. Assembling CARRY rows:Notice that any 0-tiles (except the east-most)in the ACTIVE row allow a CARRY 0-tile to attach on top by means of bonds of strength 3.These tiles then allow CARRY 17 1-tiles to attach on the west through bonds of strength1,which in turn allow more CARRY1-tiles to attach on the west.Notice that CARRY0-tiles do not provide any glues on the east and therefore can not facilitate attachment of CARRY1-tiles to their east.This allows most of the ACTIVE row to replicate into the CARRY row–we just need to bother about the east-most tile and those ACTIVE 1-tiles that do not have an ordinary ACTIVE0-tile to their east.We will now consider two cases depending on the east-most tile in the ACTIVE row.If the east-most tile in the ACTIVE row is a 0-tile then it will allow a east-most CARRY1-tile to attach on its top through a bond of strength3. This then provides a bond of strength1to its west which will allow ACTIVE1-tiles to assemble to its west,thus completing the CARRY row.Notice that this CARRY row already represents the correct result for the increment operation.If the east-most tile is an ACTIVE1-tile,then it allows a east-most CARRY0-tile to attach on top.This tile then allows special CARRY0-tiles(and not CARRY1-tiles) to bond to its west on top of the ACTIVE1-tiles.Thus the entire sequence of contiguous ACTIVE 1-tiles on the east will have special CARRY0-tiles attached on top.The CARRY row now represents the correct result for the CARRY operation with one exception:the ACTIVE0-tile which was im-mediately to the west of the east-most sequence of ACTIVE1-tiles has a CARRY0-tile attached on top,whereas the increment operation should convert it into a1-tile due to carry propagation.This is remedied in the next step. Assembling INERT rows:The0-tile which needs to be changed into a1-tile can be“detected”as a CARRY0-tile which has a special CARRY0-tile or a east-most CARRY0-tile to its immediate east. The description for the assembly of the INERT row is simple.All the tiles except ordinary CARRY 0-tiles can attach an INERT tile(with the other labels such as the bit-label,the east-most label,and the special label remaining the same)on top.Now special INERT0-tiles and east-most INERT0-tiles allow a special INERT1-tile to attach(on top of a CARRY0-tile)to their west,while all other INERT tiles allow an INERT0-tile to attach.This accomplishes the desired carry propagation and completes the increment process. The Seed Row:The seed s-tile S K is a row of K special tiles.The east-most tile in S K is identical to the tile0LE except that the bottom surface has no glue.The other K?1tiles are identical to the tile0L except that there is no glue on the bottom surfaces2. The tile system T SA(K)has a tile set consisting of all the tiles in?gure5as well as the special tiles needed in the s-tile S K.The glue strength function is as indicated in?gure5.The temperature is3,and there is a single seed s-tile S K.We will refer to the Markov chain de?ned by the tile system as the SA-counter. We will assume that all tiles which are not in S K have the same constant probability. The next theorem follows from our description of the tile system,and we omit the proof. Theorem7.1The tile system T SA(K)uniquely produces an s-tile which is a K×(3·2K?2)rectangle. Minor modi?cation of the seed row results in a tile system that uniquely produces an s-tile which is a K×n rectangle for any n≤3·2K?2. 2In this section we are using s-tiles consisting of more than one tile as the seed,whereas our restricted model allows us to use only s-tiles with a single tile as seed.We rectify this in section6. 18 The equivalent acyclic graph:Look at a completed self assembly,and replace each bond by two directed bonds,one in each direction.Each directed bond has the same strength as the original bidirected bond. Then,remove all the directed bonds that satisfy any of the following criteria: 1.The bond goes from a higher to a lower row. 2.The bond goes from west to east in a non-ACTIVE row. 3.The bond goes from west to east in an ACTIVE row,and there is at least one zero-tile to the east of the origin of the bond. 4.The bond goes from east to west in an ACTIVE row,and the destination tile of the bond is a zero-tile. 5.The bond goes from east to west in an ACTIVE row,the source and destination tiles are both one-tiles, and there are no zero-tiles to the east of the source. We can de?ne an equivalent graph as the graph with vertices corresponding to the tiles,and directed arcs corresponding to the directed bonds and labeled by the strength.The following lemma is immediate from our construction. Lemma7.2The sentinel graph is acyclic. The sentinel process is a Markov chain obtained by modifying the Markov chain corresponding to the SA-counter as follows.We consider each transition in the Markov chain for the SA-counter.Let this transition correspond to adding a new tile X to an s-tile A.A tile Y in A is said to be a support tile if it shares a side with X and there is an arc from Y to X in the sentinel graph;the strength of this arc is said to be the support strength from Y.We retain this transition if the sum of the support strengths from the support tiles is greater than the temperature and else we discard it.Any state in the Markov chain that is unreachable from the source state is discarded. Intuitively,the sentinel process is formed by taking the SA-counter and introducing a“sentinel”who disallows transitions that require bond-formation from the west to the east,except when such transitions are necessary for replication.It is not dif?cult to see that the sentinel process produces exactly the same complete assembly as the SA-counter. In the sentinel graph,there is exactly one bond that goes from the west-most column to the east,and this happens just above the INERT row011...11where the west-most0is the only tile that can“self-replicate”into the active row and must then induce the1-tiles to attach to its east.Further,this property is recursively satis?ed if we remove the west-most column and look at the sentinel graphs for the two sub-rectangles below and above the011...11row.This recursive structure makes the sentinel process more amenable to analysis. The structure of the sentinel graph is illustrated in?gure6. 8Conclusions and open problems We have generalized the Tile Assembly Model of Rothemund and Winfree[8]to include time complexity and have demonstrated a tile system for self-assembling n×n squares that is optimal in both time and pro-gram size.The long term goal of this research is the development of a mathematical-computational theory 19 G(4)13G(8)G(4)Figure 6:The recursive structure of the sentinel graph. 20 [Title of Paper] [Student Name] [School] [Course/Number] April 13, 2013 [Instructor Name] Abstract (if needed)[replace] [According to the Publication Manual of the American Psychological Association (APA), “An abstract is a brief, comprehensive summary of the contents of the article; it allows readers to survey the contents of an article quickly and, like a title, it enables persons interested in the document to retrieve it from abstracting and indexing databases” (2010, p. 25). The first line of the abstract is not indented. An abstract may range from 150 to 250 words (APA, 2010). Because an abstract is not always required for student papers, adhere to your instructor’s requirements. ] Uppaal4.0:Small Tutorial? 16November2009 1Introduction This document is intended to be used by newcomers to Uppaal and veri?cation.Students or engineers with little background in formal methods should be able to use Uppaal for practical purposes after this tutorial. Section2describes Uppaal and Section3is the tutorial itself. 2Uppaal Uppaal is a tool box for validation(via graphical simulation)and veri?cation(via automatic model-checking)of real-time systems.It consists of two main parts:a graphical user interface and a model-checker engine.The user interface is implemented in Java and is executed on the users work station.Version4.0of Uppaal requires that the Java Runtime Environment5or higher is installed on the computer.The engine part is by default executed on the same computer as the user interface,but can also run on a more powerful server. The idea is to model a system using timed automata,simulate it and then verify properties on it.Timed automata are?nite state machines with time(clocks).A system consists of a network of processes that are composed of locations.Transitions between these locations de?ne how the system behaves.The simulation step consists of running the system interactively to check that it works as intended.Then we can ask the veri?er to check reachability properties,i.e.,if a certain state is reachable or not.This is called model-checking and it is basically an exhaustive search that covers all possible dynamic behaviours of the system. More precisely,the engine uses on-the-?y veri?cation combined with a symbolic technique re-ducing the veri?cation problem to that of solving simple constraint systems[YPD94,LPY95].The veri?er checks for simple invariants and reachability properties for e?ciency reasons.Other prop-erties may be checked by using testing automata[JLS96]or the decorated system with debugging information[LPY97]. 3Learning Uppaal Uppaal is based on timed automata,that is?nite state machine with clocks.The clocks are the way to handle time in Uppaal.Time is continuous and the clocks measure time progress.It is allowed to test the value of a clock or to reset it.Time will progress globally at the same pace for the whole system. A system in Uppaal is composed of concurrent processes,each of them modeled as an automa-ton.The automaton has a set of locations.Transitions are used to change location.To control when to take a transition(to“?re”it),it is possible to have a guard and a synchronization.A guard is a condition on the variables and the clocks saying when the transition is enabled.The synchronization mechanism in Uppaal is a hand-shaking synchronization:two processes take a ?This description covers version4.0.7 Java中的abstract方法和abstract类的问题 当知道一个类的子类将不同的实现某个方法时，把该类声明为抽象类很有用，可以共用相同的父类方法，不必再定义。 抽象类和抽象方法的关系:含有抽象方法的类一定是抽象类，抽象类里不一定含有抽象方法。抽象类存在的意义是用来被继承的。一个类继承了一个抽象类，必须实现抽象类里面所有的抽象方法，否则，此类也是抽象类。 abstract修饰符用来修饰类和成员方法 1：用abstract修饰的类表示抽象类，抽象类位于继承树的抽象层，抽象类不能被实例化。2：用abstract修饰的方法表示抽象方法,抽象方法没有方法体。抽象方法用来描述系统具有什么功能，但不提供具体的实现。 abstract 规则： 1：抽象类可以没有抽象方法，但是有抽象方法的类必须定义为抽象类，如果一个子类继承一个抽象类，子类没有实现父类的所有抽象方法，那么子类也要定义为抽象类，否则的话编译会出错的。 2：抽象类没有构造方法，也没有抽象静态方法。但是可以有非抽象的构造方法 3：抽象类不能被实例化，但是可以创建一个引用变量，类型是一个抽象类，并让它引用非抽象类的子类的一个实例 4：不能用final 修饰符修饰 Q:java里面有抽象类么？和接口的区别是什么？ A:java中有抽象类,用关键字abstract修饰。 以下是我对这个问题的看法。 首先，从语法上讲，抽象类是一个类，根据java的单继承体系。如果它有子类，那么它的 子类只能继承它。 java允许实现多个接口。所以一个类可以实现多个接口 抽象类里面可以定义各种类型和访问权限的变量(就像普通类一样)，也可以定义各种访问权限的方法(就像普通类一样)。 但是接口不可以。在接口里面定义的方法默认就是public abstract的，变量默认就是public static final的。(不管你有没有加权限控制符，不加，默认就是这些权限；加错了，权限缩小了，那么就会报错) 其次，从意义上讲，如果继承一个抽象类，那么抽象类和它的子类就有父子关系，即有类的层次关系(这关系到类的设计问题)。 接口，在我看来，是一种契约或者协议，是一层提供给另一层的接口(可以想象成OSI各层之间的关系) 在某一层中有多个类协作实现这个层的功能，通过接口暴露出去。但这些类之间会有层次关系(is a,has a) Q:一个方法加abstract和不加abstract有什么区别？就是说不加有什么关系？加了又会怎样？ A:一方法要是加abstract，那么这个方法就是抽象的，须由子类去实现 抽象方法必须在抽象类当中，也就是说，一个类只要有一个方法是抽象的，那么这个类就必须是抽象类 抽象类里面的方法不一定要抽象的，也可以全都不是抽象的 抽象类不能实例化！ 所以可以想到，当你不想让你的类被别人实例化，只想这个类的子类可以实例化，那么只要将这个类声明为abstract的就可以了 一、研究生必备四本 俗话说好记性不如烂笔头，所以一定要首先养成做笔记的好习惯！作为研究生下面这几个本子是必不可少的。 1，实验记录本（包括试验准备本），这当然首当其冲必不可少，我就不多说了； 2，Idea记录本，每次看文献对自己有用的东西先记下，由此产生的idea更不能放过，这可是做研究的本钱，好记性不如烂笔头，以后翻翻会更有想法的； 3，专业概念以及理论进展记录本，每个人不可能对自己领域的概念都了如指掌，初入门者更是如此，这时候小小一个本子的作用就大了； 4，讲座记录本，这本本子可能有些零杂，记录听到的内容，更要记录瞬间的灵感，以及不懂的地方，不可小视！ 这四本是你必不可少的，不过作为我们这些非英语专业的研究生来说，还有一个应该具备的本子就是英语好句记录本。 二、论文写作要点 1、选题要小，开掘要深；不要题目很大，内容却很单薄。 2、写作前要读好书、翻阅大量资料、注意学术积累，在这个过程中，还要注重利用网络，特别是一些专业数据库 3、“选题新、方法新、资料新”的三新原则（老板教导的） 4、“新题新做”和“小题大做 总之，一点之见即成文。 三、如何撰写实验研究论文（唐朝枢） 论文发表意识：基础研究成果的表达方式；是否急于发表（创新与严谨的关系）；发表的论文与学位论文的区别（反映科学事实而不是反映作者水平） 论文格式：原著 original research paper, full length paper、review综述论文，快报、简报、摘要。不同于教科书、讲义，更不同于工作总结。 撰写前的准备工作：复习和准备好相关文献;再次审定实验目的(学术思想,Idea);实验资料完整并再次审核 1.Introduction:引言 问题的提出；研究的现状及背景；以前工作基础；本工作的目的；思路（可提假说）；对象；方法；结果。在…模型上，观察…指标，以探讨…（目的） 文摘要求 对于科技期刊的文章，论文的 abstract 主要由三部分组成，即：研究的问题、过程和方法、结果。 文摘只有写得正确，写的好，才能起到帮助读者了解原文的作用。因此必须对文献进行认真的主题分析， 找出文献的主题概念， 正确地组织好这些主题内容， 简明准确完整地写出文摘来。 文摘长度一般不超过 150 words 。少数情况下允许例外，视原始文献而定。在不遗漏主题概念的前提下，文摘应尽量简洁。 （一）.缩短文摘方法: 1.取消不必要的字句：如 ”t is reported here ”、 “new ”、 “ mainly ” 也尽量不要。 2. 对物理单位及一些通用词可以适当进行简化; 3. 取消或减少背景信息（ Background Information ）; 4. 不说无用的话，如“本文所谈的有关研究工作是对过去老工艺的一个极大的改进” ， “本工作首次实现了 …” “经检索尚未发现与本文类似的文献”等词句切不可进入文摘; 5. 作者在文献中谈及的未来计划不纳入文摘； 6. 文摘第一句应避免与题目（Title ）重复。 7. 尽量简化一些措辞和重复的单元，如： （二）.文体风格 1. 文摘叙述要完整，清楚，简明； 2. 尽量用短句子并避免句形单调； 3. 用过去时态叙述作者工作，用现在时态叙述作者结论； 如 “The structure of dislocation cores in GaP was investigated by weak-beam electron microscopy. The dislocations are dissociated into two Shokley partials with separations of 80 edge and screw cases respectively. The results show that... __________________________________ ” 可直接用名词或名词短语作定语的情况下，要少用 of 句型。 例如： 用 Thick ness of plastic sheets was measured. 不用 Measurement of thickness of plastic sheet was made. 注意冠词用法，不要误用，滥用或随便省略冠词。 避免使用一长串形容词或名词来修饰名词，可以将这些词分成几个前置短语，用连字符连接名词 组，作为单位形容词（一个形容词） 。 如应用 The chlorine-containing propylene-based polymer of high meld index. 代替 The chlorine containing high melt index propylene based polymer. 尽量用主动语态代替被动语态； 尽量用简短、词义清楚并为人熟知的词; 10?慎用行话和俗语; " Exte nsive in vestigati ons show that 'The author discusses ” This paper concerned with …”；一些不必要的修饰词，如“ in detail ”、“ briefly ±10 and 40 ±10 A in the pure 能用名词做定语不要用动名词做定 语， 例如：用 measurement accuracy 用 experimental results 能用形容词做定语就不要用名词做定语。 不用 measuri ng accuracy 不用 experime nt results 例女口 用 measurement accuracy 不用 accuracy of measureme nt 用 camera curtain shutter 不用 curta in shutter of camera 用 equipment structure 不用 structure of equipme nt 5. 可用动词的情况尽量避免用动词的名词形式; 6 . 8. 9. A4 Paper Size Format for RFIT (Title in 18-point Times font) 1st Author1,2, 2nd Author2, 3rd Author1,2 (List authors on this line using 12 point Times font) 1Name of first affiliation, City, State/Region, Mail/Zip Code, Country 2Name of second affiliation, City, State/Region, Mail/Zip Code, Country (authors' affiliation(s) listed here in 12 point Times font) Email: contact.author@https://www.wendangku.net/doc/7f5243816.html, Abstract — Use 9 point Times New Roman Bold font for the abstract. Set your line spacing to be 10 points rather than single space. Indent the first line by 0.125 inches and type the word "Abstract" in 9 point Times New Roman Bold Italic. This should be followed by two spaces, a long dash (option / shift / minus), two spaces, and then the first word of your abstract (as shown above). Please try to keep the length of your abstract to 100 words or less. Times font is an acceptable substitute for Times New Roman font. After the abstract, you should list a few key words from the IEEE approved “Index Terms” LIST that describe your paper. The index terms are used by automated IEEE search engines to quickly locate your paper. Typically, you should list about 5 to 7 key words, in alphabetical order, using 9 point Times New Roman Bold font. An example is shown next. Index Terms — Ceramics, coaxial resonators, delay filters, delay-lines, power amplifiers. I. I NTRODUCTION Please read through this entire template before you start using it to create your paper! This will save you and the RFIT Committee considerable time, and improve your chances for acceptance. The following information is provided to help you prepare the Initial Submission as well as the Final Paper for submission to RFIT. (Many authors submit the same paper for the initial as well as the final submission. This is a common practice. See item #4 below.) A contributor should remember that: 1) Deadlines are absolute, don't even ask! 2) Summaries may not exceed four pages, including all figures, tables, references, etc. Additionally, there is a size limit on the electronic version of all Summaries. In Adobe Portable Document Format (PDF), submissions may not exceed 1 Megabyte. 3) Acceptance rates have historically run at approx-imately 50%. There is not sufficient room within the Technical Program to accept all submissions. 4) Many submitters with previous experience realize that, if their submission is accepted, they will be required to submit a version of their Final Paper to be published in the Symposium Digest. As the Digest paper will be similar in length to the Summary, many contributors opt to prepare their Summary in the format required for the Digest. This template contains the instructions for the proper preparation of such a document. 5) Although not required, you are encouraged to employ this format. This document is being made available as a template for your convenience. If you elect not to use this template, please remember that you must still adhere to the general guidelines embodied in this document concerning, but not limited to, font size, margin size, page limits, file size, etc. (Note: Starting in 2004, Index Terms are required.) II. O VERVIEW OF THE D IGEST F ORMAT We are requesting that you follow these guidelines as closely as possible so that the Digest has a professional look and resembles the MTT Transactions. All paragraphs of text, including the abstract, figure captions, and refer-ences, should be justified at the left and the right edges. For the Title use 18-point Times (Roman) font. Its paragraph description should be set so that the line spacing is single with 6-point spacing before and 6-point spacing after (Format --> Paragraph --> Indents and Spacing). The font description for the Author List and Authors' Affiliation(s) should be 12-point Times. The paragraph descriptions should be set so that the line spacing is single with 6-point spacings before and after. Use an additional line spacing of 12 points before the beginning of the double column section, as shown above. III. D ETAILED T EXT F ORMATTING Using 210 x 297-mm (8.27 x 11.69-inch) A4 paper, the top and bottom margins are 31.75-mm (1.25 inches), and the left and right margins are 19-mm (0.75 inches). Except for Title, Authors and Affiliations, use a double column format. The column width is 83-mm (3.27 inches) and the column spacing is 5.8-mm (0.23 inch). Each major section begins with a Heading in 10 point Times font centered within the column and numbered using Roman numerals (except for A CKNOWLEDGEMENT and R EFERENCES), followed by a period, a single space, and the title using an initial capital letter for each word. The remaining letters are in SMALL CAPITALS. The paragraph description of the section heading line should be set for 18 points before, 6 points after, and the line spacing should be set to exactly 12 points. 第34卷第6期 唐山师范学院学报 2012年11月 Vol.34 No.6 Journal of Tangshan Teachers College Nov. 2012 ────────── 收稿日期：2012-03-25 作者简介：申丽红（1975-），女，河北邯郸人，博士研究生，讲师，研究方向为理论语言学及语言教学。 -24- 语言学中的研究方法 申丽红1,2 （1. 中国传媒大学 文学院，北京 100021；2. 河北联合大学 外国语学院，河北 唐山 063000） 摘 要：语言学作为社会科学和自然科学的交叉学科，近年来有了长足的发展。各家学者秉承不同的语言学理论，采用不同的研究方法对语言进行了多方位的研究。本文从语言学理论的不同发展阶段对语言学研究方法做一梳理。 关键词：语言学；定量研究；定性研究 中图分类号： H 0-05 文献标识码： A 文章编号：1009-9115(2012)06-0024-03 Some Research Methods of Linguistics SHEN Li-hong 1,2 (1. College of Liberal Arts, The Communication University of China, Beijing 100021, China; 2. College of Foreign Languages, Hebei United University, Tangshan 063000, China) Abstract: Linguistics, as a cross-discipline between natural and social science, has developed well in recent years. Different scholars did some researches on language with different theories and from different angles. A summary about the research methods of linguistics is made. Key Words: linguistics; quantitative research; qualitative research 语言是人类特有的宝贵财产，是人类社会生活的重要组成部分。随着社会发展，文明进步，人们开始从不同角度探索语言的奥秘，以揭示形形色色的言语背后所隐藏的规律，从而形成了林林总总的语言学流派和语言学理论。 任何一门学科的研究方法对于一门学科的发展都是至关重要的。在语言学发展的不同阶段，不同的语言学流派以不同的哲学基础建立起自己的理论框架后，因其学科发展的不同时期以及不同的研究目的而选用不同的研究方法来进行语言学相关研究。 一、语言学发展简史 西方的语言学研究自古希腊始，希腊著名的哲学家苏格拉底（Socrates, BC 470-BC 399），柏拉图（ Plato, BC 429-BC 347）和亚里士多德（Aristotle, BC 384- BC322）等通过对语言的辩论奠定了语言研究的哲学基础。此后语言学在西方历经中世纪、文艺复兴以及19世纪历史比较语言学的发展，随着一些人类学家、哲学家等相继加入语言学研究，语言学学科迅速发展。他们详细研究了语言的分类， 语言中的音变等，为现代语言学的诞生奠定了坚实的基础。 20世纪初，瑞士语言学家索绪尔提出的普通语言学理论使语言学真正成为了一门科学的学科。此后的布拉格学派、哥本哈根学派以及美国的结构主义学派基本上秉承了结构主义的衣钵，对语言的结构、音位等进行了详细的描写和切分。 20世纪50年代，乔姆斯基（Noam Chomsky ）提出了转换生成语法（Transformational-Generative Grammar ）。转换生成语法彻底颠覆了传统的结构主义语法，推动语言学研究进入当代语言学时期。乔姆斯基认为人类获得语言的过程无论采用“白板说”还是“刺激-反应”论都不足以说明问题，以此提出了“先天性假设”（innateness hypothesis ）。他认为人类的大脑先天被内置了一套“普遍语法”（universal grammar ）或“语言普遍现象”（linguistic universals ）。这种普遍语法在后天经验的触发下而形成各种各样的“个别语法”（particular grammar ）。语言学家的任务就是运用数学的运算原理，运用各种规则逐步推导以 Writing: Abstract WHAT IS AN ABSTRACT 1. The Definition of an Abstract 1 ) the objectives and scope of investigation; 2) the methods used; 3) the most important results; 4) conclusion or recommendation. 2. Features of Abstracts Brevity Accuracy Specificity Objectivity Informativeness Independency CLASSIFICATION OF ABSTRACTS 1.Indicative Abstracts https://www.wendangku.net/doc/7f5243816.html,rmative Abstracts https://www.wendangku.net/doc/7f5243816.html,rmative-indicative Abstracts 4.Other Types of Abstracts 1) Critical Abstracts 2) Mini-abstracts FUNCTIONS OF ABSTRACTS A Screening Device of Documents: An abstract gives readers the idea of what the article is about. A Self-contained Text: We’ll know the information it contains, without seeing the article . A Helpful Preview: It "frames" the article and prepares the reader for the main points to come. To Facilitate Indexing: It will improve the chances of having it read by the right people. STYLISTIC FEATURES OF ABSTRACTS 1. The Length of Abstracts 1) In general, there is a 100-300 word limit to the number of words in an abstract. 2) Do not confuse an abstract with a review. There should be no comment or evaluation. 3) Give information only once. 4) Do not repeat the information given in the title. 5) Do not include any facts or ideas that are not in the text. 6) For informative abstracts, include enough data to support the conclusions. 7) If reference to procedure is essential, try to restrict it to identification of method or process. 8) State results, conclusions, or findings in clear concise fashion. 9) Organize the information in the way that is most useful to the reader. (a thesis-first abstract) 2. Verbs and Tenses Used in Abstracts 1) Active verbs: use active verbs rather than passive verbs. 2) Present tense: background information, existing facts, what is in the paper and conclusion. 3) Past tense /present perfect tense: completed research, methodology or major activities results. 3. Words Used in Abstracts 1) Avoid use of highly specialized words or abbreviations. Define unfamiliar words. 2) Synthesize or rephrase the information into clear, concise statements. 3) Avoid using jargon. 4. Sentence Structures of Abstracts 1) Use third person sentences. 2) Use short sentences, but vary sentence structure. 3) Use complete sentences. 4) The first sentence should present the subject and scope of the report. The thesis or the writer's focus should be presented in the second sentence. The balance of the article is a summary of the important points of each section, including methods, procedures, results and conclusions. 5) Good abstracts are sure to include a variety of pat phrases: a. Background Information (Research has shown... It has been proposed... Another proposed property... The search is on for... One of the promising new...) b. Statement of the Problem (The objective of the research is to prove / verify... The experiment was designed to determine...) e. Statement of Procedure (To investigate this .... A group of 10 specimens / subjects ... Measurements TOPSIS分析方法研究 摘要 本文主要介绍了TOPSIS分析方法理论及其主要思想，运用数学理论，对其算法进行了详细的分析，并指出原始方法存在的优缺点；在此基础上提出了一种改进的TOPSIS分析方法，给出具体求权重的方法，突出其客观公正性.本文还分析了TOPSIS方法逆序产生的原因及其改进的方法，突出其实用性，推广其应用范围. 关键词TOPSIS法; 改进的TOPSIS; 权重；逆序 TOPSIS ANALYSIS METHOD ABSTRACT This paper describes a method of theory—TOPSIS, and its main idea. Using mathematical theory, its algorithm for a detailed analysis and noted the advantages and disadvantages of the original methods. On this base ,an improved TOPSIS method is given, and specific for weight, in order to highlight its objective impartiality. The paper also analyzes the causes of TOPSIS Reverse and its improved methods, highlight its practicality and the promotion of its use. Keywords TOPSIS method; Improved TOPSIS; weight; Reverse 摘要的分类 1．陈述性摘要(descriptive abstract) 只说明（陈述）论文的主题，不介绍论文的具体内容 Sample 1 Translation is not only a linguistic transference, but also an intercultural communication. For quite a long time, translation studies have been concentrated on the prescription of translation methods, with scant attention paid to the description of macro-cultural factors involved in the translating. In this paper, the writer contends that the study of the macro-cultural factors will surely enlarge the scope and enrich the content of the translation studies. The paper is largely a rudimentary step, both in theory and in practice, to expose some of the factors influencing Mr. Fu’s translation of Gone with the Wind, with a historic and descriptive approach employed. Sample 2 To the general public, China English is a relatively new and serious concept, while in the fields of linguistics and translation a group of scholars have already make a study on it. Now most scholars hold that China English, based on the standard English, is a kind of variant of English to express things and concepts with Chinese characteristic. It is the product of the English language used in English-speaking countries combined with the unique Chineseness. Then, in the nation of China with a thousand-long history and civilization, how has China English come into being, grown and developed? This paper mainly focuses on the factors involved in the emergence and development of China English and it also explores people’s attitude toward China English, and analyzes the trend and role of China English in China and the world. 2．资料性/信息性摘要(informative abstract) 除了说明论文的主题外，还要介绍论文的主要观点、主要内容和研究成果Sample 3 This paper, based on the theories and principles of psycholinguistics and cognitive psychology, deals with definitions and functions of emotional quotient, revealing some of the learners’ emotional characteristics, which affect the outcome of language learning. The author insists that language learning is a very sophisticated psychological process, and aspects of emotional quotient influence the learner’s cognitive process in which knowledge of the target language is internalized as language competence or skills. Results of experiments prove that positive and rich emotions are the motives needed for language learning. It is vital for language teachers to motivate their students to acquire the target language by developing their emotions and helping them internalize what they are learning. The author also mentions that language teachers should recognize the potential for creating a warm and friendly environment for language learning so that language teaching and learning process will be more effective in improving the learner’s IQ, EQ, and language creative ability. Sample 4 In order to help students with their translation and assist teachers to find students’main problems with translation, this paper studies an English to Chinese国外写作APA详细模板
UPPAAL建模工具教程
Java中的abstract方法和abstract类的问题
学术论文写作的要点范文
论文的Abstract写法
英文论文模板
语言学中的研究方法
Abstract Writing (论文摘要写作精简版)
TOPSIS方法研究讲解
英语 论文 Abstract