Georgian is remarkably different from Indo-European languages. The language has several linguistic phenomena that are challenging both from theoretical and computational points of view. In addition, it is low- resourced and insufficiently studied from the computational point of view. In the thesis, we model morphology and syntax of a core fragment of the language in a formal grammar. Namely, the formal grammar is written in the HPSG framework - one of the most powerful grammar frameworks nowadays. We also implement the grammar in TRALE - a grammar implementation platform, which is faithful to "hand-written" HPSG-based grammars. Note that this is the first application of HPSG to Georgian.

This thesis presents a novel Dynamic Gesture Language Recognition (DGLR) system for human-robot and inter-robot communication. We developed and implemented an experimental setup consisting of a humanoid robot/android able to recognize and execute in real time all the arm gestures of the Dynamic Gesture Language (DGL) in similar way as humans do. Our DGLR system comprises two main subsystems: an image processing (IP) module and a linguistic recognition system (LRS) module. The IP module enables recognizing individual DGL gestures. In this module, we use the bag-of-features (BOFs) and a local part model approach for dynamic gesture recognition from images. Dynamic gesture classification is conducted using the BOFs and nonlinear support-vector-machine (SVM) methods. The multiscale local part model preserves the temporal context. The IP module was tested using two databases, one consisting of images of a human performing a series of dynamic arm gestures under different environmental conditions and a second database consisting of images of an android performing the same series of arm gestures. The linguistic recognition system (LRS) module uses a novel formal grammar approach to accept DGL-wise valid sequences of dynamic gestures and reject invalid ones. LRS consists of two subsystems: one using a Linear Formal Grammar (LFG) to derive the valid sequence of dynamic gestures and another using a Stochastic Linear Formal Grammar (SLFG) to occasionally recover gestures that were unrecognized by the IP module. Experimental results have shown that the DGLR system had a slightly better overall performance when recognizing gestures made by a human subject (98.92% recognition rate) than those made by the android (97.42% recognition rate).

Tree-based genetic programming (GP) has several known shortcomings: difficult adaptability to specific programming languages and environments, the problem of closure and multiple types, and the problem of declarative representation of knowledge. Most of the methods that try to solve these problems are based on formal grammars. The precise effect of their distinctive features is often difficult to analyse and a good comparison of performance in specific problems is missing. This thesis reviews three grammar-based methods: context-free grammar genetic programming (CFG-GP), including its variant GPHH recently applied to exam timetabling, grammatical evolution (GE), and LOGENPRO, it discusses how they solve the problems encountered by GP, and compares them in a series of experiments in six applications using success rates and derivation tree characteristics. The thesis demonstrates that neither GE nor LOGENPRO provide a substantial advantage over CFG-GP in any of the experiments, and analyses the differences between the effects of operators used in CFG-GP and GE. It also presents results from a highly efficient implementation of CFG-GP and GE.

I denna studie undersöks om styrdokument och läromedel korrelerar i sättet att se på grammatik i kursen Svenska 2 på gymnasiet, med utgångspunkt i begreppen funktionell respektive formell grammatikundervisning. Svenskämnets syfte, kunskapskrav och kommentarsmaterial tillsammans med grammatikavsnitten i läromedlen Svenska rum 2 och Svenska impulser 2 undersöks genom en kvalitativ innehållsanalys. Den teoretiska utgångspunkten är en begreppsdefinition av funktionell och formell grammatik som innefattar sex olika kriterier för varje begrepp. I resultatet framkommer att styrdokumenten ger uttryck för ett mer funktionellt perspektiv på grammatik, medan läromedlet Svenska rum 2 ger uttryck för ett formellt perspektiv på grammatik. Läromedlet Svenska impulser 2 har både ett funktionellt och formellt perspektiv på grammatik. Det finns en formell grund men läromedlet innehåller flera funktionella ansatser, därför har läromedlets grammatikavsnitt tolkats som mer funktionell än formell. Slutsatsen som kan dras är således att Svenska impulser 2 kan anses korrelera med styrdokumenten, trots att de funktionella aspekterna skulle kunna utvecklas ytterligare. Styrdokumenten kan dock inte anses korrelera med grammatikavsnittet i Svenska rum 2 efter begreppet funktionell grammatik. / This essay aims to examine whether or not the syllabi and teaching materials correlate in their views on grammar in the upper secondary school course Swedish 2, in regards to functional and formal grammar teaching. The aim of the subject, knowledge requirements and commentary materials, as well as the grammar sections of the teaching materials Svenska rum 2 and Svenska impulser 2, are examined through a qualitative text analysis. The theoretical assumption for the study is based on a definition of the concepts of functional and formal grammar, where each concept is defined by six different criteria. The results show that the syllabus favor a more functional perspective on grammar, whereas the teaching material Svenska rum 2 favors a more formal perspective on grammar. The teaching material Svenska impulser 2 expresses both a functional and a formal perspective on grammar. Its basis is a formal perspective on grammar, but the material includes several functional approaches to grammar and has therefore been interpreted as more functional than formal. This study concludes that Svenska impulser 2 can be considered to correlate with the syllabus, even though the functional aspects could be developed further. However, the syllabus cannot be considered to correlate with the grammar sections in Svenska rum 2 in regards to the concept of functional grammar.

