Дисертації з теми "Computer lexicography"

The present article is devoted to the problems of creating linguistic tools for the virtual lexicographic laboratory of Spanish explanatory dictionary (DLE 23). The goal of the research is to consider some issues related to the development of linguistic tools for the virtual lexicographic laboratory. To achieve this goal the dictionary was analyzed to define the peculiarities of linguistic facts representation, its structure and metalanguage. On the basis of the dictionary analysis and the theory of lexicographic systems the formal model of DLE 23 was developed and its main components, including their relationships, were determined to ensure their availability via linguistic tools for accessing linguistic information. The range of research activities to be performed by using the linguistic tools was outlined.

This dissertation reports on studies of the application of lexicographic graph searches to solve problems in FPGA detailed routing. Our contributions include the derivation of iteration limits for scalar implementations of negotiation congestion for standard floating point types and the identification of pathological cases for path choice. In the study of the routability-driven detailed FPGA routing problem, we show universal detailed routability is NP-complete based on a related proof by Lee and Wong. We describe the design of a lexicographic composition operator of totally-ordered monoids as path cost metrics and show its optimality under an adapted A* search. Our new router, CornNC, based on lexicographic composition of congestion and wirelength, established a new minimum track count for the FPGA Place and Route Challenge. For the problem of long-path timing-driven FPGA detailed routing, we show that long-path budgeted detailed routability is NP-complete by reduction to universal detailed routability. We generalise the lexicographic composition to any finite length and verify its optimality under A* search. The application of the timing budget solution of Ghiasi et al. is used to solve the long-path timing budget problem for FPGA connections. Our delay-clamped spiral lexicographic composition design, SpiralRoute, ensures connection based budgets are always met, thus achieves timing closure when it successfully routes. For 113 test routing instances derived from standard benchmarks, SpiralRoute found 13 routable instances with timing closure that were unroutable by a scalar negotiated congestion router and achieved timing closure in another 27 cases when the scalar router did not, at the expense of increased runtime. We also study techniques to improve SpiralRoute runtimes, including a data structure of a trie augmented by data stacks for minimum element retrieval, and the technique of step tomonoid elimination in reducing the retrieval depth in a trie of stacks structure.

The paper deals with the lexicographic description of Ukrainian hydroturbine term subsystem in electronic dictionary. The formation and development of computer lexicography in Ukraine and abroad are considered. The lines of research in modern Ukrainian computer lexicography are analyzed, and its development prospects are outlined. Theoretical studies of lexical unit description in paper and electronic dictionaries, performed by leading scientists, are surveyed. Based on the vast research material the analysis of hydroturbine term subsystem, in particular its sources of formation, structure and system relations between terms, is performed. The structural and semantic characteristics of hydroturbine terms are given.
Дисертаційне дослідження присвячено описові української гідротурбінної термінології та її лексикографічній репрезентації в електронному словнику. Розглянуто становлення і розвиток українського та зарубіжного електронного словникарства, визначено напрямки досліджень сучасної української комп'ютерної лексикографії, наголошено на перспективах її розвитку. Здійснено огляд теоретичних праць провідних науковців щодо опрацювання лексики в паперових та комп'ютерних словниках. Проаналізовано гідротурбінну термінологічну підсистему, зокрема висвітлено джерела її формування, структурну організацію та внутрішні системні зв'язки, з'ясовано структурно-семантичну будову термінів. Запропоновано модель комп'ютерного словника спеціальної лексики, обґрунтовано лексикографічні параметри, за якими здійснюється опис терміносистеми у словнику.

Cette thèse présente un environnement ouvert et souple pour l'acquisition automatique d'expressions multimots (MWE) à partir de corpus textuels monolingues. Cette recherche est motivée par l'importance des MWE pour les applications du TALN. Après avoir brièvement présenté les modules de l'environnement, le mémoire présente des résultats d'évaluation intrinsèque en utilisant deux applications: la lexicographie assistée par ordinateur et la traduction automatique statistique. Ces deux applications peuvent bénéficier de l'acquisition automatique de MWE, et les expressions acquises automatiquement à partir de corpus peuvent à la fois les accélérer et améliorer leur qualité. Les résultats prometteurs de nos expériences nous encouragent à mener des recherches ultérieures sur la façon optimale d'intégrer le traitement des MWE dans ces applications et dans bien d'autres

