Martin Berglund's Homepage

In the pipeline

Various journal versions of past papers, continued investigation of the "Characterizing non-regularity" track, funding applications.

Paper at CIAA

Berglund, Martin, and Brink van der Merwe. On the Semantics of Regular Expression Parsing in the Wild. Implementation and Application of Automata, pages 292-304, Springer, 2015. (PDF available here, requires appropriate subscription).

Thesis completed!

The final version of my thesis is now available here: here.

My thesis includes the following papers.

  1. Martin Berglund, Henrik Björklund, and Johanna Björklund. Shuffled languages – representation and recognition. Theoretical Computer Science, 489-490:1–20, 2013. (PDF available here , requires appropriate subscription.)
  2. Martin Berglund, Henrik Björklund, and Frank Drewes. On the parameterized complexity of Linear Context-Free Rewriting Systems. In Proceedings of the 13th Meeting on the Mathematics of Language (MoL 13), pages 21–29, Sofia, Bulgaria, August 2013. Association for Computational Linguistics. (PDF available here.)
  3. Martin Berglund, Henrik Björklund, Frank Drewes, Brink van der Merwe, and Bruce Watson. Cuts in regular expressions. In Developments in Language Theory, pages 70–81, 2013. (PDF available here.)
  4. Martin Berglund. Analyzing edit distance on trees: Tree swap distance is intractable. In Jan Holub and Jan Zdarek, editors, Proceedings of the Prague Stringology Conference 2011, pages 59–73. Prague Stringology Club, Czech Technical University, 2011. (PDF available here.)
  5. Martin Berglund, Frank Drewes, and Brink van der Merwe. Analyzing catatrophic backtracking behavior in practical regular expression matching. Submitted to the 14th International Conference on Automata and Formal Languages (AFL 2014), 2014.
  6. Martin Berglund. Characterizing non-regularity. Technical Report UMINF 14.12, Computing Science, Umeå University, http://www8.cs.umu.se/research/uminf/, 2014. In collaboration with Henrik Björklund and Frank Drewes.