Spelling suggestions: "subject:"amathematical linguistics"" "subject:"dmathematical linguistics""
21 |
Modelling syntactic gradience with loose constraint-based parsing Modélisation de la gradience syntaxique par analyse relâchée à base de contraintes /Prost, Jean-Philippe. January 2008 (has links)
Thesis (PhD)--Macquarie University, Division of Information and Communication Sciences, Department of Computing, 2008. / Thesis submitted for the joint institutional requirements for the double-badged degree of Doctor of Philosophy and Docteur de l'Université de Provence, Spécialité : Informatique. Includes bibliography (p. 229-240) and index.
|
22 |
The complexity of unavoidable word patternsSauer, Paul Van der Merwe 12 1900 (has links)
Bibliography: pages 192-195 / The avoidability, or unavoidability of patterns in words over finite alphabets has
been studied extensively. The word α over a finite set A is said to be unavoidable
for an infinite set B+ of nonempty words over a finite set B if, for all but finitely
many elements w of B+, there exists a semigroup morphism φ ∶ A+ → B+ such that
φ(α) is a factor of w.
In this treatise, we start by presenting a historical background of results that are
related to unavoidability. We present and discuss the most important theorems
surrounding unavoidability in detail.
We present various complexity-related properties of unavoidable words. For words
that are unavoidable, we provide a constructive upper bound to the lengths of
words that avoid them. In particular, for a pattern α of length n over an alphabet
of size r, we give a concrete function N(n, r) such that no word of length N(n, r)
over the alphabet of size r avoids α.
A natural subsequent question is how many unavoidable words there are. We show
that the fraction of words that are unavoidable drops exponentially fast in the
length of the word. This allows us to calculate an upper bound on the number of
unavoidable patterns for any given finite alphabet.
Subsequently, we investigate computational aspects of unavoidable words. In
particular, we exhibit concrete algorithms for determining whether a word is
unavoidable. We also prove results on the computational complexity of the problem
of determining whether a given word is unavoidable. Specifically, the
NP-completeness of the aforementioned problem is established. / Decision Sciences / D. Phil. (Operations Research)
|
23 |
Modelling syntactic gradience with loose constraint-based parsing: Modélisation de la gradience syntaxique par analyse relâchée à base de contraintes / Modélisation de la gradience syntaxique par analyse relâchée à base de contraintesProst, Jean-Philippe January 2008 (has links)
Thesis submitted for the joint institutional requirements for the double-badged degree of Doctor of Philosophy and Docteur de l'Université de Provence, Spécialité : Informatique. / Thesis (PhD)--Macquarie University, Division of Information and Communication Sciences, Department of Computing, 2008. / Includes bibliography (p. 229-240) and index. / Introduction -- Background -- A model-theoretic framework for PG -- Loose constraint-based parsing -- A computational model for gradience -- Conclusion. / The grammaticality of a sentence has conventionally been treated in a binary way: either a sentence is grammatical or not. A growing body of work, however, focuses on studying intermediate levels of acceptability, sometimes referred to as gradience. To date, the bulk of this work has concerned itself with the exploration of human assessments of syntactic gradience. This dissertation explores the possibility to build a robust computational model that accords with these human judgements. -- We suggest that the concepts of Intersective Gradience and Subsective Gradience introduced by Aarts for modelling graded judgements be extended to cover deviant language. Under such a new model, the problem then raised by gradience is to classify an utterance as a member of a specific category according to its syntactic characteristics. More specifically, we extend Intersective Gradience (IG) so that it is concerned with choosing the most suitable syntactic structure for an utterance among a set of candidates, while Subsective Gradience (SG) is extended to be concerned with calculating to what extent the chosen syntactic structure is typical from the category at stake. IG is addressed in relying on a criterion of optimality, while SG is addressed in rating an utterance according to its grammatical acceptability. As for the required syntactic characteristics, which serve as features for classifying an utterance, our investigation of different frameworks for representing the syntax of natural language shows that they can easily be represented in Model-Theoretic Syntax; we choose to use Property Grammars (PG), which offers to model the characterisation of an utterance. We present here a fully automated solution for modelling syntactic gradience, which characterises any well formed or ill formed input sentence, generates an optimal parse for it, then rates the utterance according to its grammatical acceptability. -- Through the development of such a new model of gradience, the main contribution of this work is three-fold. -- First, we specify a model-theoretic logical framework for PG, which bridges the gap observed in the existing formalisation regarding the constraint satisfaction and constraint relaxation mechanisms, and how they relate to the projection of a category during the parsing process. This new framework introduces the notion of loose satisfaction, along with a formulation in first-order logic, which enables reasoning about the characterisation of an utterance. -- Second, we present our implementation of Loose Satisfaction Chart Parsing (LSCP), a dynamic programming approach based on the above mechanisms, which is proven to always find the full parse of optimal merit. Although it shows a high theoretical worst time complexity, it performs sufficiently well with the help of heuristics to let us experiment with our model of gradience. -- And third, after postulating that human acceptability judgements can be predicted by factors derivable from LSCP, we present a numeric model for rating an utterance according to its syntactic gradience. We measure a good correlation with grammatical acceptability by human judgements. Moreover, the model turns out to outperform an existing one discussed in the literature, which was experimented with parses generated manually. / Mode of access: World Wide Web. / xxviii, 283 p. ill
|
Page generated in 0.1254 seconds