Preferences are very important in research fields such as decision making, recommendersystemsandmarketing. The focus of this thesis is on preferences over combinatorial domains, which are domains of objects configured with categorical attributes. For example, the domain of cars includes car objects that are constructed withvaluesforattributes, such as ‘make’, ‘year’, ‘model’, ‘color’, ‘body type’ and ‘transmission’.Different values can instantiate an attribute. For instance, values for attribute ‘make’canbeHonda, Toyota, Tesla or BMW, and attribute ‘transmission’ can haveautomaticormanual. To this end,thisthesis studiesproblemsonpreference visualization and learning for lexicographic preference trees, graphical preference models that often are compact over complex domains of objects built of categorical attributes. Visualizing preferences is essential to provide users with insights into the process of decision making, while learning preferences from data is practically important, as it is ineffective to elicit preference models directly from users. The results obtained from this thesis are two parts: 1) for preference visualization, aweb- basedsystem is created that visualizes various types of lexicographic preference tree models learned by a greedy learning algorithm; 2) for preference learning, a genetic algorithm is designed and implemented, called GA, that learns a restricted type of lexicographic preference tree, called unconditional importance and unconditional preference tree, or UIUP trees for short. Experiments show that GA achieves higher accuracy compared to the greedy algorithm at the cost of more computational time. Moreover, a Dynamic Programming Algorithm (DPA) was devised and implemented that computes an optimal UIUP tree model in the sense that it satisfies as many examples as possible in the dataset. This novel exact algorithm (DPA), was used to evaluate the quality of models computed by GA, and it was found to reduce the factorial time complexity of the brute force algorithm to exponential. The major contribution to the field of machine learning and data mining in this thesis would be the novel learning algorithm (DPA) which is an exact algorithm. DPA learns and finds the best UIUP tree model in the huge search space which classifies accurately the most number of examples in the training dataset; such model is referred to as the optimal model in this thesis. Finally, using datasets produced from randomly generated UIUP trees, this thesis presents experimental results on the performances (e.g., accuracy and computational time) of GA compared to the existent greedy algorithm and DPA.