A variety of markup languages exist for formatting text and exporting to HTML. These languages are tailored to the needs in a specific context by specialising tags, selecting tags and limiting the number of possible distinctions to a subset of what is available in HTML. However, limiting the number of possible distinctions creates problems when changes occur in the context. The real world is ever-changing, thus that which models it must be able to reflect the changes in the operational environment to remain relevant and satisfactory. Incorporating new requirements and adjusting to the changes in requirements means adapting and evolving. This thesis explores giving document authors the possibility to extend and modify the repertoire of available markup tags when new user requirements demand it. What is presented is a prototype which allows the user to tailor the markup and also adapt it to changes in the environment. The system allows users to create their own set of markup tags, annotate their documents with them, and export a generated XML document. Users create the tag and assign a meaning to it, when changes occur in the requirements they can be implemented by modifying the tags, extending the repertoire by adding tags, or changing the meaning of a defined tag.

La reconnaissance de la langue des signes française (LSF) comme une langue à part entière en 2005 a créé un besoin important de développement d’outils informatiques pour rendre l’information accessible au public sourd. Dans cette perspective, cette thèse a pour cadre la modélisation linguistique pour un système de génération de la LSF. Nous présentons dans un premier temps les différentes approches linguistiques ayant pour but la description linguistique des langues des signes (LS). Nous présentons ensuite les travaux effectués en informatique pour les modéliser.Dans un deuxième temps, nous proposons une approche permettant de prendre en compte les caractéristiques linguistiques propres au LS tout en respectant les contraintes d’un processus de formalisation. En étudiant des liens entre des fonctions sémantiques et leurs formes observées dans les corpus LSF, nous avons identifié plusieurs règles de production. Nous présentons finalement le fonctionnement des règles comme étant un système susceptible de modéliser un énoncé entier en LSF. / The recognition of French Sign Language (LSF) as a natural language in 2005 has created an important need for the development of tools to make information accessible to the deaf public. With this prospect, this thesis aims at linguistic modeling for a system of generation of LSF. We first present the different linguistic approaches aimed at describing the sign language (SL). We then present the models proposed in computer science. In a second step, we propose an approach allowing to take into account the linguistic properties of the SL while respecting the constraints of a formalisation process.By studying the links between semantic functions and their observed forms in LSF Corpora, we have identified several production rules. We finally present the rule functioning as a system capable of modeling an entire utterance in LSF.

This paper concerns a specific pursuit-evasion problem with a node-located evader which we call the monk problem. First, we propose a way of verifying a strategy using a new kind of recursive systems, called EL-systems. We show how an EL-system representing a graph-instance of the problem can be represented using matrices, and we give an example of how this can be used to efficiently implement a verifier. In the later parts we propose heuristics to construct a strategy, based on a greedy algorithm. Our main focus is to minimise the number of pursuers needed, called the search number. The heuristics rely on properties of minimal stable components. We show that the minimal stable components are equivalent to the strongly connected components of a graph, and prove that the search number is equal to the maximum search number of its strongly connected components. We also establish lower and upper bounds for the search number to narrow the search space. / Denna rapport avhandlar ett specifikt pursuit-evasion problem med en hörnplacerad flykting, som vi kallar för munkproblemet. Först föreslår vi ett sätt att verifiera en strategi med en ny typ av rekursivt system, kallat EL-system. Vi visar hur ett EL-system som representerar en grafinstans av munkproblemet kan representeras med matriser, och vi ger ett exempel på hur detta kan användas för att effektivt implementera en verifikator. I de senare delarna föreslår vi heuristiker för att konstruera en strategi, baserad på giriga algoritmer. Vårt huvudfokus är att minimera antalet förföljare som krävs för att dekontaminera grafen, det så kallade söktalet. Vår heuristik förlitar sig på egenskaper för minimala stabila komponenter. Vi visar att minimala stabila komponenter är ekvivalenta med de starka komponenterna i en graf, och härleder att söktalet är lika med det maximala söktalet för grafens starka komponenter. Vi etablerar också undre och övre gränser för söktalet i syfte att minska sökintervallet.

No description available.

In this thesis, three methods are investigated to express context-free tree languages by regular tree grammars. The first method is a characterization. We show restrictions to context-free tree grammars such that, for each restricted context-free tree grammar, a regular tree grammar can be constructed that induces the same tree language. The other two methods are approximations. An arbitrary context-free tree language can be approximated by a regular tree grammar with a restricted pushdown storage. Furthermore, we approximate weighted context-free tree languages, induced by weighted linear nondeleting context-free tree grammars, by showing how to approximate optimal weights for weighted regular tree grammars.

In this thesis, three methods are investigated to express context-free tree languages by regular tree grammars. The first method is a characterization. We show restrictions to context-free tree grammars such that, for each restricted context-free tree grammar, a regular tree grammar can be constructed that induces the same tree language. The other two methods are approximations. An arbitrary context-free tree language can be approximated by a regular tree grammar with a restricted pushdown storage. Furthermore, we approximate weighted context-free tree languages, induced by weighted linear nondeleting context-free tree grammars, by showing how to approximate optimal weights for weighted regular tree grammars.