Faster Algorithms for Incremental Topological Ordering.Robert Tarjan

We present two online algorithms for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm takes O(m 1/2) amortized time per arc and our second algorithm takes O(n 2.5/m) amortized time per arc, where n is the number of vertices and m is the total number of arcs. For sparse graphs, our O(m 1/2) bound improves the best previous bound by a factor of logn and is tight to within a constant factor for a natural class of algorithms that includes all the existing ones. Our main insight is that the two-way search method of previous algorithms does not require an ordered search, but can be more general, allowing us to avoid the use of heaps (priority queues). Instead, the deterministic version of our algorithm uses (approximate) median-finding; the randomized version of our algorithm uses uniform random sampling. For dense graphs, our O(n 2.5/m) bound improves the best previously published bound by a factor of n 1/4 and a recent bound obtained independently of our work by a factor of logn. Our main insight is that graph search is wasteful when the graph is dense and can be avoided by searching the topological order space instead. Our algorithms extend to the maintenance of strong components, in the same asymptotic time bounds.

Scalable Context-Sensitive Points-To Analysis Using Multi-Dimensional Bloom Filters

Context-sensitive points-to analysis is critical for several program optimizations. However, as the number of contexts grows exponentially, storage requirements for the analysis increase tremendously for large programs, making the analysis non-scalable. We propose a scalable flow-insensitive context-sensitive inclusion-based points-to analysis that uses a specially designed multi-dimensional bloom filter to store the points-to information. Two key observations motivate our proposal: (i) points-to information (between pointer-object and between pointer-pointer) is sparse, and (ii) moving from an exact to an approximate representation of points-to information only leads to reduced precision without affecting correctness of the (may-points-to) analysis. By using an approximate representation a multi-dimensional bloom filter can significantly reduce the memory requirements with a probabilistic bound on loss in precision. Experimental evaluation on SPEC 2000 benchmarks and two large open source programs reveals that with an average storage requirement of 4MB, our approach achieves almost the same precision (98.6%) as the exact implementation. By increasing the average memory to 27MB, it achieves precision upto 99.7% for these benchmarks. Using Mod/Ref analysis as the client, we find that the client analysis is not affected that often even when there is some loss of precision in the points-to representation. We find that the NoModRef percentage is within 2% of the exact analysis while requiring 4MB (maximum 15MB) memory and less than 4 minutes on average for the points-to analysis. Another major advantage of our technique is that it allows to trade off precision for memory usage of the analysis.

An (O)over-bar(m(2)n) randomized algorithm to compute a minimum cycle basis of a directed graph

