Mathematics as Grammar

Tésis de Doctorado en Filosofía, Universidad de Indiana, Bloomington, 2000

Robust handling of out-of-vocabulary words in deep language processing

Tese de doutoramento, Informática (Ciências da Computação), Universidade de Lisboa, Faculdade de Ciências, 2014

Constituição e transcendência: os casos dos regimes comunitários do entre-guerras

Tede de Doutoramento, na especialidade de Ciências Políticas apresentada à FDUNL

Automatic evolution of conceptual building architectures

This thesis describes research in which genetic programming is used to automatically evolve shape grammars that construct three dimensional models of possible external building architectures. A completely automated fitness function is used, which evaluates the three dimensional building models according to different geometric properties such as surface normals, height, building footprint, and more. In order to evaluate the buildings on the different criteria, a multi-objective fitness function is used. The results obtained from the automated system were successful in satisfying the multiple objective criteria as well as creating interesting and unique designs that a human-aided system might not discover. In this study of evolutionary design, the architectures created are not meant to be fully functional and structurally sound blueprints for constructing a building, but are meant to be inspirational ideas for possible architectural designs. The evolved models are applicable for today's architectural industries as well as in the video game and movie industries. Many new avenues for future work have also been discovered and highlighted.

Quantification de la relation séquence-activité de l’ARN par prédiction de structure tridimensionnelle

Dans un premier temps, nous avons modélisé la structure d’une famille d’ARN avec une grammaire de graphes afin d’identifier les séquences qui en font partie. Plusieurs autres méthodes de modélisation ont été développées, telles que des grammaires stochastiques hors-contexte, des modèles de covariance, des profils de structures secondaires et des réseaux de contraintes. Ces méthodes de modélisation se basent sur la structure secondaire classique comparativement à nos grammaires de graphes qui se basent sur les motifs cycliques de nucléotides. Pour exemplifier notre modèle, nous avons utilisé la boucle E du ribosome qui contient le motif Sarcin-Ricin qui a été largement étudié depuis sa découverte par cristallographie aux rayons X au début des années 90. Nous avons construit une grammaire de graphes pour la structure du motif Sarcin-Ricin et avons dérivé toutes les séquences qui peuvent s’y replier. La pertinence biologique de ces séquences a été confirmée par une comparaison des séquences d’un alignement de plus de 800 séquences ribosomiques bactériennes. Cette comparaison a soulevée des alignements alternatifs pour quelques unes des séquences que nous avons supportés par des prédictions de structures secondaires et tertiaires. Les motifs cycliques de nucléotides ont été observés par les membres de notre laboratoire dans l'ARN dont la structure tertiaire a été résolue expérimentalement. Une étude des séquences et des structures tertiaires de chaque cycle composant la structure du Sarcin-Ricin a révélé que l'espace des séquences dépend grandement des interactions entre tous les nucléotides à proximité dans l’espace tridimensionnel, c’est-à-dire pas uniquement entre deux paires de bases adjacentes. Le nombre de séquences générées par la grammaire de graphes est plus petit que ceux des méthodes basées sur la structure secondaire classique. Cela suggère l’importance du contexte pour la relation entre la séquence et la structure, d’où l’utilisation d’une grammaire de graphes contextuelle plus expressive que les grammaires hors-contexte. Les grammaires de graphes que nous avons développées ne tiennent compte que de la structure tertiaire et négligent les interactions de groupes chimiques spécifiques avec des éléments extra-moléculaires, comme d’autres macromolécules ou ligands. Dans un deuxième temps et pour tenir compte de ces interactions, nous avons développé un modèle qui tient compte de la position des groupes chimiques à la surface des structures tertiaires. L’hypothèse étant que les groupes chimiques à des positions conservées dans des séquences prédéterminées actives, qui sont déplacés dans des séquences inactives pour une fonction précise, ont de plus grandes chances d’être impliqués dans des interactions avec des facteurs. En poursuivant avec l’exemple de la boucle E, nous avons cherché les groupes de cette boucle qui pourraient être impliqués dans des interactions avec des facteurs d'élongation. Une fois les groupes identifiés, on peut prédire par modélisation tridimensionnelle les séquences qui positionnent correctement ces groupes dans leurs structures tertiaires. Il existe quelques modèles pour adresser ce problème, telles que des descripteurs de molécules, des matrices d’adjacences de nucléotides et ceux basé sur la thermodynamique. Cependant, tous ces modèles utilisent une représentation trop simplifiée de la structure d’ARN, ce qui limite leur applicabilité. Nous avons appliqué notre modèle sur les structures tertiaires d’un ensemble de variants d’une séquence d’une instance du Sarcin-Ricin d’un ribosome bactérien. L’équipe de Wool à l’université de Chicago a déjà étudié cette instance expérimentalement en testant la viabilité de 12 variants. Ils ont déterminé 4 variants viables et 8 létaux. Nous avons utilisé cet ensemble de 12 séquences pour l’entraînement de notre modèle et nous avons déterminé un ensemble de propriétés essentielles à leur fonction biologique. Pour chaque variant de l’ensemble d’entraînement nous avons construit des modèles de structures tertiaires. Nous avons ensuite mesuré les charges partielles des atomes exposés sur la surface et encodé cette information dans des vecteurs. Nous avons utilisé l’analyse des composantes principales pour transformer les vecteurs en un ensemble de variables non corrélées, qu’on appelle les composantes principales. En utilisant la distance Euclidienne pondérée et l’algorithme du plus proche voisin, nous avons appliqué la technique du « Leave-One-Out Cross-Validation » pour choisir les meilleurs paramètres pour prédire l’activité d’une nouvelle séquence en la faisant correspondre à ces composantes principales. Finalement, nous avons confirmé le pouvoir prédictif du modèle à l’aide d’un nouvel ensemble de 8 variants dont la viabilité à été vérifiée expérimentalement dans notre laboratoire. En conclusion, les grammaires de graphes permettent de modéliser la relation entre la séquence et la structure d’un élément structural d’ARN, comme la boucle E contenant le motif Sarcin-Ricin du ribosome. Les applications vont de la correction à l’aide à l'alignement de séquences jusqu’au design de séquences ayant une structure prédéterminée. Nous avons également développé un modèle pour tenir compte des interactions spécifiques liées à une fonction biologique donnée, soit avec des facteurs environnants. Notre modèle est basé sur la conservation de l'exposition des groupes chimiques qui sont impliqués dans ces interactions. Ce modèle nous a permis de prédire l’activité biologique d’un ensemble de variants de la boucle E du ribosome qui se lie à des facteurs d'élongation.

