A critical aspect of the non-native students' academic adjustment in English-speaking countries is their English language ability, including their reading fluency and comprehension. Even when these students are considered proficient readers of English at an advanced level, they display different reading processes when dealing with the complex input of a second language (L2) text, as compared with their native English reading classmates. Despite the importance of comprehending highly sophisticated academic reading in international education, there is a lack of research in the field as to how advanced L2 readers cope with the texts with which the highly educated native speakers engage. This study, therefore, examined meaning construction processes of highly proficient L2 readers during reading the texts that vary in degree of cohesion. To describe readers' approaches to text cohesion and also recognize readers' perceptions of their own process, the study used a close observation of reading processes of nine highly proficient graduate students at a U.S. university with the use of qualitative research methods. The students participated in two interviews - pre-reading interview and post-reading cognitive interview - and two think-aloud verbal protocol sessions. Participants read one high-cohesive and one low-cohesive text during the think-aloud sessions, and then shared the meaning they constructed from the texts and also their thinking about the texts. The data from the instruments were analyzed qualitatively using a grounded theory approach. The results of the study reveal that the readers' meaning representation processes emerging as the result of reader and text interaction display differences at the local and global levels of processing of the high- and low-cohesive text. The processing differences between the readers are most apparent in texts with low text cohesion. The low cohesive text allowed the readers, especially, the creators of meaning, to conduct more elaborative processing compared to their performance with the high-cohesive one, in which all readers attempted to create a catalogue of facts trusting the explicitly provided text cohesion features. These results have implications for theories of text processing as well as the design of materials and instruction used for advanced L2 readers and lower level L2 readers.

Searching for textual information has become an important activity on the web. To satisfy the rising demand and user expectations, search systems should be fast, scalable and deliver relevant results. To decide which objects should be retrieved, search systems should compare holistic meanings of queries and text document objects, as perceived by humans. Existing techniques do not enable correct comparison of composite holistic meanings like: "evidences on role of DR2 gene in development of diabetes in Caucasian population", which is composed of multiple elementary meanings: "evidence", "DR2 gene", etc. Thus these techniques can not discern objects that have a common set of keywords but convey different meanings. Hence we need new methods to compare composite meanings for superior search quality. In distributed search engines, for scalability, speed and efficiency, index entries should be systematically distributed across multiple index-server nodes based on the meaning of the objects. Furthermore, queries should be selectively sent to those index nodes which have relevant entries. This requires an overlay Semantic Routed Network which will route messages, based on meaning. This network will consist of fast response networking appliances called semantic routers. These appliances need to: (a) carry out sophisticated meaning comparison computations at high speed; and (b) have the right kind of behavior to automatically organize an optimal index system. This dissertation presents the following artifacts that enable the above requirements: (1) An algebraic theory, a design of a data structure and related techniques to efficiently compare composite meanings. (2) Algorithms and accelerator architectures for high speed meaning comparisons inside semantic routers and index-server nodes. (3) An overlay network to deliver search queries to the index nodes based on meanings. (4) Algorithms to construct a self-organizing, distributed meaning based index system. The proposed techniques can compare composite meanings ~105 times faster than an equivalent software code and existing hardware designs. Whereas, the proposed index organization approach can lead to 33% savings in number of servers and power consumption in a model search engine having 700,000 servers. Therefore, using all these techniques, it is possible to design a Semantic Routed Network which has a potential to improve search results and response time, while saving resources.

