Martin Berglund

Dr. Martin Berglund

orcid

Research Focus & Metrics

Academic Career Length

12Years (2015-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
15 September 2023 in Electronic Proceedings in Theoretical Computer Science
Verified
Journal Article
Open access
PDF file
MBMartin Berglund
Martin Berglund
BMBrink Van der Merwe
Brink Van der Merwe
In this paper, we formalize practical byte pair encoding tokenization as it is used in large language models and other NLP systems, in particular we formally define and investigate the semantics of the SentencePiece and HuggingFace tokenizers, in particular how they relate to each other, depending on how the tokenization rules are constructed. Beyond this we consider how tokenization can be performed in an incremental fashion, as well as doing it left-to-right using an amount of memory constant in the length of the string, enabling e.g. using a finite state string-to-string transducer.

1 May 2017 in Theoretical Computer Science
Verified
Journal Article
Closed access
MBMartin Berglund
Martin Berglund
BMBrink van der Merwe
Brink van der Merwe

3 September 2024
Verified
Book Chapter
Closed access
PDF file
MBMartin Berglund
Martin Berglund
WMWilleke Martens
Willeke Martens
BMBrink Van der Merwe
Brink Van der Merwe

11 May 2016 in Algorithms
Verified
Journal Article
Open access
PDF file
HBHenrik Björklund
Henrik Björklund
MBMartin Berglund
Martin Berglund
PEPetter Ericson
Petter Ericson
Parsing for mildly context-sensitive language formalisms is an important area within natural language processing. While the complexity of the parsing problem for some such formalisms is known to be polynomial, this is not the case for all of them. This article presents a series of results regarding the complexity of parsing for linear context-free rewriting systems and deterministic tree-walking transducers. We discuss the difference between uniform and nonuniform complexity measures and how parameterized complexity theory can be used to investigate how different aspects of the formalisms influence how hard the parsing problem is. The main results we survey are all hardness results and indicate that parsing is hard even for relatively small values of parameters such as rank and fan-out in a rewriting system.

28 July 2015
Verified
Book Chapter
Closed access
PDF file
MBMartin Berglund
Martin Berglund
BMBrink Van der Merwe
Brink Van der Merwe

15 October 2018
Verified
Book Chapter
Closed access
PDF file
MBMartin Berglund
Martin Berglund
WBWillem Bester
Willem Bester
BMBrink Van der Merwe
Brink Van der Merwe