Avoir ou être dans les formes verbales composées : conflits, usages et choix des grammairiens dans l'histoire du français de 1500 à 1789

En français contemporain, l’hésitation dans le choix entre être et avoir comme auxiliaire dans les formes verbale composées (par ex. le passé composé) de certains verbes intransitifs (par ex. tomber), surtout dans des variétés non standards du français, démonte clairement l’écart qui existe entre le français normé et le français oral quotidien. Cette hésitation, voire l’incertitude, dans le choix de l’auxiliaire n’est pas une particularité arbitraire ou aléatoire de la langue contemporaine; elle s’inscrit plutôt dans une tendance diachronique et pan-romane que l’on a pu observer dans la langue française depuis son émancipation du latin. Notre étude, qui se fonde sur la théorie de la grammaticalisation, propose une analyse du discours grammatical de 1500 – époque où sont apparues les premières grammaires du français – jusqu’à 1789 avec la Révolution française, signalant le moment où la langue se serait stabilisée et aurait adopté sa forme moderne. Nous divisons les trois siècles de notre étude en quatre périodes distinctes, déjà bien établies dans les études historiques. Ce sont : - Le XVIe siècle (1530-1599) - La première moitié de la période classique (1600-1650) - La deuxième moitié de la période classique (1651-1715) - Le Siècle des lumières (1716-1789) Pour chacune des quatre périodes, l’analyse se fait en trois temps. Premièrement, nous recensons les grammairiens, les lexicographes et les essayistes qui se sont prononcés, soit explicitement, soit implicitement, sur l’emploi des auxiliaires être et avoir dans les formes verbales composées (FVC). Nous identifions, là où cela est possible, le dialecte maternel de chaque auteur et son modèle d’usage. Deuxièmement, nous résumons les observations et les commentaires sur l’emploi des auxiliaires dans les FVC formulés par chaque auteur, y compris les tentatives d’explication quant à la variation dans le choix de l’auxiliaire. Finalement, nous rapportons la description de l’emploi des auxiliaires dans les FVC proposée par des historiens de la langue française pour la période en question. Notre étude nous permet de confirmer, en ce qui concerne les FVC, certaines tendances déjà reconnues dans la langue française et d’en identifier d’autres. Également, nous avons pu repérer, voire circonscrire des facteurs qui ont eu une influence sur le choix, tels les verbes plus sensibles à l’alternance, les grammairiens dont l’autorité s’est imposé plus que d’autres ou avant les autres dans l’établissement de la norme sur ce point, les contextes sociaux dans lesquels le débat a eu lieu et la période pendant laquelle les préoccupations sur ce choix était les plus intenses.

Design and Development of an Adaptable Frame -Based System for Dravidian Language Processing