Thesis (MPhil (Modern Foreign Languages))--University of Stellenbosch, 2011.
ENGLISH ABSTRACT: Available dictionaries involving Afrikaans and German do not satisfactorily deal with collocations. Therefore, this study recommends a theoretically grounded design of a user interface for an electronic dictionary of German collocations for foreign language learners of German whose first language or mother tongue is Afrikaans. In order to be able to do so, a set of requirements is drawn up, upon which the electronic collocations dictionary will be based. On the one hand these requirements give consideration to lexicographic factors relevant to the envisaged dictionary; on the other hand a theoretical basis for the presentation of the electronic dictionary according to usability principles and standards is established. The underlying definition of collocations will be discussed as one of the lexicographic factors constituting the learner dictionary of collocations. Being primarily aimed at Afrikaans speaking foreign language learners of German, their usage situation plays an important role. At an intermediate language learning level topics to be conversed about become increasingly complex. As collocations offer adequate means of expressing these increasingly complex ideas, the learners’ need of collocational knowledge increases, even more with regard to the language production than to the language reception. As collocations are not dealt with adequately in available dictionaries involving Afrikaans and German, there is a definite demand for an adequate dictionary for this user group. The envisaged learner dictionary’s function and type will be determined accordingly. In addition to the lexicographic factors underpinning the design of the user interface, international usability standards DIN EN ISO 9241 (amongst others) and practical recommendations for user interface design by Jakob Nielsen (amongst others) are discussed. This discussion makes provision for the theoretically grounded presentation of the envisaged electronic dictionary of German collocations in line with usability standards. Finally, giving consideration to the set of lexicographic and usability requirements drawn up, a user interface design is recommended for the electronic dictionary for foreign language learners of German whose first language or mother tongue is Afrikaans.
AFRIKAANSE OPSOMMING: Die Afrikaans / Duitse woordeboeke wat tans beskikbaar is, bied nie genoegsame inligting oor kollokasies nie. Dus word in hierdie studie’n teoreties gebaseerde voorstel vir ’n gebruikerskoppelvlak vir ’n elektroniese woordeboek om Duitse kollokasies op te soek, gemaak. Dié woordeboek is gemik op individue wie se eerste taal of moedertaal Afrikaans is, en wat Duits as ’n vreemde taal aanleer. Om voorstelle vir die aanbieding van so ‘n woordeboek te kan maak, word ’n stel vereistes aanbeveel waarop die elektroniese kollokasie-woordeboek gebaseer sal word. Aan die een kant neem hierdie vereistes die leksikografiese faktore in ag, wat relevant is tot die beoogde woordeboek en aan die ander kant word daar ’n teoretiese basis gelê vir die aanbieding van die elektroniese woordeboek volgens gebruikersvriendelike beginsels en standaarde. Die onderliggende definisie van kollokasies word bespreek as een van die leksikografiese faktore wat die opstel van ‘n kollokasie-woordeboek beïnvloed. Omdat dit primêr gemik is op Afrikaanssprekendes wat Duits as ’n vreemde taal aanleer, speel hul gebruiksituasie ’n belangrike rol. Op ’n intermediêre taalvaardigheidsvlak is die onderwerpe waaroor gepraat en wat bespreek word, heelwat meer kompleks en kollokasies bied die moontlikheid om hierdie toenemende komplekse idees uit te druk. Leerders se behoefte aan ‘n grondiger kennis van kollokasies vir taalproduksie, en minder vir taalresepsie, neem dus aansienlik toe. Die Afrikaans / Duitse woordeboeke wat tans beskikbaar is, gee egter nie genoegsame inligting oor kollokasies nie. Daar is dus ’n definitiewe leemte aan ’n woordeboek wat in hierdie gebruikersgroep se behoefte sal voorsien. Die beoogde leerderwoordeboek se funksie en soort word hiervolgens bepaal. Bykomend tot die leksikografiese faktore wat dien as basis vir die ontwerp van die gebruikerskoppelvlak, word internasionale gebruikersvriendelike standaarde soos byvoorbeeld die norm DIN EN ISO 9241 en praktiese aanbevelings vir die ontwerp van ’n gebruikerskoppelvlak deur byvoorbeeld Jakob Nielsen bespreek. Hierdie bespreking maak voorsiening vir die teoreties gefundeerde aanbieding van die beoogde elektroniese woordeboek van Duitse kollokasies wat in pas is met gebruikstandaarde. Laastens word daar op grond van die lys van leksikografiese en gebruikersbehoeftes wat opgestel is, ’n ontwerp van ‘n gebruikerskoppelvlak aanbeveel vir die elektroniese woordeboek vir leerders wie se eerste taal of moedertaal Afrikaans is en wat Duits as ’n vreemde taal aanleer.
GERMAN SUMMARY: Derzeit zur Verfügung stehende Wörterbücher mit Afrikaans und Deutsch behandeln Kollokationen auf ungenügende Weise. Daher wird in der vorliegenden Arbeit eine theoretisch begründete Gestaltung einer Benutzeroberfläche eines elektronischen Wörterbuches deutscher Kollokationen für afrikaans-sprechende Lerner des Faches Deutsch als Fremdsprache vorgeschlagen. Hierzu werden die nötigen Anforderungen erarbeitet, auf die das elektronische Kollokationswörterbuch aufbauen soll. Die Anforderungen werden einerseits aufgrund von lexikografischen Faktoren ermittelt, andererseits wird die theoretische Grundlage für eine gebrauchstaugliche Präsentation des elektronischen Wörterbuches erörtert. Die lexikografischen Faktoren, welche die Konzipierung eines Kollokationslernerwörterbuches beeinflussen, schließen den Kollokationsbegriff ein, welcher dem Wörterbuch zugrunde liegen wird. Des weiteren spielt die primäre Benutzergruppe des anvisierten Wörterbuches bei der Konzipierung eine entscheidende Rolle. Die Wörterbuchfunktion und der Wörterbuchtyp werden daher anhand des Bedarfs des afrikaans-sprechenden Lerners des Faches Deutsch als Fremdsprache mittleren Sprachniveaus ermittelt. Dieser Bedarf ist in der korrekten Verwendung von deutschen Kollokationen in der Sprachproduktion und weniger in ihrem Verständnis während der Sprachrezeption begründet. Die Notwendigkeit, diesen Bedarf zu decken, ergibt sich aus dem unbefriedigenden Umgang mit Kollokationen in den beiden Wörterbüchern, die dem afrikaans-sprechenden Lerner des Faches Deutsch als Fremdsprache derzeit zur Verfügung stehen. Aufgrund des elektronischen Mediums des anvisierten Wörterbuches, werden unter anderem internationale Gestaltungsgrundsätze der Norm DIN EN ISO 9241 sowie praktische Empfehlungen zur Gestaltung von Bildschirmpräsentationen von unter anderem Jakob Nielsen diskutiert. Aufgrund dieser Diskussion wird schlussendlich unter Berücksichtigung und Zusammenführung der erarbeiteten Anforderungen eine Gestaltung einer Benutzeroberfläche eines elektronischen Wörterbuches deutscher Kollokationen für afrikaans-sprechende Lerner des Faches Deutsch als Fremdsprache vorgeschlagen.

La thèse de M. Mario Monteleone est intitulée Lexicographie et dictionnaires électroniques. Des usages linguistiques aux bases de donnés lexicales et concerne les rapports (existants et potentiels) entre la lexicographie classique et la linguistique informatique. En particulier, M. Monteleone essaie à établir si certaines limites analytiques de la lexicographie peuvent être dépassées par l'application des méthodes de recherche de la linguistique informatique. Dans ce but, M. Monteleone effectue une analyse détaillée soit des deux disciplines, soit des leurs instruments classiques, i.e. les dictionnaires papier et les dictionnaires électroniques, du point de vue de leurs méthodes de constructions et de leurs domaines d'application. Il en résulte un vade-mecum pour les lexicographes classiques et informatiques, focalisé sur le repérage et le classement des données linguistiques pour la réalisations de dictionnaires papier et électroniques.

