A Hybrid GLR Algorithm for Parsing with Epsilon Grammars

We give a hybrid algorithm for parsing epsilon grammars based on Tomita's non-ϵ-grammar parsing algorithm ([Tom86]) and Nozohoor-Farshi's ϵ-grammar recognition algorithm ([NF91]). The hybrid parser handles the same set of grammars handled by Nozohoor-Farshi's recognizer. The algorithm's details and an example of its use are given. We also discuss the deployment of the hybrid algorithm within a GB parser, and the reason an ϵ grammar parser is needed in our GB parser.

Iterative Linearized Density Matrix Propagation for Modeling Coherent Energy Transfer in Photosynthetic Light Harvesting

We present results of calculations [1] that employ a new mixed quantum classical iterative density matrix propagation approach (ILDM , or so called Is‐Landmap) [2] to explore the survival of coherence in different photo synthetic models. Our model studies confirm the long lived quantum coherence , while conventional theoretical tools (such as Redfield equation) fail to describe these phenomenon [3,4]. Our ILDM method is a numerical exactly propagation scheme and can be served as a bench mark calculation tools[2]. Result get from ILDM and from other recent methods have been compared and show agreement with each other[4,5]. Long lived coherence plateau has been attribute to the shift of harmonic potential due to the system bath interaction, and the harvesting efficiency is a balance between the coherence and dissipation[1]. We use this approach to investigate the excitation energy transfer dynamics in various light harvesting complex include Fenna‐Matthews‐Olsen light harvesting complex[1] and Cryptophyte Phycocyanin 645 [6]. [1] P.Huo and D.F.Coker ,J. Chem. Phys. 133, 184108 (2010) . [2] E.R. Dunkel, S. Bonella, and D.F. Coker, J. Chem. Phys. 129, 114106 (2008). [3] A. Ishizaki and G.R. Fleming, J. Chem. Phys. 130, 234111 (2009). [4] A. Ishizaki and G.R. Fleming, Proc. Natl. Acad. Sci. 106, 17255 (2009). [5] G. Tao and W.H. Miller, J. Phys. Chem. Lett. 1, 891 (2010). [6] P.Huo and D.F.Coker in preparation

Small-World Internet Topologies: Possible Causes and Implications on Scalability of End-System Multicast

Recent work has shown the prevalence of small-world phenomena [28] in many networks. Small-world graphs exhibit a high degree of clustering, yet have typically short path lengths between arbitrary vertices. Internet AS-level graphs have been shown to exhibit small-world behaviors [9]. In this paper, we show that both Internet AS-level and router-level graphs exhibit small-world behavior. We attribute such behavior to two possible causes–namely the high variability of vertex degree distributions (which were found to follow approximately a power law [15]) and the preference of vertices to have local connections. We show that both factors contribute with different relative degrees to the small-world behavior of AS-level and router-level topologies. Our findings underscore the inefficacy of the Barabasi-Albert model [6] in explaining the growth process of the Internet, and provide a basis for more promising approaches to the development of Internet topology generators. We present such a generator and show the resemblance of the synthetic graphs it generates to real Internet AS-level and router-level graphs. Using these graphs, we have examined how small-world behaviors affect the scalability of end-system multicast. Our findings indicate that lower variability of vertex degree and stronger preference for local connectivity in small-world graphs results in slower network neighborhood expansion, and in longer average path length between two arbitrary vertices, which in turn results in better scaling of end system multicast.

A Hierarchical Characterization of a Live Streaming Media Workload

We present what we believe to be the first thorough characterization of live streaming media content delivered over the Internet. Our characterization of over five million requests spanning a 28-day period is done at three increasingly granular levels, corresponding to clients, sessions, and transfers. Our findings support two important conclusions. First, we show that the nature of interactions between users and objects is fundamentally different for live versus stored objects. Access to stored objects is user driven, whereas access to live objects is object driven. This reversal of active/passive roles of users and objects leads to interesting dualities. For instance, our analysis underscores a Zipf-like profile for user interest in a given object, which is to be contrasted to the classic Zipf-like popularity of objects for a given user. Also, our analysis reveals that transfer lengths are highly variable and that this variability is due to the stickiness of clients to a particular live object, as opposed to structural (size) properties of objects. Second, based on observations we make, we conjecture that the particular characteristics of live media access workloads are likely to be highly dependent on the nature of the live content being accessed. In our study, this dependence is clear from the strong temporal correlations we observed in the traces, which we attribute to the synchronizing impact of live content on access characteristics. Based on our analyses, we present a model for live media workload generation that incorporates many of our findings, and which we implement in GISMO [19].