Tout d’abord perçue comme un phénomène marginal, presque un accident en langue, on considère aujourd’hui que la polysémie fait partie intégrante des systèmes linguistiques. De nombreuses théories se sont intéressées au phénomène des unités à sens multiples et reliés. La première partie de notre travail en dresse un panorama non exhaustif mais révélateur, montrant comment et pourquoi la polysémie s’est peu à peu imposée comme un phénomène incontournable qui doit nécessairement être au cœur de tout modèle de la signification. Aussi, à partir de la distinction établie par G. Kleiber (1999), nous considérons deux grands courants selon le rapport établi entre signification, référence et polysémie. Le premier décrit la polysémie en termes de sens premier référentiel dont sont dérivés des sens secondaires (courant objectiviste). Le second l’analyse en termes de potentiel sémantique aréférentiel à partir duquel est obtenu l’ensemble des sens du polysème par spécialisation ou enrichissement contextuel(le) (courant constructiviste). Notre réflexion porte ensuite sur la représentation de la signification des polysèmes – principalement des noms – en grammaire cognitive (R.W. Langacker). Nous postulons que toute expression est associée, dans l’appareil cognitif des locuteurs-auditeurs, à une structure conceptuelle d’informations représentant sa signification. Nous proposons une modélisation en réseau structuré autour de valeurs sémantiques plus ou moins schématiques et de sens élaborés. Ainsi, c’est la valeur la plus schématique qui permet de faire le lien en langue entre ses élaborations que sont les sens observables en discours. Sur la base des travaux de D. Tuggy (1993), nous déclinons les représentations de la signification des mots à sens multiples le long d’un continuum homonymie-polysémie-multifacialité-indétermination, selon les degrés d’enracinement, de saillance, et les possibilités d’accessibilité et d’activation des différents composants (valeur schématique et élaborations sémantiques). Et, nous mettons ainsi en avant certaines des régularités organisatrices propres aux représentations sémanticoconceptuelles des polysèmes nominaux, ainsi qu’une typologie des sens polysémiques. Nous abordons enfin la construction du sens en grammaire cognitive, notamment l’influence du contexte dans l’interprétation d’expressions complexes comportant un polysème. Ainsi, nous considérons qu’il s’agit d’un processus non modulaire, compositionnel et dynamique. L’analyse de syntagmes nominaux du type Adj-N et N-Adj révèle en outre certaines régularités dans l’activation des sens polysémiques des unités linguistiques mises en jeu, liées au cotexte (place et fonction de l’adjectif par rapport au substantif recteur) et au contexte extralinguistique / For a long time, polysemy used to be considered as a marginal or accidental phenomenon in language. Where as today, it is well known that polysemy is being part of linguistic systems. The first part of our thesis draws up a panorama of semantic theories dealing with polysemy. Although it is not exhaustive, it reveals how and why that phenomenon has become a problematic of the utmost significance in linguistics. From the distinction established by G. Kleiber (1999), we consider two major trends in accordance with the way they conceive the link between meaning, reference and polysemy. On one hand, polysemy is described in terms of one basic referential sense from which secondary senses derive (objectivism). On the other hand, polysemy is analyzed as an areferential semantic potential from which senses emerge by contextual mechanisms (constructivism). About the question of the meaning representation of polysems, we postulate that linguistic unities are associated with a structure of pieces of conceptual information into the mind of speakers-hearers, so that it is possible to elaborate of conceptual modeling of it. In the framework of Cognitive Grammar (R.W. Langacker), the structure is a network constituted of semantic values, which are more or less schematic, and of elaborated senses stemmed from them. The most schematic meaning corresponds to the linguistic conceptual link between its instantiations. Some elaborations are the senses which can be constructed in discourse. On the basis of D. Tuggy’s works (1993), we propose to organize the conceptual modelings of multiple meanings words along a continuum homonymy-polysemy-multifaciality-vagueness, in function of various parameters : entrenchment, cognitive salience, possibility of accessibility and of activation of the network components (schematic or elaborated values). So, we can highlight some organizational regularities specific to the semantic representation of polysems as well as a typology of polysemous senses. The third and last part of our thesis is dedicated to sense construction. In Cognitive Grammar, it is a non modulary, compositional and dynamic process. Focusing especially on the impact of context on the interpretation of complex expressions containing a polysem, the analysis of Adj-N and N-Adj noun phrases puts to the fore some regularities governing the activation of polysemic senses. These regularities are linked to the linguistic context (position and function of the adjective towards the qualified substantive) and to the extra-linguistic context

The overall goal of the field of natural language processing is to facilitate the communication between humans and computers, and to help humans with natural language problems such as translation. In this thesis, we focus on semantic language processing. Modelling semantics – the meaning of natural language – requires both a structure to hold the semantic information and a device that can enforce rules on the structure to ensure well-formed semantics while not being too computationally heavy. The devices used in natural language processing are preferably weighted to allow for comparison of the alternative semantic interpretations outputted by a device. The structure employed here is the abstract meaning representation (AMR). We show that AMRs representing well-formed semantics can be generated while leaving out AMRs that are not semantically well-formed. For this purpose, we use a type of graph grammar called contextual hyperedge replacement grammar (CHRG). Moreover, we argue that a more well-known subclass of CHRG – the hyperedge replacement grammar (HRG) – is not powerful enough for AMR generation. This is due to the limitation of HRG when it comes to handling co-references, which in its turn depends on the fact that HRGs only generate graphs of bounded treewidth. Furthermore, we also address the N best problem, which is as follows: Given a weighted device, return the N best (here: smallest-weighted, or more intuitively, smallest-errored) structures. Our goal is to solve the N best problem for devices capable of expressing sophisticated forms of semantic representations such as CHRGs. Here, however, we merely take a first step consisting in developing methods for solving the N best problem for weighted tree automata and some types of weighted acyclic hypergraphs.

The formalized and algorithmic study of human language within the field of Natural Language Processing (NLP) has motivated much theoretical work in the related field of formal languages, in particular the subfields of grammar and automata theory. Motivated and informed by NLP, the papers in this thesis explore the connections between expressibility – that is, the ability for a formal system to define complex sets of objects – and algorithmic complexity – that is, the varying amount of effort required to analyse and utilise such systems. Our research studies formal systems working not just on strings, but on more complex structures such as trees and graphs, in particular syntax trees and semantic graphs. The field of mildly context-sensitive languages concerns attempts to find a useful class of formal languages between the context-free and context-sensitive. We study formalisms defining two candidates for this class; tree-adjoining languages and the languages defined by linear context-free rewriting systems. For the former, we specifically investigate the tree languages, and define a subclass and tree automaton with linear parsing complexity. For the latter, we use the framework of parameterized complexity theory to investigate more deeply the related parsing problems, as well as the connections between various formalisms defining the class. The field of semantic modelling aims towards formally and accurately modelling not only the syntax of natural language statements, but also the meaning. In particular, recent work in semantic graphs motivates our study of graph grammars and graph parsing. To the best of our knowledge, the formalism presented in Paper III of this thesis is the first graph grammar where the uniform parsing problem has polynomial parsing complexity, even for input graphs of unbounded node degree.