L'espanyol és una llengua amb moltes realitzacions en funció dels seus diferents registres. És clar que les diferències existents en la llengua espanyola són degudes a la seva àmplia distribució geogràfica i l'alt nombre de parlants; això es materialitza en els termes que designen realitats noves, com en el cas de la informàtica. Per aquesta raó, hem considerat pertinent realitzar un estudi detallat que posés de manifest les diferents realitzacions d'aquest tipus de lèxic en els països de parla hispana, des d'una perspectiva descriptiva i contrastiva, que permetés observar punts de trobades i/o desencontres en aspectes morfològics, semàntics i discursius d'aquest llenguatge d'especialitat. Per a aquesta investigació, hem portat a terme un rastreig d'aquest tipus de lèxic en fonts lexicogràfiques (diccionaris generals, corpus, bases terminològiques i glossaris especialitzats) i en fonts textuals (d’entre els anys 2006 i 2010). Aquestes últimes responen a dos tipus: diaris digitals i pàgines web d'universitats, ambdues de vint països de parla hispana. Amb les fonts textuals, s'ha conformat un corpus mitjançant l'eina TLCorpus de TshwaneDJe, que permet visualitzar llistats de termes i indica la seva freqüència d'aparició; així mateix, possibilita la seva cerca en un microcontext, alhora d'extreure exemples. Finalment, en aquesta recerca s'ha aprofundit tant en l'aspecte teòric com en el pràctic del lèxic de la informàtica i Internet en l'àmbit hispànic. Pretenem que es constitueixi en un antecedent vàlid per a posteriors estudis i anàlisis en aquest camp, així com en la base per a un glossari actualitzat d'aquest tipus de termes.
El español es una lengua con muchas realizaciones en función de sus diferentes registros. Es claro que las diferencias existentes en la lengua española son debidas a su amplia distribución geográfica y al alto número de hablantes; esto se materializa en los términos que designan realidades nuevas, como en el caso de la informática. Por esta razón, se consideró pertinente realizar un estudio detallado que pusiese de manifiesto las diferentes realizaciones de este tipo de léxico en los países de habla hispana, desde una perspectiva descriptiva y contrastiva, que permitiese observar puntos de encuentros y/o desencuentros en aspectos morfológicos, semánticos y discursivos de este lenguaje de especialidad. Para esta investigación, hemos llevado a cabo un rastreo de este tipo de léxico en fuentes lexicográficas (diccionarios generales, corpus, bases terminológicas y glosarios especializados) y en fuentes textuales (entre los años 2006 y 2010); estas últimas responden a dos tipos: periódicos digitales y páginas web de universidades, ambas de veintiún países de habla hispana. Con las fuentes textuales, se ha conformado un corpus mediante la herramienta TLCorpus de TshwaneDJe, que permite visualizar listados de términos e indica su frecuencia de aparición; asimismo, posibilita su búsqueda en un microcontexto, a la vez que extraer ejemplos. Finalmente, en esta investigación se ha profundizado tanto en el aspecto teórico como en el práctico del léxico de la informática e Internet en el ámbito hispánico. Aspiramos a que se constituya en un antecedente válido para posteriores estudios y análisis en este campo, así como en la base para un glosario actualizado de este tipo de términos.
Spanish is a language with many embodiments according to different registers. It is clear that the differences in the Spanish language occur due to its wide geographic distribution and the large number of speakers; this is materialized in the terms designating new realities, as in the case of computing science. For this reason, it was considered appropriate to realize a detailed study that would reveal the different usage of this type of vocabulary in Spanish-speaking countries, from a descriptive and contrastive perspective, that allows to observe all the matches and/or counterpoints in morphological, semantic and discourse aspects of this language for specific purposes. For this investigation, we have accomplished a tracing search of this kind of lexicon in lexicographical sources (general dictionaries, corpora, terminology databases and specialized glossaries), and in textual sources (between 2006 and 2010); the latter ones correspond to two types: digital newspapers and university websites, both from the following twenty-one Spanish speaking countries. With the textual sources, we have assembled a corpus by means of TLCorpus tool by TshwaneDJe, which allows to visualize listings of terms and indicates their frequency of appearance; further on, it also allows searching in a microcontext, as well as extracting examples. Ultimately, in this research we have deepened both into the theoretical and the practical aspect of the lexicon of computing science and Internet in the Hispanic world. We aim to establish it as a valid precendent for further studies and analysis in this field, and also, as the basis for an updated glossary of this type of terms.

