@article{3867, abstract = {Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages L that assign to each word w a real number L(w). In the case of infinite words, the value of a run is naturally computed as the maximum, limsup, liminf, limit-average, or discounted-sum of the transition weights. The value of a word w is the supremum of the values of the runs over w. We study expressiveness and closure questions about these quantitative languages. We first show that the set of words with value greater than a threshold can be omega-regular for deterministic limit-average and discounted-sum automata, while this set is always omega-regular when the threshold is isolated (i.e., some neighborhood around the threshold contains no word). In the latter case, we prove that the omega-regular language is robust against small perturbations of the transition weights. We next consider automata with transition weights 0 or 1 and show that they are as expressive as general weighted automata in the limit-average case, but not in the discounted-sum case. Third, for quantitative languages L-1 and L-2, we consider the operations max(L-1, L-2), min(L-1, L-2), and 1 - L-1, which generalize the boolean operations on languages, as well as the sum L-1 + L-2. We establish the closure properties of all classes of quantitative languages with respect to these four operations.}, author = {Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A}, journal = {Logical Methods in Computer Science}, number = {3}, pages = {1 -- 23}, publisher = {International Federation for Computational Logic}, title = {{Expressiveness and closure properties for quantitative languages}}, doi = {10.2168/LMCS-6(3:10)2010}, volume = {6}, year = {2010}, } @article{3868, abstract = {Simulation and bisimulation metrics for stochastic systems provide a quantitative generalization of the classical simulation and bisimulation relations. These metrics capture the similarity of states with respect to quantitative specifications written in the quantitative mu-calculus and related probabilistic logics. We first show that the metrics provide a bound for the difference in long-run average and discounted average behavior across states, indicating that the metrics can be used both in system verification, and in performance evaluation. For turn-based games and MDPs, we provide a polynomial-time algorithm for the computation of the one-step metric distance between states. The algorithm is based on linear programming; it improves on the previous known exponential-time algorithm based on a reduction to the theory of reals. We then present PSPACE algorithms for both the decision problem and the problem of approximating the metric distance between two states, matching the best known algorithms for Markov chains. For the bisimulation kernel of the metric our algorithm works in time O(n(4)) for both turn-based games and MDPs; improving the previously best known O(n(9).log(n)) time algorithm for MDPs. For a concurrent game G, we show that computing the exact distance be tween states is at least as hard as computing the value of concurrent reachability games and the square-root-sum problem in computational geometry. We show that checking whether the metric distance is bounded by a rational r, can be done via a reduction to the theory of real closed fields, involving a formula with three quantifier alternations, yielding O(vertical bar G vertical bar(O(vertical bar G vertical bar 5))) time complexity, improving the previously known reduction, which yielded O(vertical bar G vertical bar(O(vertical bar G vertical bar 7))) time complexity. These algorithms can be iterated to approximate the metrics using binary search}, author = {Chatterjee, Krishnendu and De Alfaro, Luca and Majumdar, Ritankar and Raman, Vishwanath}, journal = {Logical Methods in Computer Science}, number = {3}, pages = {1 -- 27}, publisher = {International Federation for Computational Logic}, title = {{Algorithms for game metrics}}, doi = {10.2168/LMCS-6(3:13)2010}, volume = {6}, year = {2010}, } @inproceedings{3782, abstract = {In cortex surface segmentation, the extracted surface is required to have a particular topology, namely, a two-sphere. We present a new method for removing topology noise of a curve or surface within the level set framework, and thus produce a cortical surface with correct topology. We define a new energy term which quantifies topology noise. We then show how to minimize this term by computing its functional derivative with respect to the level set function. This method differs from existing methods in that it is inherently continuous and not digital; and in the way that our energy directly relates to the topology of the underlying curve or surface, versus existing knot-based measures which are related in a more indirect fashion. The proposed flow is validated empirically.}, author = {Chen, Chao and Freedman, Daniel}, booktitle = {Conference proceedings MCV 2010}, location = {Beijing, China}, pages = {31 -- 42}, publisher = {Springer}, title = {{Topology noise removal for curve and surface evolution}}, doi = {10.1007/978-3-642-18421-5_4}, volume = {6533}, year = {2010}, } @article{3789, abstract = {The development of multicellular organisms is dependent on the tight coordination between tissue growth and morphogenesis. The stereotypical orientation of cell divisions has been proposed to be a fundamental mechanism by which proliferating and growing tissues take shape. However, the actual contribution of stereotypical division orientation (SDO) to tissue morphogenesis is unclear. In zebrafish, cell divisions with stereotypical orientation have been implicated in both body-axis elongation and neural rod formation [1, 2], although there is little direct evidence for a critical function of SDO in either of these processes. Here we show that SDO is required for formation of the neural rod midline during neurulation but dispensable for elongation of the body axis during gastrulation. Our data indicate that SDO during both gastrulation and neurulation is dependent on the noncanonical Wnt receptor Frizzled 7 (Fz7) and that interfering with cell division orientation leads to severe defects in neural rod midline formation but not body-axis elongation. These findings suggest a novel function for Fz7-controlled cell division orientation in neural rod midline formation during neurulation. }, author = {Quesada-Hernández, Elena and Caneparo, Luca and Schneider, Sylvia and Winkler, Sylke and Liebling, Michael and Fraser, Scott and Heisenberg, Carl-Philipp J}, journal = {Current Biology}, number = {21}, pages = {1966 -- 1972}, publisher = {Cell Press}, title = {{Stereotypical cell division orientation controls neural rod midline formation in zebrafish}}, doi = {10.1016/j.cub.2010.10.009}, volume = {20}, year = {2010}, } @article{22446, abstract = {By partitioning mass and energy fluxes, soil moisture exerts a fundamental control on basin hydrological response. Using the design characteristics of the Biosphere 2 hillslope experiment, this study investigates aspects of soil moisture spatial and temporal variability in a zero‐order catchment of a semiarid climate. The hydrological response of the domain exhibits a particular structure, which depends on whether topography‐induced subsurface stormflow is triggered. The occurrence of the latter is conditioned by topography, soil depth, and pre‐storm spatial distribution of moisture. As a result, a non‐unique behavior of soil moisture spatial heterogeneity emerges, manifested through a hysteretic dependence of variability metrics on mean water content. Further, it is argued that vegetation dynamics impose a “homogenizing” effect on pre‐storm moisture states, decreasing the likelihood that a rainfall event will result in topographic redistribution of soil water. Consequently, post‐rainfall soil moisture dynamics associated with the effect of topography that could lead to the enhancement of spatial heterogeneity are suppressed; a potential “attractor” of catchment states emerges. The study thus proposes several hypotheses that will be testable within the framework of long‐term hillslope experiments.}, author = {Ivanov, Valeriy Y. and Fatichi, Simone and Jenerette, G. Darrel and Espeleta, Javier F. and Troch, Peter A. and Huxman, Travis E.}, issn = {1944-7973}, journal = {Water Resources Research}, number = {9}, publisher = {American Geophysical Union}, title = {{Hysteresis of soil moisture spatial heterogeneity and the “homogenizing” effect of vegetation}}, doi = {10.1029/2009wr008611}, volume = {46}, year = {2010}, }