This work is aimed at building an adaptable frame-based system for processing Dravidian languages. There are about 17 languages in this family and they are spoken by the people of South India.Karaka relations are one of the most important features of Indian languages. They are the semabtuco-syntactic relations between verbs and other related constituents in a sentence. The karaka relations and surface case endings are analyzed for meaning extraction. This approach is comparable with the borad class of case based grammars.The efficiency of this approach is put into test in two applications. One is machine translation and the other is a natural language interface (NLI) for information retrieval from databases. The system mainly consists of a morphological analyzer, local word grouper, a parser for the source language and a sentence generator for the target language. This work make contributios like, it gives an elegant account of the relation between vibhakthi and karaka roles in Dravidian languages. This mapping is elegant and compact. The same basic thing also explains simple and complex sentence in these languages. This suggests that the solution is not just ad hoc but has a deeper underlying unity. This methodology could be extended to other free word order languages. Since the frame designed for meaning representation is general, they are adaptable to other languages coming in this group and to other applications.

CD-Systems of Restarting Automata

Die vorliegende Arbeit behandelt Restartautomaten und Erweiterungen von Restartautomaten. Restartautomaten sind ein Werkzeug zum Erkennen formaler Sprachen. Sie sind motiviert durch die linguistische Methode der Analyse durch Reduktion und wurden 1995 von Jancar, Mráz, Plátek und Vogel eingeführt. Restartautomaten bestehen aus einer endlichen Kontrolle, einem Lese/Schreibfenster fester Größe und einem flexiblen Band. Anfänglich enthält dieses sowohl die Eingabe als auch Bandbegrenzungssymbole. Die Berechnung eines Restartautomaten läuft in so genannten Zyklen ab. Diese beginnen am linken Rand im Startzustand, in ihnen wird eine lokale Ersetzung auf dem Band durchgeführt und sie enden mit einem Neustart, bei dem das Lese/Schreibfenster wieder an den linken Rand bewegt wird und der Startzustand wieder eingenommen wird. Die vorliegende Arbeit beschäftigt sich hauptsächlich mit zwei Erweiterungen der Restartautomaten: CD-Systeme von Restartautomaten und nichtvergessende Restartautomaten. Nichtvergessende Restartautomaten können einen Zyklus in einem beliebigen Zustand beenden und CD-Systeme von Restartautomaten bestehen aus einer Menge von Restartautomaten, die zusammen die Eingabe verarbeiten. Dabei wird ihre Zusammenarbeit durch einen Operationsmodus, ähnlich wie bei CD-Grammatik Systemen, geregelt. Für beide Erweiterungen zeigt sich, dass die deterministischen Modelle mächtiger sind als deterministische Standardrestartautomaten. Es wird gezeigt, dass CD-Systeme von Restartautomaten in vielen Fällen durch nichtvergessende Restartautomaten simuliert werden können und andererseits lassen sich auch nichtvergessende Restartautomaten durch CD-Systeme von Restartautomaten simulieren. Des Weiteren werden Restartautomaten und nichtvergessende Restartautomaten untersucht, die nichtdeterministisch sind, aber keine Fehler machen. Es zeigt sich, dass diese Automaten durch deterministische (nichtvergessende) Restartautomaten simuliert werden können, wenn sie direkt nach der Ersetzung einen neuen Zyklus beginnen, oder ihr Fenster nach links und rechts bewegen können. Außerdem gilt, dass alle (nichtvergessenden) Restartautomaten, die zwar Fehler machen dürfen, diese aber nach endlich vielen Zyklen erkennen, durch (nichtvergessende) Restartautomaten simuliert werden können, die keine Fehler machen. Ein weiteres wichtiges Resultat besagt, dass die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt den Zyklus beenden, genau die deterministischen kontextfreien Sprachen erkennen, wohingegen die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen ohne diese Einschränkung echt mehr, nämlich die links-rechts regulären Sprachen, erkennen. Damit werden zum ersten Mal Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt ihren Zyklus beenden, von Restartautomaten desselben Typs ohne diese Einschränkung getrennt. Besonders erwähnenswert ist hierbei, dass beide Automatentypen wohlbekannte Sprachklassen beschreiben.

The Informational Complexity of Learning from Examples

This thesis attempts to quantify the amount of information needed to learn certain tasks. The tasks chosen vary from learning functions in a Sobolev space using radial basis function networks to learning grammars in the principles and parameters framework of modern linguistic theory. These problems are analyzed from the perspective of computational learning theory and certain unifying perspectives emerge.

The Logical Problem of Language Change