Cette thèse aborde le problème de la structuration de bases lexicales multilingues (BDLM) en lexies et axies, à partir de ressources existantes. Ce travail est motivé par l'inadéquation des techniques existantes utilisées isolément, pour la structuration de BDLM.
Pour résoudre ce problème, la stratégie proposée est de composer des techniques existantes de désambiguïsation pour structurer semi-automatiquement des bases lexicales multilingues à lexies et acceptions interlingues. De plus, cette thèse propose une catégorisation des critères d'évaluation de la qualité des BDLM, ainsi que les mesures correspondantes.
Cette stratégie a été implémentée dans Jeminie, un système logiciel adaptable qui permet d'implémenter à la fois des méthodes de structuration de BDLM et des mesures de qualité, sous la forme de modules logiciels réutilisables.
Des compositions arbitraires de ces modules peuvent être définies par un lexicologue dans un langage de haut niveau d'abstraction, ce qui permet d'adapter facilement la structuration et l'évaluation de qualité en fonction des objectifs du lexicologue et des ressources disponibles sans nécessiter de connaissances en programmation.
L'intérêt de cette approche a été validé expérimentalement : la qualité des BDLM obtenues est meilleure par combinaison de techniques qu'avec chaque technique antérieure utilisée seule.

Cette thèse présente un environnement ouvert et souple pour l'acquisition automatique d'expressions multimots (MWE) à partir de corpus textuels monolingues. Cette recherche est motivée par l'importance des MWE pour les applications du TALN. Après avoir brièvement présenté les modules de l'environnement, le mémoire présente des résultats d'évaluation intrinsèque en utilisant deux applications: la lexicographie assistée par ordinateur et la traduction automatique statistique. Ces deux applications peuvent bénéficier de l'acquisition automatique de MWE, et les expressions acquises automatiquement à partir de corpus peuvent à la fois les accélérer et améliorer leur qualité. Les résultats prometteurs de nos expériences nous encouragent à mener des recherches ultérieures sur la façon optimale d'intégrer le traitement des MWE dans ces applications et dans bien d'autres

De nombreuses méthodes existent pour résoudre des problèmes d'optimisation multicritère, et il n'est pas aisé de choisir une méthode suffisamment adaptée à un problème multicritère donné. En effet, après le choix d'une méthode multicritère, différents paramètres (e.g. poids, fonctions d'utilité, etc.) doivent être déterminés, soit pour trouver la solution optimale (meilleur compromis) ou pour classer l'ensemble des solutions faisables (alternatives). Justement, vue cette difficulté pour fixer les paramètres, les méthodes d'élicitation sont utilisées pour aider le décideur dans cette tâche de fixation des paramètres. Par ailleurs, nous supposons que nous disposons d'un ensemble de solutions plausibles, et nous faisons aussi l'hypothèse de la disponibilité au préalable, des informations préférentielles obtenues après une interaction avec le décideur. Dans la première contribution de ce travail, nous tirons profit d'une mesure statistique simple et rapidement calculable, à savoir, le coefficient de corrélation $rho$ de Spearman, afin de développer une approche gloutonne (approchée), et deux approches exactes basées sur la programmation par contraintes (PPC) et la programmation linéaire en nombres entiers (PLNE). Ces méthodes sont ensuite utilisées pour éliciter automatiquement les paramètres appropriés de la méthode multicritère basée sur l'ordre lexicographique. Nous proposons aussi des modèles d'élicitation des paramètres d'autres méthodes multicritère, telles que la méthode MinLeximax issue de la théorie du choix social et du partage équitable, la méthode de la somme pondérée et les opérateurs OWA.

Nous présentons une recherche en ingénierie des connaissances appliquée aux prédicats linguistiques et aux définitions lexicographiques de la théorie Sens-Texte (TST). Notre méthodologie comporte trois étapes. 1. Nous montrons en quoi la conceptualisation de la TST devrait être étendue pour faciliter sa formalisation. Nous justifions la nécessité de définir un niveau sémantique profond (SemP) à base de graphes. Nous y définissons la notion de type d'unité sémantique profonde et sa structure actancielle, de sorte que leur organisation hiérarchique puisse correspondre à une hiérarchie de sens au sein de laquelle ces structures actancielles sont héritées et spécialisées. Nous reconceptualisons les définitions lexicographiques au niveau SemP, et au niveau du dictionnaire. Finalement, nous présentons un prototype d'éditeur de définitions basé sur la manipulation directe de graphes. 2. Nous proposons un formalisme de représentation des connaissances adapté à cette conceptualisation. Nous démontrons que les logiques de description et le formalisme des Graphes Conceptuels ne sont pas adaptés, et nous construisons alors un nouveau formalisme, dit des Graphes d'Unités. 3. Nous étudions l'opérationnalisation du formalisme des Graphes d'Unités. Nous lui associons une sémantique formelle basée sur la théorie des modèles et l'algèbre relationnelle, et montrons que les conditions de décidabilité du raisonnement logique correspondent aux intuitions des lexicographes. Nous proposons également une implémentation du formalisme avec les standards du web sémantique, ce qui permet de profiter des architectures existantes pour l'interopérationnalisation sur le web des données lexicales liées.

