Search for dissertations about: "context-free grammars"

Showing result 1 - 5 of 8 swedish dissertations containing the words context-free grammars.

2. 1. Expressivity and Complexity of the Grammatical Framework

   Author : Peter Ljunglöf; Göteborgs universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; Grammatical Framework; generalized context-free grammar; multiple context-free grammar; context-free rewriting systems; type theory; expressive power; abstract syntax; linearization; parsing; context-free rewriting systems;

   Abstract : This thesis investigates the expressive power and parsing complexity of the Grammatical Framework (GF), a formalism originally designed for displaying formal propositions and proofs in natural language. This is done by relating GF with two more well-known grammar formalisms; Generalized Context-Free Grammar (GCFG), best seen as a framework for describing various grammar formalisms; and Parallel Multiple Context-Free Grammar (PMCFG), an instance of GCFG. READ MORE

4. 2. Complexities of Order-Related Formal Language Extensions

   Author : Martin Berglund; Frank Drewes; Henrik Björklund; Markus Holzer; Umeå universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; complexity; automata; languages; order; shuffle; regular expressions; context-free; mildly context-sensitive; parsing; membership; algorithm analysis; Computer Science; datalogi;

   Abstract : The work presented in this thesis discusses various formal language formalisms that extend classical formalisms like regular expressions and context-free grammars with additional abilities, most relating to order. This is done while focusing on the impact these extensions have on the efficiency of parsing the languages generated. READ MORE

5. 3. Pure Functional Parsing - an advanced tutorial

   Author : Peter Ljunglöf; Göteborgs universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; context-free grammars; parsing algorithms; parser combinators; functional programming;

   Abstract : Parsing is the problem of deciding whether a sequence of tokens is recognized by a given grammar, and in that case returning the grammatical structure of the sequence. This thesis investigates di erent aspects of the parsing problem from the viewpoint of a functional programmer. READ MORE

6. 4. Modeling of bacterial DNA patterns important in horizontal gene transfer using stochastic grammars

   Author : Mariana Buongermino Pereira; Göteborgs universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Stochastic context-free grammars; hidden Markov model; conditional random fields; integrons; attC sites; secondary structure.; secondary structure.;

   Abstract : DNA contains genes which carry the blueprints for all processes necessary to maintain life. In addition to genes, DNA also contains a wide range of functional patterns, which governs many of these processes. These functional patterns have typically a high variability, both within and between species, which makes them hard to detect. READ MORE

7. 5. Complexity and expressiveness for formal structures in Natural Language Processing

   Author : Petter Ericson; Henrik Björklund; Frank Drewes; Umeå universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; graph grammars; formal languages; natural language processing; parameterized complexity; abstract meaning representation; tree automata; deterministic tree-walking transducers; mildly context-sensitive languages; hyperedge replacement; tree adjoining languages; minimally adequate teacher;

   Abstract : 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. READ MORE