This paper considers the problem of language change. Linguists must explain not only how languages are learned but also how and why they have evolved along certain trajectories and not others. While the language learning problem has focused on the behavior of individuals and how they acquire a particular grammar from a class of grammars ${cal G}$, here we consider a population of such learners and investigate the emergent, global population characteristics of linguistic communities over several generations. We argue that language change follows logically from specific assumptions about grammatical theories and learning paradigms. In particular, we are able to transform parameterized theories and memoryless acquisition algorithms into grammatical dynamical systems, whose evolution depicts a population's evolving linguistic composition. We investigate the linguistic and computational consequences of this model, showing that the formalization allows one to ask questions about diachronic that one otherwise could not ask, such as the effect of varying initial conditions on the resulting diachronic trajectories. From a more programmatic perspective, we give an example of how the dynamical system model for language change can serve as a way to distinguish among alternative grammatical theories, introducing a formal diachronic adequacy criterion for linguistic theories.

Unifying syntactic theory and sentence processing difficulty through a connectionist minimalist parser

Syntactic theory provides a rich array of representational assumptions about linguistic knowledge and processes. Such detailed and independently motivated constraints on grammatical knowledge ought to play a role in sentence comprehension. However most grammar-based explanations of processing difficulty in the literature have attempted to use grammatical representations and processes per se to explain processing difficulty. They did not take into account that the description of higher cognition in mind and brain encompasses two levels: on the one hand, at the macrolevel, symbolic computation is performed, and on the other hand, at the microlevel, computation is achieved through processes within a dynamical system. One critical question is therefore how linguistic theory and dynamical systems can be unified to provide an explanation for processing effects. Here, we present such a unification for a particular account to syntactic theory: namely a parser for Stabler's Minimalist Grammars, in the framework of Smolensky's Integrated Connectionist/Symbolic architectures. In simulations we demonstrate that the connectionist minimalist parser produces predictions which mirror global empirical findings from psycholinguistic research.

Subject-to-subject raising and the syntax of tense in L2 Spanish: a full access approach

This paper investigates the acquisition of syntax in L2 grammars. We tested adult L2 speakers of Spanish (English L1) on the feature specification of T(ense), which is different in English and Spanish in so-called subject-to-subject raising structures. We present experimental results with the verb parecer “to seem/to appear” in different tenses, with and without experiencers, and with Tense Phrase (TP), verb phrase (vP) and Adjectival Phrase (AP) complements. The results show that advanced L2 learners can perform just like native Spanish speakers regarding grammatical knowledge in this domain, although the subtle differences between both languages are not explicitly taught. We argue that these results support Full Access approaches to Universal Grammar (UG) in L2 acquisition, by providing evidence that uninterpretable syntactic features can be learned in adult L2, even when such features are not directly instantiated in the same grammatical domain in the L1 grammar.

The syntax-semantics of bare and definite plural subjects in the L2 Spanish of English natives

This study investigates the extent to which advanced native-English L2 learners of Spanish come to acquire restrictions on bare plural preverbal subjects in L2 Spanish (e.g. gatos “cats” vs. definite plurals such as los gatos “the cats”). It tests L2 knowledge of available semantic readings of bare plurals and definite plurals in Spanish, where [+specific] and [+generic] interpretations are syntactically represented differently from English. Assuming L1 transfer, and in view of a potential subset/superset relationship of the two grammars, the learning task in this domain is not a straightforward one. Target acquisition requires both grammatical expansion and retraction; Spanish definite plural subjects require the addition of an L1-unavailable [+generic] reading, while a loss of an L1-available [+generic] reading for preverbal subject bare plurals is required. The results and analysis show that advanced L2 learners of Spanish (English L1) can circumvent a superficial subset/superset learnability problem by means of feature resetting in line with the Nominal Mapping Parameter.

Heritage speaker competence differences, language change and input type: inflected infinitives in Heritage Brazilian Portuguese

It has been argued that colloquial dialects of Brazilian Portuguese (BP) have undergone significant linguistic change resulting in the loss of inflected infinitives (e.g., Pires, 2002, 2006). Since BP adults, at least educated ones, have complete knowledge of inflected infinitives, the implicit claim is that they are transmitted via formal education in the standard dialect. In the present article, I test one of the latent predictions of such claims; namely, the fact that heritage speakers of BP who lack formal education in the standard dialect should never develop native-like knowledge of inflected infinitives. In doing so, I highlight two significant implications (a) that heritage speaker grammars are a good source for testing dialectal variation and language change proposals and (b) incomplete acquisition and/or attrition are not the only sources of heritage language competence differences. Employing the syntactic and semantic tests of Rothman and Iverson (2007), I compare heritage speakers' knowledge to Rothman and Iverson's advanced adult L2 learners and educated native controls. Unlike the latter groups, the data for heritage speakers indicate that they do not have target knowledge of inflected infinitives, lending support to Pires' claims, suggesting that literacy plays a significant role in the acquisition of this grammatical property in BP.