Chan, Shing Kai.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2010.
Includes bibliographical references (leaves 106-114).
Abstracts in English and Chinese.
Abstract --- p.i
Acknowledgements --- p.v
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Problem Statement --- p.2
Chapter 1.2 --- Motivation for Story Segmentation --- p.4
Chapter 1.3 --- Terminologies --- p.5
Chapter 1.4 --- Thesis Goals --- p.6
Chapter 1.5 --- Thesis Organization --- p.8
Chapter 2 --- Background Study --- p.9
Chapter 2.1 --- Coherence-based Approaches --- p.10
Chapter 2.1.1 --- Defining Coherence --- p.10
Chapter 2.1.2 --- Lexical Chaining --- p.12
Chapter 2.1.3 --- Cosine Similarity --- p.15
Chapter 2.1.4 --- Language Modeling --- p.19
Chapter 2.2 --- Feature-based Approaches --- p.21
Chapter 2.2.1 --- Lexical Cues --- p.22
Chapter 2.2.2 --- Audio Cues --- p.23
Chapter 2.2.3 --- Video Cues --- p.24
Chapter 2.3 --- Pros and Cons and Hybrid Approaches --- p.25
Chapter 2.4 --- Chapter Summary --- p.27
Chapter 3 --- Experimental Corpora --- p.29
Chapter 3.1 --- The TDT2 and TDT3 Multi-language Text Corpus --- p.29
Chapter 3.1.1 --- Introduction --- p.29
Chapter 3.1.2 --- Program Particulars and Structures --- p.31
Chapter 3.2 --- Data Preprocessing --- p.33
Chapter 3.2.1 --- Challenges of Lexical Chain Formation on Chi- nese Text --- p.33
Chapter 3.2.2 --- Word Segmentation for Word Units Extraction --- p.35
Chapter 3.2.3 --- Part-of-speech Tagging for Candidate Words Ex- traction --- p.36
Chapter 3.3 --- Chapter Summary --- p.37
Chapter 4 --- Indication of Lexical Cohesiveness by Lexical Chains --- p.39
Chapter 4.1 --- Lexical Chain as a Representation of Cohesiveness --- p.40
Chapter 4.1.1 --- Choice of Word Relations for Lexical Chaining --- p.41
Chapter 4.1.2 --- Lexical Chaining by Connecting Repeated Lexi- cal Elements --- p.43
Chapter 4.2 --- Lexical Chain as an Indicator of Story Segments --- p.48
Chapter 4.2.1 --- Indicators of Absence of Cohesiveness --- p.49
Chapter 4.2.2 --- Indicator of Continuation of Cohesiveness --- p.58
Chapter 4.3 --- Chapter Summary --- p.62
Chapter 5 --- Indication of Story Boundaries by Lexical Chains --- p.63
Chapter 5.1 --- Formal Definition of the Classification Procedures --- p.64
Chapter 5.2 --- Theoretical Framework for Segmentation Based on Lex- ical Chaining --- p.65
Chapter 5.2.1 --- Evaluation of Story Segmentation Accuracy --- p.65
Chapter 5.2.2 --- Previous Approach of Story Segmentation Based on Lexical Chaining --- p.66
Chapter 5.2.3 --- Statistical Framework for Story Segmentation based on Lexical Chaining --- p.69
Chapter 5.2.4 --- Post Processing of Ratio for Boundary Identifi- cation --- p.73
Chapter 5.3 --- Comparing Segmentation Models --- p.75
Chapter 5.4 --- Chapter Summary --- p.79
Chapter 6 --- Analysis of Lexical Chains Features as Boundary Indi- cators --- p.80
Chapter 6.1 --- Error Analysis --- p.81
Chapter 6.2 --- Window Length in the LRT Model --- p.82
Chapter 6.3 --- The Relative Importance of Each Set of Features --- p.84
Chapter 6.4 --- The Effect of Removing Timing Information --- p.92
Chapter 6.5 --- Chapter Summary --- p.96
Chapter 7 --- Conclusions and Future Work --- p.98
Chapter 7.1 --- Contributions --- p.98
Chapter 7.2 --- Future Works --- p.100
Chapter 7.2.1 --- Further Extension of the Framework --- p.100
Chapter 7.2.2 --- Wider Applications of the Framework --- p.105
Bibliography --- p.106

