Search for dissertations about: "context-free"

Showing result 1 - 5 of 15 swedish dissertations containing the word context-free.

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. Constraints for Membership in Formal Languages under Systematic Search and Stochastic Local Search

   Author : Jun He; Pierre Flener; Justin Pearson; Yves Deville; Uppsala universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; constraint programming; regular constraint; automaton constraint; context-free grammar constraint; solution neighbourhood; counter automaton; Datavetenskap; Computer Science;

   Abstract : This thesis focuses on constraints for membership in formal languages under both the systematic search and stochastic local search approaches to constraint programming (CP). Such constraints are very useful in CP for the following three reasons: They provide a powerful tool for user-level extensibility of CP languages. READ MORE

7. 5. 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