Introduction
This is the page for all information concerning the licenciate thesis of Petter Ericson, to be presented in May of 2017. Below, you will find links and information on the component papers and, in time, the complete thesis.
The common theme of the papers is essentially algorithmic reasoning on structures used in natural language processing, with a particular focus on complexity issues on the one hand, and trees and tree-like graphs on the other. Even thus focused, the thesis is very broad, and there are among the papers everything from new proposed types of automata and language formalisms to comparisons and reductions concerning parameterized complexity theory in the NLP context.
Latest version of the kappa and cover. The full thesis as sent to the printer.
Papers
A Bottom-Up Automaton for Tree Adjoining Languages (Petter Ericson)
Technical Report UMINF 15.14 Dept. Computing Sci., Umeå University
A Note on the Complexity of Deterministic Tree-Walking Transducers (Henrik Björklund, Petter Ericson)
In Fifth Workshop on Non-Classical Models of Automata and Applications (NCMA), pp. 69-84, Austrian Computer Society, 2013.
Between a Rock and a Hard Place – Parsing for Hyperedge Replacement DAG Grammars (Henrik Björklund, Frank Drewes, Petter Ericson)
In Language and Automata Theory and Applications (LATA), pp. 521-532, Springer, 2016.
On the Regularity and Learnability of Ordered DAG Languages (Henrik Björklund, Johanna, Björklund, Petter Ericson)
In Conference on Implementation and Application of Automata (CIAA) 2017. Accepted for publication, to appear.
Investigating Different Graph Representations of Semantics (Petter Ericson)
Poster presentation at Swedish Language Technology Conference (http://sltc2016.cs.umu.se/) 2016