Les besoins croissants en ressources lexicales et le succès des projets de développement coopératif comme LINUX convergent vers l'idée d'accumuler des données lexicales multilingues de grande taille et de grande richesse par construction coopérative sur la Toile et utilisation "mutualisée". Les contributeurs fourniraient eux-mêmes ces informations sous une forme standardisée grâce à un environnement adapté. L'étude du contexte actuel de la dictionnairique nous a conduit à l'identification de problèmes difficiles tels que la structuration et la manipulation de données hétérogènes, la visualisation d'une grande quantité de données lexicales multilingues et la construction en coopération par des personnes aux compétences diverses. Des prototypages et des expérimentations portant sur la consultation de ressources hétérogènes, l'enrichissement et personnalisation du résultat, la construction de ressources en ligne et la rédaction d'articles avec un éditeur standard nous ont permis de résoudre séparément ces problèmes. Cela nous a permis de concevoir un environnement complet de "bases lexicales" répondant à tous ces problèmes se plaçant au dessus des SGBD utilisés pour le stockage et intégrant un serveur pour la construction coopérative. Son noyau inclut un formalisme générique de définition de structures lexicales inspiré de SUBLIM de G. Sérasset, mais complété et réexprimé en XML. Cet environnement est actuellement appliqué au projet Papillon de développement par des bénévoles sur Internet d'une base lexicale comprenant cinq langues. L'architecture de la base est constituée d'un dictionnaire monolingue pour chaque langue et d'un dictionnaire pivot d'acceptions interlingues reliant les articles monolingues (lexies) dont la structure provient de la lexicologie combinatoire. Enfin, l'architecture du serveur assez générique devrait être réutilisée dans d'autres contextes (mémoires de traduction, outils pour traducteurs, communication et RI multilingue, annotations multimédia).

abstract: Contention based IEEE 802.11MAC uses the binary exponential backoff algorithm (BEB) for the contention resolution. The protocol suffers poor performance in the heavily loaded networks and MANETs, high collision rate and packet drops, probabilistic delay guarantees, and unfairness. Many backoff strategies were proposed to improve the performance of IEEE 802.11 but all ignore the network topology and demand. Persistence is defined as the fraction of time a node is allowed to transmit, when this allowance should take into account topology and load, it is topology and load aware persistence (TLA). We develop a relation between contention window size and the TLA-persistence. We implement a new backoff strategy where the TLA-persistence is defined as the lexicographic max-min channel allocation. We use a centralized algorithm to calculate each node's TLApersistence and then convert it into a contention window size. The new backoff strategy is evaluated in simulation, comparing with that of the IEEE 802.11 using BEB. In most of the static scenarios like exposed terminal, flow in the middle, star topology, and heavy loaded multi-hop networks and in MANETs, through the simulation study, we show that the new backoff strategy achieves higher overall average throughput as compared to that of the IEEE 802.11 using BEB.
Dissertation/Thesis
M.S. Computer Science 2013

The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. This graph parameter was introduced by Chartrand et al. in 2008. The problem has garnered considerable interest and several variants of the initial version have since been introduced. The rainbow connection number of a connected graph G is denoted by rc(G). It can be shown that the rainbow connection number of a tree on n vertices is n -1. Hence |G|-1 is an upper bound for rc(G)of any non-trivial graph G. For all non-trivial, bridge-less and connected graphs G, Basavaraju etal. Showed that rc(G) can be upper-bounded by a quadratic function of its radius. In addition they also proved the tightness of the bound. It is clear that we cannot hope to get an upper-bound better than |G| - 1 in the case of graphs with bridges. An immediate and natural question is the following: Are there classes of bridge-less graphs whose rainbow connection numbers are linear functions of their radii? This question is of particular interest since the diameter is a trivial lower bound for rc(G). We answer in affirmative to the above question. In particular we studied three (graph) product operations (Cartesian, Lexicographic and Strong) and the graph powering operation. We were able to show that the rainbow connection number of the graph resulting from any of the above graph operations is upper-bounded by 2r(G)+c, where r(G) is radius of the resultant graph and c ε {0, 1, 2}.

