BibSonomy publications for /user/vittorio.loretoMon Apr 19 09:07:17 CEST 2010HardcoverJanuaryAlgorithms on strings, trees, and sequences : computer science and computational biology20072007 biology computational gusfield sequences strings trees 15{Traditionally an area of study in computer science, string algorithms have, in recent years, become an increasingly important part of biology, particularly genetics. This volume is a comprehensive look at computer algorithms for string processing. In addition to pure computer science, Gusfield adds extensive discussions on biological problems that are cast as string problems and on methods developed to solve them. This text emphasizes the fundamental ideas and techniques central to today's applications. New approaches to this complex material simplify methods that up to now have been for the specialist alone. With over 400 exercises to reinforce the material and develop additional topics, the book is suitable as a text for graduate or advanced undergraduate students in computer science, computational biology, or bio-informatics.}Sat Apr 03 18:39:08 CEST 2010in press in Molecular Biology and EvolutionA Stochastic Local Search algorithm for distance-based phylogeny reconstruction20102010 caglioti loreto pagnani phylogenesis sbix tria In many interesting cases the reconstruction of a correct phylogeny is blurred by high mutation rates and/or horizontal transfer events. As a consequence a divergence arises between the true evolutionary distances and the differences between pairs of taxa as inferred from available data, making the phylogenetic reconstruction a challenging problem. Mathematically this divergence translates in a loss of additivity of the actual distances between taxa. In distance-based reconstruction methods, two properties of additive distances were extensively exploited as antagonist criteria to drive phylogeny reconstruction: on the one hand a local property of quartets, i.e., sets of four taxa in a tree, the four-points condition; on the other hand a recently proposed formula that allows to write the tree length as a function of the distances between taxa, the Pauplin's formula. Here we introduce a new reconstruction scheme, that exploits in a unified framework both the four-points condition and the Pauplin's formula. We propose, in particular, a new general class of distance-based Stochastic Local Search algorithms, which reduces in a limit case to the minimization of the Pauplin's length. When tested on artificially generated phylogenies our Stochastic Big-Quartet Swapping algorithmic scheme significantly outperforms state-of-art distance-based algorithms in cases of deviation from additivity due to high rate of back mutations. A significant improvement is also observed with respect to the state-of-art algorithms in case of high rate of horizontal transfer. Sat Apr 03 18:21:46 CEST 2010Kolmogorov’s Legacy about Entropy, Chaos, and Complexity 20032003 complexity compression entropy falcioni kolmogorov legacy loreto physics vulpiani Sat Apr 03 16:04:50 CEST 2010An Introduction to Kolmogorov Complexity and Its Applications19971997 applications complexity kolmogorov li vitanyi Thu Apr 01 14:24:10 CEST 2010Cambridge, MA, USAArtif. Life2129--143Effects of compression on language evolution620002000 compressione evolution language taylor teal Thu Apr 01 14:20:32 CEST 2010Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science-{Pictish symbols revealed as a written language through application of Shannon entropy}20102010 entropy jonathan language lee pictish shannon symbols ziman Many prehistoric societies have left a wealth of inscribed symbols for which the meanings are lost. For example, the Picts, a Scottish, Iron Age culture, left a few hundred stones expertly carved with highly stylized petroglyph symbols. Although the symbol scripts are assumed to convey information, owing to the short (one to three symbols), small (less than 1000 symbols) and often fragmented nature of many symbol sets, it has been impossible to conclude whether they represent forms of written language. This paper reports on a two-parameter decision-tree technique that distinguishes between the different character sets of human communication systems when sample sizes are small, thus enabling the type of communication expressed by these small symbol corpuses to be determined. Using the technique on the Pictish symbols established that it is unlikely that they are random or sematographic (heraldic) characters, but that they exhibit the characteristics of written languages. Thu Apr 01 14:17:16 CEST 2010Science59311165-{Entropic Evidence for Linguistic Structure in the Indus Script}32420092009 adhikari entropy indus joglekar language mahadevan rao script structure vahia yadav The script of the ancient Indus civilization remains undeciphered. The hypothesis that the script encodes language has recently been questioned. Here, we present evidence for the linguistic hypothesis by showing that the script's conditional entropy is closer to those of natural languages than various types of nonlinguistic systems. Thu Apr 01 14:01:50 CEST 2010Trends in Cognitive Sciences18 - 11Why is conversation so easy?820042004 conversation dialogue garrod language pickering Thu Apr 01 13:50:25 CEST 2010Nature Reviews GeneticsJune405-415Human language as a culturally transmitted replicator1020092009 cultural dynamics language pagel phylogenesis phylogeny Thu Apr 01 13:23:36 CEST 2010Cambridge, EnglandThe rise and fall of languages19981998 bursts dixon evolution fall languages phylogenesys punctuation rise Thu Apr 01 11:02:48 CEST 2010PaperbackmayUsing Language19961996 clark language using Herbert Clark argues that language use is more than the sum of a speaker speaking and a listener listening. It is the joint action that emerges when speakers and listeners, writers and readers perform their individual actions in coordination, as ensembles. In contrast to work within the cognitive sciences, which has seen language use as an individual process, and to work within the social sciences, which has seen it as a social process, the author argues strongly that language use embodies both individual and social processes.Wed Mar 31 19:20:06 CEST 2010New York, NY, USAHCOMP '09: Proceedings of the ACM SIGKDD Workshop on Human Computation29--30TurKit: tools for iterative tasks on mechanical Turk20092009 mechanical tools turk Wed Mar 31 19:16:34 CEST 2010Cognitive Science5737--767An Experimental Study of the Emergence of Human Communication Systems2920052005 communication emergence experiments galantucci language The emergence of human communication systems is typically investigated via 2 approaches with complementary strengths and weaknesses: naturalistic studies and computer simulations. This study was conducted with a method that combines these approaches. Pairs of participants played video games requiring communication. Members of a pair were physically separated but exchanged graphic signals through a medium that prevented the use of standard symbols (e.g., letters). Communication systems emerged and developed rapidly during the games, integrating the use of explicit signs with information implicitly available to players and silent behavior-coordinating procedures. The systems that emerged suggest 3 conclusions: (a) signs originate from different mappings; (b) sign systems develop parsimoniously; (c) sign forms are perceptually distinct, easy to produce, and tolerant to variations.Wed Mar 31 19:14:34 CEST 2010PNASmay187361--7366The emergence of simple languages in an experimental coordination game10420072007 coordination emergence experimental languages selten simple warglien 1We investigate in a series of laboratory experiments how costs and benefits of linguistic communication affect the emergence of simple languages in a coordination task when no common language is available in the beginning. The experiment involved pairwise computerized communication between 152 subjects involved in at least 60 rounds. The subjects had to develop a common code referring to items in varying lists of geometrical figures distinguished by up to three features. A code had to be made of a limited repertoire of letters. Using letters had a cost. We are interested in the question of whether a common code is developed, and what enhances its emergence. Furthermore, we explore the emergence of compositional, protogrammatical structure in such codes. We compare environments that differ in terms of available linguistic resources (number of letters available) and in terms of stability of the task environment (variability in the set of figures). Our experiments show that a too small repertoire of letters causes coordination failures. Cost efficiency and role asymmetry are important factors enhancing communicative success. In stable environments, grammars do not seem to matter much, and instead efficient arbitrary codes often do better. However, in an environment with novelty, compositional grammars offer considerable coordination advantages and therefore are more likely to arise. 10.1073/pnas.0702077104Wed Mar 31 19:10:16 CEST 2010Proceedings of the National Academy of SciencesAugust3110681--10686Cumulative cultural evolution in the laboratory: An experimental approach to the origins of structure in human language10520082008 cornish cultural evolution experiment kirby language smith 510.1073/pnas.0707835105 We introduce an experimental paradigm for studying the cumulative cultural evolution of language. In doing so we provide the first experimental validation for the idea that cultural transmission can lead to the appearance of design without a designer. Our experiments involve the iterated learning of artificial languages by human participants. We show that languages transmitted culturally evolve in such a way as to maximize their own transmissibility: over time, the languages in our experiments become easier to learn and increasingly structured. Furthermore, this structure emerges purely as a consequence of the transmission of language over generations, without any intentional design on the part of individual language learners. Previous computational and mathematical models suggest that iterated learning provides an explanation for the structure of human language and link particular aspects of linguistic structure with particular constraints acting on language during its transmission. The experimental work presented here shows that the predictions of these models, and models of cultural evolution more generally, can be tested in the laboratory.Tue Mar 30 10:44:41 CEST 2010{Cognitive Psychology}328-350{Natural categories}419731973 categories cognition rosch Mon Mar 22 18:37:30 CET 2010J. Conflict Resolut.2203-226{The Dissemination of Culture: A Model with Local Convergence and Global Polarization}4119971997 axelrod convergence culture dultural dynamics model polarization Despite tendencies toward convergence, differences between individuals and groups continue to exist in beliefs, attitudes, and behavior. An agent-based adaptive model reveals the effects of a mechanism of convergent social influence. The actors are placed at fixed sites. The basic premise is that the more similar an actor is to a neighbor, the more likely that that actor will adopt one of the neighbor's traits. Unlike previous models of social influence or cultural change that treat features one at a time, the proposed model takes into account the interaction between different features. The model illustrates how local convergence can generate global polarization. Simulations show that the number of stable homogeneous regions decreases with the number of features, increases with the number of alternative traits per feature, decreases with the range of interaction, and (most surprisingly) decreases when the geographic territory grows beyond a certain size. Mon Mar 22 18:36:40 CET 2010J. Math. Sociol.2143--186Dynamic Models of Segregation119711971 model schelling segregation Mon Mar 22 16:01:52 CET 2010New York, NY, USADynamical Processes on Complex Networks20082008 barrat barthelemy complex dynamical networks processes vespignani Mon Mar 22 10:46:14 CET 2010OxfordLanguage and Number: the emergence of a cognitive system19871987 hurford language number numeral systems