Martin Berglund

Researcher in the areas of fundamental algorithms, automata theory, and the theory of machine learning. Teaches courses in this area.

Contact

martin.berglund@umu.se

Works at

Associate professor at Department of Computing Science

MIT-huset, Umeå universitet, MIT.C.447 Umeå universitet, 901 87 Umeå

Parsing unranked tree languages, folded once

Algorithms, MDPI 2024, Vol. 17, (6)

Berglund, Martin; Björklund, Henrik; Björklund, Johanna

Constructing a BPE Tokenization DFA

Implementation and Application of Automata: 28th International Conference, CIAA 2024, Akita, Japan, September 3–6, 2024, Proceedings, Springer 2024 : 66-78

Berglund, Martin; Martens, Willeke; van der Merwe, Brink

Parsing unranked tree languages, folded once

Fundamentals of computation theory: 24th International Symposium, FCT 2023, Trier, Germany, September 18–21, 2023, Proceedings, Springer Nature 2023 : 60-73

Berglund, Martin; Björklund, Henrik; Björklund, Johanna

Transduction from trees to graphs through folding

Information and Computation, Elsevier 2023, Vol. 295

Berglund, Martin; Björklund, Henrik; Björklund, Johanna; et al.

Re-examining regular expressions with backreferences

Theoretical Computer Science, Elsevier 2023, Vol. 940 : 66-80

Berglund, Martin; van der Merwe, Brink

Formalizing BPE Tokenization

13th International Workshop onNon-Classical Models of Automata and Applications (NCMA 2023), Open Publishing Association 2023 : 16-27

Berglund, Martin; van der Merwe, Brink

Ordered Context-Free Grammars

Implementation and Application of Automata: 26th International Conference, CIAA 2022, Rouen, France, June 28 – July 1, 2022, Proceedings, Springer Science+Business Media B.V. 2022 : 53-66

van der Merwe, Brink; Berglund, Martin

Formalising and implementing Boost POSIX regular expression matching

Theoretical Computer Science, Elsevier 2021, Vol. 857 : 147-165

Berglund, Martin; Bester, Willem; van der Merwe, Brink

Regular Expressions with Lookahead

Journal of universal computer science (Online), Vol. 27, (4) : 324-340

Berglund, Martin; van der Merwe, Brink; van Litsenborgh, Steyn

Memoized Regular Expressions

Implementation and Application of Automata: 25th International Conference, CIAA 2021, Virtual Event, July 19-22, 2021, Proceedings, Springer 2021 : 39-52

van der Merwe, Brink; Mouton, Jacobie; van Litsenborgh, Steyn; et al.

Regular Expressions with Backreferences Re-examined

Proceedings of the Prague Stringology Conference 2017, Praque Stringology Club 2017 : 30-41

Berglund, Martin; van der Merwe, Brink

On the semantics of regular expression parsing in the wild

Theoretical Computer Science, Elsevier 2017, Vol. 679 : 69-82

Berglund, Martin; van der Merwe, Brink

On the Semantics of Atomic Subgroups in Practical Regular Expressions

Implementation and Application of Automata: 22nd International Conference, CIAA 2017, Marne-la-Vallée, France, June 27-30, 2017, Proceedings, Springer 2017 : 14-26

Berglund, Martin; van der Merwe, Brink; Bruce, Watson

Turning evil regexes harmless

SAICSIT '17: Proceedings of the South African Institute of Computer Scientists and Information Technologists

van der Merwe, Brink; Weideman, Nicolaas; Berglund, Martin

Uniform vs. Nonuniform Membership for Mildly Context-Sensitive Languages: A Brief Survey

Algorithms, MDPI 2016, Vol. 9, (2)

Björklund, Henrik; Berglund, Martin; Petter, Ericson

Analyzing Matching Time Behavior of Backtracking Regular Expression Matchers by Using Ambiguity of NFA

Implementation and Application of Automata, Springer 2016 : 322-334

Weideman, Nicolaas; van der Merwe, Brink; Berglund, Martin; et al.

Complexities of Order-Related Formal Language Extensions

Report / UMINF, 2014:13

Berglund, Martin

Characterizing Non-Regularity

Report / UMINF, 14.12

Berglund, Martin

Analyzing catastrophic backtracking behavior in practical regular expression matching

Proceedings 14th international conference on automata and formal languages (AFL 2014), Open Publishing Association 2014 : 109-123

Berglund, Martin; Drewes, Frank; van der Merwe, Brink

Shuffled languages: representation and recognition

Theoretical Computer Science, Elsevier 2013, Vol. 489-490 : 1-20

Berglund, Martin; Björklund, Henrik; Björklund, Johanna

On the Parameterized Complexity of Linear Context-Free Rewriting Systems

Proceedings of the 13th Meeting on the Mathematics of Language (MoL 13), Association for Computational Linguistics 2013 : 21-29

Berglund, Martin; Björklund, Henrik; Drewes, Frank

Cuts in Regular Expressions

Developments in Language Theory: 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings, Springer Berlin/Heidelberg 2013 : 70-81

Berglund, Martin; Björklund, Henrik; Drewes, Frank; et al.

Complexities of Parsing in the Presence of Reordering

Report / UMINF, 12.10

Berglund, Martin

The Membership Problem for the Shuffle of Two Deterministic Linear Context-Free Languages is NP-complete

Report / UMINF, 12.09

Berglund, Martin

Analyzing Edit Distance on Trees: Tree Swap Distance is Intractable

Proceedings of the Prague Stringology Conference 2011, Prague: Prague Stringology Club, Czech Technical University 2011 : 59-73

Berglund, Martin

Recognizing Shuffled Languages

Report / UMINF, 11.01

Berglund, Martin; Björklund, Henrik; Högberg, Johanna

Recognizing shuffled languages

Language and Automata Theory and Applications: 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings, Springer Berlin/Heidelberg 2011 : 142-154

Berglund, Martin; Björklund, Henrik; Högberg, Johanna

On the complexity of variants of the k Best strings problem

Proceedings of the Prague stringology conference 2010, dblp 2010 : 76-88

Berglund, Martin; Drewes, Frank

On the complexity of variants of the k best strings problem

Proc. Prague Stringology Conference 2010

Berglund, Martin; Drewes, Frank

View publications in DiVA

Research groups

Head of research

Foundations of Language Processing

I teach a variet of courses in the areas of programming and theory of computation. Including e.g. the Fundamentals of Computer Science and the Computational Complexity courses, as well as the summer course Programming for Effective Problem Solving.