A sophisticated system of finger-counting was developed in Greco-Roman antiquity and was used until the middle ages. It enabled people to count to high amounts on their fingers. In the early middle ages, this system gave emergence to a pictorial tradition that lasted centuries: throughout the middle ages, large numbers of illuminated manuscripts with depictions of number-gestures circulated across Europe. There is no doubt that finger-counting illuminated manuscripts carried a heavy cultural and intellectual weight in the middle ages. This is evident from the peculiar form of their images, the pervasiveness of the finger system in medieval society, and the diffusion and dynamism of the manuscript tradition. However, this tradition is still widely unexplored. Not only a broad comparative analysis is wanting, but many sources remain unexamined. This dissertation analyses two twelfth-thirteenth centuries little-studied Portuguese grammatical codices. Although these codices include finger-counting images – typically associated with arithmetic and astronomy – they are grammatical compilations. To properly evaluate this seeming misplacement, this dissertation contextualizes the codices in the intellectual and cultural framework of coeval Portuguese and European monasticism. As this dissertation shows, the finger system was a polyvalent medium that crossed discipline barriers and was even useful for the teaching of grammar. Furthermore, the finger-counting images are impregnated with rhetorical devices, including a variety of visual puns – functioning as “visual etymologies.” The Portuguese codices are thus a befitting framing for the finger-counting images. The nature of the problem required a multidisciplinary approach that benefitted from art history, latin, neuroscience, mathematics, computer science, and paleography.
Na antiguidade Greco-Romana, desenvolveu-se um sofisticado sistema de contagem digital, o qual foi usado até à idade média. Este sistema permitia contar até grandes quantidades usando apenas os dedos. Nos inícios da idade média, este sistema deu origem a uma tradição pictórica que se prolongou por séculos: ao longo da idade média, circularam pela Europa, em grandes números, manuscritos iluminados com representações de gestos numéricos. Não existem dúvidas de que os manuscritos iluminados com contagem digital transportavam consigo um grande peso cultural e intelectual, na idade média. Isto é evidente pela forma peculiar das suas imagens, pela ubiquidade do sistema digital na sociedade medieval, e pela difusão e dinamismo da tradição manuscrita. No entanto, esta tradição permanece ainda largamente inexplorada. Não só uma análise comparativa alargada está por fazer, como muitas fontes ainda não foram examinadas. Esta dissertação analisa dois manuscritos gramaticais Portugueses pouco estudados, dos séculos XII-XIII. Apesar destes códices incluírem imagens de contagem digital – tipicamente associada à aritmética e à astronomia – eles são compilações gramaticais. Para adequadamente avaliar o aparente extravio, este estudo contextualiza os códices no panorama cultural e intelectual do monasticismo coevo Português e Europeu. Tal como revela esta dissertação, o sistema digital era um medium polivalente que cruzava fronteiras entre disciplinas, e que era útil mesmo no ensino da gramática. Para além disso, as imagens de contagem digital estão impregnadas de dispositivos retóricos, incluindo uma série de trocadilhos visuais – funcionando como “etimologias visuais.” Os códices portugueses são, pois, um enquadramento adequado para estas imagens. A natureza do problema em estudo requereu uma abordagem multidisciplinar, que beneficiou da história da arte, do latim, da neurociência, da matemática, da informática, e da paleografia.

Combinatorial objects can be represented by strings, such as 21534 for the permutation (1 2) (3 5 4), or 110100 for the binary tree corresponding to the balanced parentheses (()()). Given a string s = s1 s2 sn, the right-shift operation shift(s, i, j) replaces the substring si si+1..sj by si+1..sj si. In other words, si is right-shifted into position j by applying the permutation (j j−1 .. i) to the indices of s. Right-shifts include prefix-shifts (i = 1) and adjacent-transpositions (j = i+1). A fixed-content language is a set of strings that contain the same multiset of symbols. Given a fixed-content language, a shift Gray code is a list of its strings where consecutive strings differ by a shift. This thesis asks if shift Gray codes exist for a variety of combinatorial objects. This abstract question leads to a number of practical answers. The first prefix-shift Gray code for multiset permutations is discovered, and it provides the first algorithm for generating multiset permutations in O(1)-time while using O(1) additional variables. Applications of these results include more efficient exhaustive solutions to stacker-crane problems, which are natural NP-complete traveling salesman variants. This thesis also produces the fastest algorithm for generating balanced parentheses in an array, and the first minimal-change order for fixed-content necklaces and Lyndon words. These results are consequences of the following theorem: Every bubble language has a right-shift Gray code. Bubble languages are fixed-content languages that are closed under certain adjacent-transpositions. These languages generalize classic combinatorial objects: k-ary trees, ordered trees with fixed branching sequences, unit interval graphs, restricted Schr oder and Motzkin paths, linear-extensions of B-posets, and their unions, intersections, and quotients. Each Gray code is circular and is obtained from a new variation of lexicographic order known as cool-lex order. Gray codes using only shift(s, 1, n) and shift(s, 1, n−1) are also found for multiset permutations. A universal cycle that omits the last (redundant) symbol from each permutation is obtained by recording the first symbol of each permutation in this Gray code. As a special case, these shorthand universal cycles provide a new fixed-density analogue to de Bruijn cycles, and the first universal cycle for the "middle levels" (binary strings of length 2k + 1 with sum k or k + 1).