We consider the problem of computing a minimum cycle basis in a directed graph G. The input to this problem is a directed graph whose arcs have positive weights. In this problem a {- 1, 0, 1} incidence vector is associated with each cycle and the vector space over Q generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of weights of the cycles is minimum is called a minimum cycle basis of G. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m arcs and n vertices runs in O(m(w+1)n) time (where w < 2.376 is the exponent of matrix multiplication). If one allows randomization, then an (O) over tilde (m(3)n) algorithm is known for this problem. In this paper we present a simple (O) over tilde (m(2)n) randomized algorithm for this problem. The problem of computing a minimum cycle basis in an undirected graph has been well-studied. In this problem a {0, 1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of the graph. The fastest known algorithm for computing a minimum cycle basis in an undirected graph runs in O(m(2)n + mn(2) logn) time and our randomized algorithm for directed graphs almost matches this running time.

Dataflow analysis for data-race free programs

Memory models for shared-memory concurrent programming languages typically guarantee sequential consistency (SC) semantics for datarace-free (DRF) programs, while providing very weak or no guarantees for non-DRF programs. In effect programmers are expected to write only DRF programs, which are then executed with SC semantics. With this in mind, we propose a novel scalable solution for dataflow analysis of concurrent programs, which is proved to be sound for DRF programs with SC semantics. We use the synchronization structure of the program to propagate dataflow information among threads without requiring to consider all interleavings explicitly. Given a dataflow analysis that is sound for sequential programs and meets certain criteria, our technique automatically converts it to an analysis for concurrent programs.

Improving GPGPU Concurrency with Elastic Kernels

Each new generation of GPUs vastly increases the resources available to GPGPU programs. GPU programming models (like CUDA) were designed to scale to use these resources. However, we find that CUDA programs actually do not scale to utilize all available resources, with over 30% of resources going unused on average for programs of the Parboil2 suite that we used in our work. Current GPUs therefore allow concurrent execution of kernels to improve utilization. In this work, we study concurrent execution of GPU kernels using multiprogram workloads on current NVIDIA Fermi GPUs. On two-program workloads from the Parboil2 benchmark suite we find concurrent execution is often no better than serialized execution. We identify that the lack of control over resource allocation to kernels is a major serialization bottleneck. We propose transformations that convert CUDA kernels into elastic kernels which permit fine-grained control over their resource usage. We then propose several elastic-kernel aware concurrency policies that offer significantly better performance and concurrency compared to the current CUDA policy. We evaluate our proposals on real hardware using multiprogrammed workloads constructed from benchmarks in the Parboil 2 suite. On average, our proposals increase system throughput (STP) by 1.21x and improve the average normalized turnaround time (ANTT) by 3.73x for two-program workloads when compared to the current CUDA concurrency implementation.

A Quick-Simulation Tool for Induction Motor Drives Controlled Using Advanced Space-Vector-Based PWM Techniques

Space-vector-based pulse width modulation (PWM) for a voltage source inverter (VSI) offers flexibility in terms of different switching sequences. Numerical simulation is helpful to assess the performance of a PWM method before actual implementation. A quick-simulation tool to simulate a variety of space-vector-based PWM strategies for a two-level VSI-fed squirrel cage induction motor drive is presented. The simulator is developed using C and Python programming languages, and has a graphical user interface (GUI) also. The prime focus being PWM strategies, the simulator developed is 40 times faster than MATLAB in terms of the actual time taken for a simulation. Simulation and experimental results are presented on a 5-hp ac motor drive.

Lower Bounds for Sums of Powers of Low Degree Univariates

We consider the problem of representing a univariate polynomial f(x) as a sum of powers of low degree polynomials. We prove a lower bound of Omega(root d/t) for writing an explicit univariate degree-d polynomial f(x) as a sum of powers of degree-t polynomials.

Las bodas de Camacho y una relectura del mito de D. Quijote desde versiones operísticas del episodio cervantino

Resumen: El mundo de la ópera es un campo de permanentes ebulliciones aunque todavía se le endilguen acusaciones falsas de inmovilidad y anquilosamiento. No cesan de componerse obras con lenguajes innovadores sobre temáticas inéditas. Se experimenta —a veces, abusivamente— con puestas en escena heterodoxas, y las investigaciones hallan partituras perdidas o relegadas que hacen variar, permanentemente, el mapa del canon del género. En el presente trabajo, se analiza un caso-testigo de estas continuas mutaciones. Es la recuperación entre 2006 y 2011 de tres óperas compuestas entre 1760 y 1830 sobre el episodio del Quijote referido a las bodas de Camacho. Reviste particular relevancia, a mi juicio, porque no solo ha aumentado el caudal del repertorio operístico conocido sino que por sus relaciones con la literatura nos alerta a los estudiosos de ésta acerca de fenómenos que no podemos dejar de considerar. Ellos atañen a la recepción de la obra cervantina y al mito de D. Quijote, mito cuya expansión sobrepasa, ampliamente, al público lector de la obra. Nos conduce, por lo tanto, más allá de lo literario, a las complejidades de la construcción del imaginario cultural.

Régimen jurídico de las lenguas y reconocimiento de la diversidad lingüística en el Tratado por el que se establece una Constitución para Europa

The territory of the European Union is made up of a rich and wide-ranging universe of languages, which is not circumscribed to the «State languages». The existence of multilingualism is one of Europe’s defining characteristics and it should remain so in the constantly evolving model of Europe’s political structure. Nonetheless, until now, the official use of languages has been limited to the «State languages» and has been based on a concept of state monolingualism that has led to a first level of hierarchization among the languages of Europe. This has affected the very concept of European language diversity. The draft of the treaty establishing a European Constitution contains various language-related references that can be grouped in two major categories: on the one hand, those references having to do the constitutional status of languages, and on the other, those regarding the recognition of European language diversity. Both issues are dealt with in this article. In analyzing the legal regime governing languages set forth in the draft of the constitutional treaty, we note that the draft is not based on the concept of the official status of languages. The language regulation contained in the draft of the constitutional treaty is limited in character. The constitutional language regime is based on the concept of Constitutional languages but the official status of languages is not governed by this rule. The European Constitution merely enunciates rights governing language use for European citizens vis-à-vis the languages of the Constitution and refers the regulation of the official status of languages to the Council, which is empowered to set and modify that status by unanimous decision. Because of its broad scope, this constitutes a regulatory reservation. In the final phase of the negotiation process a second level of constitutional recognition of languages would be introduced, linked to those that are official languages in the member states (Catalan, Basque, Galician, etc.). These languages, however, would be excluded from the right to petition; they would constitute a tertium genus, an intermediate category between the lan guages benefiting from the language rights recognized under the Constitution and those other languages for which no status is recognized in the European institutional context. The legal functionality of this second, intermediate category will depend on the development of standards, i.e., it will depend on the entrée provided such languages in future reforms of the institutional language regime. In a later section, the article reflects on European Union language policy with regard to regional or minority languages, concluding that the Union has not acted in accordance with defined language policy guidelines when it has been confronted, in the exercise of its powers, with regional or minority languages (or domestic legislation having to do with language demands). The Court of Justice has endeavoured to resolve on a case by case basis the conflicts raised between community freedoms and the normative measures that protect languages. Thus, using case law, the Court has set certain language boundaries for community freedoms. The article concludes by reflecting on the legal scope of the recognition of European language diversity referred to in Article II-82 of the European Constitution and the possible measures to implement the precept that might constitute the definition of a true European language policy on regional or minority languages. Such a policy has yet to be defined.

Literaturaren zertarakoa, itzulpenak eta hizkuntzaren auzia Orixerengan

Ejemplar dedicado a: Beñat Oihartzabali gorazarre - Festchrift for Bernard Oyharçabal/ Ricardo Etxepare, Ricardo Gómez, Joseba Andoni Lakarra ( eds.)

Word frequency cues word order in adults: cross-linguistic evidence

[EN] One universal feature of human languages is the division between grammatical functors and content words. From a learnability point of view, functors might provide entry points or anchors into the syntactic structure of utterances due to their high frequency. Despite its potentially universal scope, this hypothesis has not yet been tested on typologically different languages and on populations of different ages. Here we report a corpus study and an artificial grammar learning experiment testing the anchoring hypothesis in Basque, Japanese, French, and Italian adults. We show that adults are sensitive to the distribution of functors in their native language and use them when learning new linguistic material. However, compared to infants’ performance on a similar task, adults exhibit a slightly different behavior, matching the frequency distributions of their native language more closely than infants do. This finding bears on the issue of the continuity of language learning mechanism.

Augmented Peter Pan: un cuento multilingüe con Realidad Aumentada

[SPA] El objetivo de este Trabajo de Fin de Grado ha sido diseñar un cuento multilingüe que incorpora una innovación tecnológica, la Realidad Aumentada, para favorecer el proceso de enseñanza-aprendizaje lingüístico en la escuela. Para ello, hemos analizado algunos cuentos con Realidad Aumentada que se pueden encontrar en el mercado. Al no encontrar ningún cuento que cumpliese nuestras expectativas, hemos creado un cuento multilingüe con Realidad Aumentada adaptando el cuento clásico “Peter Pan”, que cumple los objetivos de fomentar el aprendizaje de diferentes idiomas y el gusto por la lectura, valorar las lenguas inmigrantes en las aulas y promover el uso de las TIC.

A importância do estudo de história da língua portuguesa no curso de Letras

Este trabalho tem como objetivo ressaltar a importância dos conteúdos da disciplina História da Língua Portuguesa para a formação do graduando do curso de Letras. O ensino de Língua Portuguesa se dá, por questões didáticas, de forma recortada, sendo cada um de seus recortes (Morfologia, Fonética, Sintaxe etc.) trabalhado em semestres diferentes. A forma fragmentada de estudar a língua parece induzir o graduando a uma visão também fragmentada (e fragmentária) de seu objeto de estudo, prejudicando a formação do futuro professor/pesquisador da língua. A análise dos fenômenos linguísticos sob a ótica da diacronia em que uma alteração fonética pode, por exemplo, resultar em alterações morfológicas e sintáticas possibilita a visão da língua em seu funcionamento como um todo, com suas partes interagindo e se interpenetrando. Essa visão mais ampla, segundo cremos, poderá capacitar o aluno para conectar as informações de diferentes recortes, a fim de alcançar conhecimentos novos e mais complexos. Procuramos evidenciar os benefícios da abordagem diacrônica apresentando o conteúdo programático da disciplina História da Língua Portuguesa e tecendo comentários que apontam a relevância de cada conteúdo para a formação do graduando. Acrescentamos, algumas vezes, sugestões de atividades didáticas com o intuito de granjear o interesse do aluno para a disciplina

Hizkuntza komunikaziorako gaitasuna lantzeko ikuspegi berriak: teoriatik praktikara

[EUS] Gure gaur egungo gizarte globalizatuak, internazionalki komunikatzeko beharra areagotu du, eta horregatik atzerriko hizkuntzak ikastea ezinbestekoa bihurtu da. Eskola errealitatearen isla denez, behar horri aurre egiteko, gero eta gehiago dira irakaskuntza eleaniztuna garatzeko ikuspegi metodologikoak. Ikuspegi metodologiko hauen artean, CLIL/HEBI eta HTB dira garrantzitsuenetarikoak. HEBIk hizkuntzak eta edukiak batera ikasteari egiten dio erreferentzia, eta HTBk curriculumeko hizkuntzen programazio adostuari. Lan honetan metodologia hauen nondik norakoak aztertzen dira, baita hauek ikastetxe batean nolako ibilbidea izan duten eta nola lantzen diren ere. Azken honetan ikastetxearen eta ikasleen aldetik HEBIrekiko dagoen jarrera aztertzen da, galdetegi batzuen bitartez.

"Erran nahi baita" birformulatzaile esplikatiboa gaurko euskaran

[EN] This article presents a detailed study of the present-day use of the Basque discourse marker "erran/esan nahi baita" (‘that is to say’). This is an explanatory reformulator by means of which the speaker presents a reformulation of something said in the previous utterance (either a clause that forms part of the current sentence, or the preceding sentence) in order to express it more clearly or explain it. In the article I will examine the marker’s values; literary tradition; form and origin; present-day variants; equivalent expressions; position; punctuation; syntax; frequency, medium (written or spoken), register and text type; equivalents in other languages; and discourse value.